題目鏈接

PRefix

3abcababaa30 20 11 1 Sample Output
763 AuthorZSTU Source2016 Multi-University Training Contest 5 
參考題解
題意：給你n個字符串，問你第L個字符串到R個字符串中不同前綴的個數，且強制在線。
思路：這題和之前d-query這題很相似，那題問的是區間內不同數的種類。這題問的是不同前綴個數，所以我們可以先把所有的字符串插入到Trie樹中，然后每次插入維護每一個節點最后被遍歷到的時刻，然后用主席樹維護下就行了。
聽說也可以hash每個前綴，然后再用主席樹維護。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=1e5+100;int a[maxn][27];//int cnt=0,tot=0,n;int root[maxn],p[maxn]; //struct node{    int l,r,sum;}T[maxn*40];void update(int l,int r,int &x,int y,int pos,int val){    T[++cnt]=T[y],x=cnt,T[cnt].sum+=val;    if(l==r) return;    int m=(l+r)/2;    if(pos<=m) update(l,m,T[x].l,T[y].l,pos,val);    else update(m+1,r,T[x].r,T[y].r,pos,val);}char s[maxn];void insert(int x){    int l=strlen(s);    int u=0;    rep(i,0,l)    {        if(!a[u][s[i]-'a'])        {            a[u][s[i]-'a']=++tot;            p[tot]=x;            if(i) update(1,n,root[x],root[x],x,1);            else update(1,n,root[x],root[x-1],x,1);                    }        else        {            int t=p[a[u][s[i]-'a']];            if(i) update(1,n,root[x],root[x],t,-1);            else update(1,n,root[x],root[x-1],t,-1);            update(1,n,root[x],root[x],x,1);            p[a[u][s[i]-'a']]=x;        }        u=a[u][s[i]-'a'];    }}int query(int l,int r,int x,int pos){    if(l==r) return T[x].sum;    int m=(l+r)/2;    if(pos<=m) return query(l,m,T[x].l,pos)+T[T[x].r].sum;    else return query(m+1,r,T[x].r,pos);}int main(){        while(~scanf("%d",&n))    {        memset(a,0,sizeof(a));        tot=0,cnt=0;        memset(root,0,sizeof(root));        memset(T,0,sizeof(T));        memset(p,0,sizeof(p));        rep(i,1,n+1)        {            scanf("%s",s);            insert(i);        }        int q,z=0;        scanf("%d",&q);        while(q--)        {            int l,r;            scanf("%d%d",&l,&r);            l=(l+z)%n,r=(r+z)%n;            l++,r++;            if(l>r) swap(l,r);            z=query(1,n,root[r],l);//            printf("%d/n",z);        }    }    return 0;}