hdu_5790_Prefix(trie+主席树)

题目链接：hdu_5790_Prefix

题意：

给你n个字符串，字符串总长度不超过10W，然后给你一个区间，问你这个区间的字符串不相同的前缀有多少个。

题解：

由于z与上一个答案有关，所以强制在线，区间询问可以用主席树搞搞。

不同前缀的话，我们可以用一个trie来记录每一个节点的最晚出现时间，也就代表了这个前缀最晚出现的时间，然后保存到对应的主席树中。

这样就转换为询问区间不大于l的数有多少个。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=1e5+7;
char s[N];
int root[N],tot,n,q;
struct node{int l,r,sum;}T[25*N];

void update(int &x,int y,int pos,int l=1,int r=n)
{
    T[++tot]=T[y],T[tot].sum++,x=tot;
    if(l==r)return;
    int m=l+r>>1;
    if(pos<=m)update(T[x].l,T[y].l,pos,l,m);
    else update(T[x].r,T[y].r,pos,m+1,r);
}

int query(int x,int y,int k,int l=1,int r=n)
{
    if(l==r)return T[x].sum-T[y].sum;
    int m=l+r>>1;
    if(k<=m)return query(T[x].l,T[y].l,k,l,m);
    else return T[T[x].l].sum-T[T[y].l].sum+query(T[x].r,T[y].r,k,m+1,r);
}

struct Trie{
    int tr[N][26],tot,mx[N];
    void nd(){mx[++tot]=0,memset(tr[tot],0,sizeof(tr[tot]));}
    void init(){tot=-1,nd();}
    void insert(char *s,int time)
    {
        int t1=root[time-1],t2;
        for(int i=0,x=0;s[i]!='';i++)
        {
            if(!tr[x][s[i]-'a'])
            {
                nd(),update(t2,t1,1);
                t1=t2,tr[x][s[i]-'a']=tot,mx[tot]=time,x=tot;
            }
            else update(t2,t1,mx[x=tr[x][s[i]-'a']]+1),t1=t2,mx[x]=time;
        }
        root[time]=t1;
    }
}trie;

void init(){tot=0;trie.init();}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        F(i,1,n)scanf("%s",s),trie.insert(s,i);
        scanf("%d",&q);
        int l,r,z=0;
        F(i,1,q)
        {
            scanf("%d%d",&l,&r);
            l=(z+l)%n+1,r=(z+r)%n+1;
            if(l>r)l^=r,r^=l,l^=r;
            printf("%d
",z=query(root[r],root[l-1],l));
        }
    }
    return 0;
}