bzoj 2434题回顾：阿狸与智能打字机的Noi2011挑战 - 结合AC自动机与树状数组解法

/************************************************************** Problem: 2434 User: walfy Language: C++ Result: Accepted Time:1120 ms Memory:171844 kb ****************************************************************/ //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double eps=1e-6; const int N=1000000+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; char s[N]; vector<int>trie[N],ftree[N]; vector<pair<int,int> >qu[N]; struct ACM{ int tot,root; int Next[N][26],id[N],fail[N],fa[N]; int newnode() { for(int i=0;i<26;i++)Next[tot][i]=-1; id[tot]=0; return tot++; } void init() { tot=0; root=newnode(); } void ins() { int now=root,n=strlen(s),co=0; for(int i=0;i<n;i++) { if('a'<=s[i]&&s[i]<='z') { if(Next[now][s[i]-'a']==-1) { Next[now][s[i]-'a']=newnode(); trie[now].pb(Next[now][s[i]-'a']); } fa[Next[now][s[i]-'a']]=now; now=Next[now][s[i]-'a']; } else if(s[i]=='P')id[++co]=now;//,printf("%d %d\n",co,now); else now=fa[now]; } } void build() { queue<int>q; fail[root]=root; for(int i=0;i<26;i++) { if(Next[root][i]==-1)Next[root][i]=root; else { fail[Next[root][i]]=root; ftree[root].pb(Next[root][i]); q.push(Next[root][i]); } } while(!q.empty()) { int now=q.front();q.pop(); for(int i=0;i<26;i++) { if(Next[now][i]==-1)Next[now][i]=Next[fail[now]][i]; else { fail[Next[now][i]]=Next[fail[now]][i]; ftree[Next[fail[now]][i]].pb(Next[now][i]); q.push(Next[now][i]); } } } } }ac; struct BIT{ int sum[N]; void add(int i,int v) { for(;i<N;i+=i&(-i))sum[i]+=v; } int query(int i) { int ans=0; for(;i;i-=i&(-i))ans+=sum[i]; return ans; } }b; int l[N],r[N],res=0,ans[N]; void dfsfail(int u) { // printf("%d \n",u); l[u]=++res; for(int i=0;i<ftree[u].size();i++) { int x=ftree[u][i]; dfsfail(x); } r[u]=res; } void dfstrie(int u) { // printf("%d\n",u); b.add(l[u],1); for(int i=0;i<qu[u].size();i++) { int x=qu[u][i].fi; ans[qu[u][i].se]=b.query(r[x])-b.query(l[x]-1); } for(int i=0;i<trie[u].size();i++) { int x=trie[u][i]; dfstrie(x); } b.add(l[u],-1); } int main() { scanf("%s",s); ac.init(); ac.ins(); ac.build(); // for(int i=0;i<ac.tot;i++) // { // for(int j=0;j<ftree[i].size();j++) // printf("%d ",ftree[i][j]); // printf("---%d\n",i); // } int m;scanf("%d",&m); for(int i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); x=ac.id[x],y=ac.id[y]; qu[y].pb(mp(x,i)); } dfsfail(ac.root); dfstrie(ac.root); for(int i=0;i<m;i++)printf("%d\n",ans[i]); return 0; } /******************** aPaPBbP 3 1 2 1 3 2 3 ********************/