HDU – 5790 Prefix 求区间不同种数的变形weixin43824564的博客-

我们先看一个简单的问题 给你一个数组 q次询问  每个询问 给l和r  问区间l到r有多少种不同的数 

这个可以离线树状数组 ，离线线段树，还可以莫队  但是现在我要你在线解决  

那么就只能用主席树了  还是那个套路 我们建立第0棵树 然后在0棵树的基础上建立第一颗树  然后在第一棵树的基础上建立第2棵树。。。以此类推  如果我们在建立第i棵树时  发现val[i]在前面已经出现了 我们记录这个位置  然后在第i棵树里面 让这个位置-1 然后在i位置+1  这样对于询问l,r 我们查询第r棵树里面 区间l到r的和就行

这道题也和上面那道题大同小异  只不过 一个字符串 有多个前缀  我们要进行判重  并且记录每个字符串出现的位置  这些操作用trie很方便  具体看代码解释 

 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5+10; int trie[N][26],cnt; int tot,rt[N],flag[N]; // flag标记串出现的最晚位置  int n,m,z; char s[N]; struct node{  int l,r,s; }t[N*50]; int update(int lasrt,int l,int r,int pos,int val){  ++tot;t[tot]=t[lasrt];  t[tot].s=t[lasrt].s+val;  if(l==r) return tot;  int mid = l+r>>1,now = tot;  if(pos<=mid) t[now].l=update(t[lasrt].l,l,mid,pos,val);  else{t[now].r=update(t[lasrt].r,mid+1,r,pos,val);}  return now;   } int query(int rt,int l,int r,int ql,int qr){  if(ql<=l&&qr>=r) return t[rt].s;  int mid = l+r>>1,ans = 0;  if(ql<=mid) ans+=query(t[rt].l,l,mid,ql,qr);  if(qr>mid) ans+=query(t[rt].r,mid+1,r,ql,qr);  return ans;  } int main(){  while(~scanf("%d",&n)){   tot=cnt=0;   memset(trie[0],0,sizeof(trie[0]));   for(int i = 1; i <= n; i++){    scanf("%s",s+1);    rt[i]=rt[i-1];//在i-1的基础上建立第i棵树      int len = strlen(s+1),p = 0;    for(int j = 1; j <= len; j++){     int c = s[j]-'a';     if(!trie[p][c])      trie[p][c]=++cnt,flag[cnt]=0,memset(trie[cnt],0,sizeof(trie[cnt]));     p = trie[p][c];     if(flag[p]) rt[i]=update(rt[i],1,n,flag[p],-1);//这个前缀出现过 在对应位置-1      flag[p]=i;//更新前缀出现的位置     }    rt[i]=update(rt[i],1,n,i,len);//这个串对这个位置的贡献是len    }   scanf("%d",&m);   z=0;   for(int i = 1; i <= m; i++){    int l,r;    scanf("%d%d",&l,&r);    l=(l+z)%n+1,r=(r+z)%n+1;    if(l>r) swap(l,r);    z=query(rt[r],1,n,l,r);    printf("%dn",z);   }  }  return 0; }