【HDU - 5790 】Prefix（主席树+Trie树）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

const int N=100005;
const int M=N*40;

using namespace std;

namespace PST{
    int T[N],lson[M],rson[M],tot,c[M],n;

    void init(int _n){
        tot=0;
        n=_n;
        memset(c,0,sizeof c);
    }

    int build(int l,int r){
        ++tot;
        c[tot]=0;
        if(l<r){
            int mid=l+r>>1;
            lson[tot]=build(l,mid);
            rson[tot]=build(mid+1,r);
        }
        return tot;
    }

    int update(int root,int pos,int val){
        int newroot=++tot, tmp=tot;
        c[tmp]=c[root]+val;
        int l=1,r=n;

        while(l<r){
            int mid=l+r>>1;
            if(pos<=mid){
                lson[newroot]=++tot; rson[newroot]=rson[root];
                root=lson[root];
                r=mid;
            }
            else{
                rson[newroot]=++tot; lson[newroot]=lson[root];
                root=rson[root];
                l=mid+1;
            }

            newroot = tot;
            c[newroot] = c[root] + val;
        }
        return tmp;
    }

    int query(int root,int pos){
        int ret=0;
        int l=1,r=n;
        while(l<pos){
            int mid=l+r>>1;
            if(pos<=mid){
                ret+=c[rson[root]];
                r=mid;
                root=lson[root];
            }
            else{
                l=mid+1;
                root=rson[root];
            }
        }
        return c[root]+ret;
    }
}

namespace Trie{
    int node[N][27];
    int tot, pre[N];

    void Insert(string& s,int x){
        int cur=0;
        for(int i=0;i<s.size();++i){
            int p=s[i]-'a';
            if(node[cur][p]==0)
                node[cur][p]=++tot;

            cur=node[cur][p];
            if(pre[cur]){
                PST::T[x]=PST::update(PST::T[x], pre[cur], -1);
            }
            pre[cur]=x+1;

        }
    }

    void init(){
        tot=0;
        memset(node,0,sizeof node);
        memset(pre,0,sizeof pre);
    }
}

string s;

int main(){
    int n;
    while(~scanf("%d",&n)){
        int z=0;
        Trie::init();
        PST::init(n);
        PST::T[0]=PST::build(1,n);
        for(int i=0;i<n;++i){
            if(i)PST::T[i]=PST::T[i-1];
            cin>>s;
            Trie::Insert(s, i);
            PST::T[i]=PST::update(PST::T[i], i+1, s.size());
        }
        int q;
        scanf("%d",&q);
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            l=(l+z)%n,r=(r+z)%n;
            if(r<l)swap(l,r);
            z=PST::query(PST::T[r],l+1);
            printf("%d\n",z);
        }
    }
    return 0;
}