#include<bits/stdc++.h> #define fi first #define se second #define INF 0x3f3f3f3f #define LNF 0x3f3f3f3f3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=4e5+8; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; const int maxp=26+5; using namespace std; struct Suffix_Node{ int ch[maxp],par,len,jg; LL dd[64]; void init(){ NEW(ch,0); par=len=0; } }; int num[maxn]; int la[maxn],ra[maxn]; int st[maxn]; int n,k; ULL ans[maxn]; pair<ULL,int> w[maxn]; class Suffix_Automation{ private: Suffix_Node s[maxn]; int cur,las,siz,crp,dx; vector<int> gg[maxn]; struct node{ int to,nxt; }g[maxn]; int cnt,head[maxn],pk[maxn]; public: Suffix_Automation():las(1),cur(1),siz(1),crp(1){} const void init(){ for(int i=0;i<=siz;i++) { pk[i]=0;s[i].init(); for(int j=0;j<=60;j++) s[i].dd[j]=0; gg[i].clear(); ans[i]=0; for(int j=0;j<20;j++){ f[i][j]=0; } } las=cur=siz=crp=1; cnt=0; head[0]=head[1]=-1; dx=0; } const int match(const char c)const{ return s[crp].ch[c-'a']; } const void withdraw(const int len){ while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par; if(crp==0) crp=1; } const void Transfer(const int len,const char c){ crp=s[crp].ch[c-'a']; if(crp==0) crp=1; withdraw(len); } const void ex_tend(const char c){ int x=c-'a'; cur=++siz; head[siz]=-1; s[cur].len =s[las].len+1; s[cur].jg=1; while(las!=0&&!s[las].ch[x]) s[las].ch[x]=cur,las=s[las].par; if(las==0) s[cur].par=1; else{ int q,nq; q=s[las].ch[x]; if(s[q].len==s[las].len+1) s[cur].par=q; else{ nq=++siz; head[siz]=-1; s[nq]=s[q],s[nq].len=s[las].len+1; s[nq].jg=0; s[cur].par=s[q].par=nq; while(las!=0&&s[las].ch[x]==q) s[las].ch[x]=nq,las=s[las].par; } } las=cur; } void dfs(int u){ if(f[u][0]) return ; add(s[u].par,u); if(s[u].par!=1){ dfs(s[u].par); } f[u][0]=s[u].par; } void solve(){ for(int i=2;i<=siz;i++){ if(!f[i][0]){ dfs(i); } } for(int j=1;j<20;j++){ for(int i=1;i<=siz;i++){ f[i][j]=f[f[i][j-1]][j-1]; } } } void add(int x,int y){ g[cnt].to=y; g[cnt].nxt=head[x]; head[x]=cnt++; } int f[maxn][20]; int d[maxn]; int fid(int u,int le){ int y; for(int j=19;j>=0;j--){ y=f[u][j]; if(y!=0&&s[y].len>=le){ u=y; } } return u; } void dfs2(int u,int fa){ d[u]=d[fa]+1; la[u]=dx+1; if(pk[u]!=0){ dx++; num[dx]=pk[u]; } for(int i=head[u];i!=-1;i=g[i].nxt){ if(g[i].to!=fa){ dfs2(g[i].to,u); s[u].jg+=s[g[i].to].jg; } } ra[u]=dx; gg[s[u].jg].push_back(u); } int get_dx(){ return dx; } void ins(int x){ pk[crp]=x; st[x]=crp; } void sss(){ for(int i=n;i>=1;i--){ for(int j=0;j<gg[w[i].se].size();j++){ int y=gg[w[i].se][j]; while(y) { LL er=w[i].fi,flag=0; for(int j=60;j>=0;j--) { if(!(er>>j)) continue; if(!s[y].dd[j]) {s[y].dd[j]=er;flag=1;break;} er^=s[y].dd[j]; } if(!flag) break; ans[y]+=w[i].fi;y=s[y].par; } } } } }SAM; char ss[maxn]; int main(){ int t; scanf("%d",&t); int x,y,z; int ai; int gh; while(t--){ SAM.init(); scanf("%d",&n); scanf("%s",ss); for(int i=1;i<=n;i++){ scanf("%llu",&w[i].fi); w[i].se=i; } sort(w+1,w+1+n); for(int i=0;ss[i];i++){ SAM.ex_tend(ss[i]); } SAM.solve(); for(int i=0;ss[i];i++){ SAM.Transfer(i+1,ss[i]); SAM.ins(i+1); } SAM.dfs2(1,0); scanf("%d",&k); int g=SAM.get_dx(); SAM.sss(); while(k--){ scanf("%d%d",&x,&y); x=y-x+1; z=SAM.fid(st[y],x); printf("%llu ",ans[z]); } } }
http://acm.hdu.edu.cn/showproblem.php?pid=6694