似乎是归队赛的最后一道题。
由于当时以为是公共字串所以没写555555，其实是求公共前缀。
做法是建立tire，把tire上的点编号看成是值，查询第l到第r个字符串的区间内不重复的值的个数。建立主席树维护即可
#include#include #include #include #define rep(i,l,r) for(int i=l;i<=r;i++)#define dow(i,l,r) for(int i=r;i>=l;i--)#define LL long long#define maxn 100100#define mm 100000#define maxm 8000000using namespace std;int lson[maxm],rson[maxm],size[maxm],root[maxn],num[maxn],n,m,toti,totr,tot,son[maxn][26],pre[maxn];char s[maxn];int more1(){ ++toti; memset(son[toti],0,sizeof(son[toti])); return toti;}int more2(){ ++totr; lson[totr]=0; rson[totr]=0; size[totr]=0; return totr;}void add(int &x,int old,int l,int r,int y,int z){ x=more2(); lson[x]=lson[old]; rson[x]=rson[old]; size[x]=size[old]+z; if (l==r) return; int mid=(l+r)>>1; if (y<=mid) add(lson[x],lson[old],l,mid,y,z); else add(rson[x],rson[old],mid+1,r,y,z);}int ask(int x,int y,int l,int r){// printf("%d %d %d %d %d %d %d\n",x,y,l,r,size[x],size[lson[x]],size[rson[x]]); if (!x) return 0; if (l==r) return size[x]; int mid=(l+r)>>1; if (y<=mid) return ask(lson[x],y,l,mid)+size[rson[x]]; return ask(rson[x],y,mid+1,r);} int main(){ while (scanf("%d",&n)!=EOF) { memset(pre,0,sizeof(pre)); toti=0; more1(); totr=0; tot=1; rep(i,1,n) { scanf("%s",s); int len=strlen(s); int u=1; root[i]=root[i-1]; rep(j,0,len-1) { // printf("\t%d\n",u); ++tot; if (!j) num[i]=tot; int k=s[j]-'a'; if (!son[u][k]) son[u][k]=more1(); // printf("\t%d\n",u); add(root[i],root[i],1,mm,tot,1); if (pre[son[u][k]]) { // printf("\t\t%d\n",pre[son[u][k]]); add(root[i],root[i],1,mm,pre[son[u][k]],-1); } pre[son[u][k]]=tot; u=son[u][k]; // printf("\t%d\n",u); } // printf("%d\n",size[root[i]]); } scanf("%d",&m); int z=0; while (m--) { int j,k; scanf("%d %d",&j,&k); int l=min((j+z)%n+1,(k+z)%n+1),r=max((j+z)%n+1,(k+z)%n+1); // printf("%d %d\n",l,r); printf("%d\n",z=ask(root[r],num[l],1,mm)); } } return 0;}