都快忘了在这类题的经典做法了……
将字符串一个个的插入字典树，在字典树维护好有该前缀串s的最大编号字符串j，我们记作j控制了前缀串s
对于当前的第i个字符串，维护此时有当前每个字符串控制了多少个前缀串，用一个线段树维护。
由于询问是在线的，所以用主席树来维护。于是对一个询问(l,r)，在第r个线段树求一下区间(l,r)的和即为答案。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 struct node{ int l,r,s;} tree[200010*20]; 8 int go[100010][26],h[100010],be[100010]; 9 char s[100010];10 int m,t,n,q;11 12 int build(int l,int r)13 {14 ++t; tree[t].l=tree[t].r=tree[t].s=0;15 if (l==r) return t;16 else {17 int cur=t,m=(l+r)>>1;18 tree[cur].l=build(l,m);19 tree[cur].r=build(m+1,r);20 return cur;21 }22 }23 24 int work(int l,int r,int last,int x,int w)25 {26 ++t; tree[t]=tree[last];27 if (l==r) {tree[t].s+=w; return t;}28 else {29 int cur=t,m=(l+r)>>1;30 if (x<=m) tree[cur].l=work(l,m,tree[last].l,x,w);31 else tree[cur].r=work(m+1,r,tree[last].r,x,w);32 tree[cur].s=tree[tree[cur].l].s+tree[tree[cur].r].s;33 return cur;34 }35 }36 37 int ask(int l,int r,int p,int x,int y)38 {39 if (x<=l&&y>=r) return tree[p].s;40 else {41 int m=(l+r)>>1,s=0;42 if (x<=m) s+=ask(l,m,tree[p].l,x,y);43 if (y>m) s+=ask(m+1,r,tree[p].r,x,y);44 return s;45 }46 }47 48 int main()49 {50 while (scanf("%d",&n)!=EOF)51 {52 t=m=0;53 h[0]=build(1,n);54 memset(go[0],0,sizeof(go[0]));55 for (int i=1; i<=n; i++)56 {57 scanf("%s",s+1);58 int k=0,l=strlen(s+1);59 h[i]=h[i-1];60 for (int j=1; j<=l; j++)61 {62 int c=s[j]-'a';63 if (!go[k][c]) {go[k][c]=++m; memset(go[m],0,sizeof(go[m])); be[m]=0;}64 k=go[k][c];65 if (be[k]) h[i]=work(1,n,h[i],be[k],-1);66 be[k]=i;67 }68 h[i]=work(1,n,h[i],i,l);69 }70 scanf("%d",&q);71 int z=0;72 for (int i=1; i<=q; i++)73 {74 int l,r;75 scanf("%d%d",&l,&r);76 l=(z+l)%n+1; r=(z+r)%n+1;77 if (l>r) swap(l,r);78 z=ask(1,n,h[r],l,r);79 printf("%d\n",z);80 }81 }82 return 0;83 }