当前位置：首页 > news >正文

青海餐饮网站建设成都seo整站

news 2025/8/12 22:25:35

青海餐饮网站建设,成都seo整站,惠州市网站开发公司,乌鲁木齐公司网站建设题面先把每个串反着插进$Trie$树每个节点的子树内，可能有一些节点是某些字符串的开头每个节点挂一棵权值线段树，记录这些节点对应的原来字符串的编号查询的时候在线段树上二分即可为了节省空间，使用线段树合并 1 #include <vector>…

题面

先把每个串反着插进$Trie$树

每个节点的子树内，可能有一些节点是某些字符串的开头

每个节点挂一棵权值线段树，记录这些节点对应的原来字符串的编号

查询的时候在线段树上二分即可

为了节省空间，使用线段树合并

  1 #include <vector>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 100100
  6 #define M1 (N1*3)
  7 #define idx(X) (X-'a')
  8 using namespace std;
  9 
 10 char str[M1];
 11 int a[N1],n;
 12 
 13 struct SEG{
 14 int sz[N1*100],ls[N1*100],rs[N1*100],root[M1],tot;
 15 inline void pushup(int rt){ sz[rt]=sz[ls[rt]]+sz[rs[rt]]; }
 16 void update(int x,int l,int r,int &rt,int w)
 17 {
 18     if(!rt) rt=++tot;
 19     if(l==r){ sz[rt]+=w; return; }
 20     int mid=(l+r)>>1; 
 21     if(x<=mid) update(x,l,mid,ls[rt],w);
 22     else update(x,mid+1,r,rs[rt],w);
 23     pushup(rt);
 24 }
 25 int merge(int l,int r,int r1,int r2)
 26 {
 27     if(!r1||!r2) return r1+r2;
 28     int mid=(l+r)>>1,rt=++tot;
 29     //sz[rt]=sz[r1]+sz[r2];
 30     ls[rt]=merge(l,mid,ls[r1],ls[r2]);
 31     rs[rt]=merge(mid+1,r,rs[r1],rs[r2]);
 32     pushup(rt);
 33     return rt;
 34 }
 35 int query(int l,int r,int rt,int K)
 36 { 
 37     if(K>sz[rt]) return -1;
 38     if(l==r) return l;
 39     int mid=(l+r)>>1;
 40     if(K>sz[ls[rt]]) return query(mid+1,r,rs[rt],K-sz[ls[rt]]);
 41     else return query(l,mid,ls[rt],K);
 42 }
 43 }s;
 44 
 45 namespace Trie{
 46 int ch[M1][26],dep[M1],fa[M1],tot;
 47 vector<int>ed[M1];
 48 void insert(int len,int id,int *pos)
 49 {
 50     int x=0,c,i;
 51     for(i=len;i>=1;i--)
 52     {
 53         c=idx(str[i]);
 54         if(!ch[x][c]) 
 55             ch[x][c]=++tot,dep[tot]=dep[x]+1,fa[tot]=x;
 56         x=ch[x][c];
 57     }
 58     ed[x].push_back(id);
 59     pos[id]=x;
 60 }
 61 int hs[M1],que[M1];
 62 void build()
 63 {
 64     int i,j,id,x;
 65     for(i=1;i<=tot;i++) hs[dep[i]]++;
 66     for(i=1;i<=tot;i++) hs[i]+=hs[i-1];
 67     for(i=1;i<=tot;i++) que[hs[dep[i]]--]=i;
 68     for(i=tot;i>=1;i--)
 69     {
 70         x=que[i];
 71         for(j=0;j<ed[x].size();j++)
 72         {
 73             id=ed[x][j];
 74             s.update(id,1,n,s.root[x],1);
 75         }
 76     }
 77     for(i=tot;i>=1;i--)
 78     {
 79         x=que[i];
 80         s.root[fa[x]]=s.merge(1,n,s.root[x],s.root[fa[x]]);
 81     }
 82 }
 83 };
 84 
 85 int pos[M1];
 86 int main()
 87 {
 88     scanf("%d",&n);
 89     int i,j,k,cnt,L;
 90     for(i=1;i<=n;i++)
 91     {
 92         scanf("%s",str+1);
 93         L=strlen(str+1);
 94         Trie::insert(L,i,pos);
 95     }
 96     Trie::build();
 97     for(i=1;i<=n;i++)
 98     {
 99         scanf("%d",&a[i]);
100         printf("%d\n",s.query(1,n,s.root[pos[i]],a[i]));
101     }
102     return 0;
103 }