Prefix

Time Limit: 2000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 791 Accepted Submission(s): 226

Problem Description

Alice gets N strings. Now she has Q questions to ask you. For each question, she wanna know how many different prefix strings between Lth and Rth strings. It's so easy right? So solve it!

Input

The input contains multiple test cases.

For each test case, the first line contains one integer

N(1≤N≤100000) . Then next N lines contain N strings and the total length of N strings is between 1 and 100000. The next line contains one integer

Q(1≤Q≤100000) . We define a specail integer Z=0. For each query, you get two integer L, R(0=<L,R<N). Then the query interval [L,R] is [min((Z+L)%N,(Z+R)%N)+1,max((Z+L)%N,(Z+R)%N)+1]. And Z change to the answer of this query.

Output

For each question, output the answer.

Sample Input

3abcababaa30 20 11 1

Sample Output

Author

ZSTU

Source

题意：给你n个字符串，问你第L个字符串到R个字符串中不同前缀的个数，且强制在线。

思路：这题和之前d-query这题很相似，那题问的是区间内不同数的种类。这题问的是不同前缀个数，所以我们可以先把所有的字符串插入到Trie树中，然后每次插入维护每一个节点最后被遍历到的时刻，然后用主席树维护下就行了。

听说也可以hash每个前缀，然后再用主席树维护。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              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;}

转载地址：https://blog.csdn.net/fouzhe/article/details/55670041 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Codeforces Round #397 E. Tree Fold(bfs,想法题,好题)

下一篇：gym100812G(想法题,最短路变形,好题)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

Prefix

发表评论

最新留言

关于作者

推荐文章