首页 > 代码库 > BZOJ 3881: [Coci2015]Divljak
BZOJ 3881: [Coci2015]Divljak
Description
有两个集合\(ST\),\(S\)集合已知。
有两个操作
添加一个字符串到\(T\)
询问T中有多少\(S_i\)
\(n,q\leqslant 10^5,len(|S|),len(|T|)\leqslant 2\times 10^5\)
Solution
Trie树+DFS序.
添加一个字符串就要把Trie树上经过的节点及其fail树上的祖先+1
将他差分一下,每次询问出现次数就变成了询问子树和。
然后就是几条树梿的+1操作,因为差分过了,所以每个节点+1,相邻LCA-1
Code
/************************************************************** Problem: 3881 User: BeiYu Language: C++ Result: Accepted Time:16216 ms Memory:514652 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 2000050;const int M = 26; namespace Bit { int d[N],n; void init(int x) { n=x; } void Add(int x,int v) { for(;x<=n;x+=x&-x) d[x]+=v; } int Qur(int x,int r=0) { for(;x;x-=x&-x) r+=d[x];return r; }} namespace Tree { vector<int> g[N]; int cnt; int b[N],f[N][M],d[N],t1[N],t2[N]; void AddEdge(int u,int v) { g[u].push_back(v),g[v].push_back(u); } void DFS(int rt) { stack<int> stk; stk.push(rt),f[rt][0]=rt,d[rt]=1; for(int x;!stk.empty();) { x=stk.top(); if(b[x]) { t2[x]=cnt,stk.pop();continue; } b[x]=1,t1[x]=++cnt; for(int i=0,v;i<(int)g[x].size();i++) if((v=g[x][i])!=f[x][0]) f[v][0]=x,d[v]=d[x]+1,stk.push(v); } } void init() { for(int j=1;j<M;j++) for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; } int LCA(int u,int v) { if(d[u]<d[v]) swap(u,v); int l=d[u]-d[v]; if(l) for(int i=M-1;~i;i--) if(l&(1<<i)) u=f[u][i]; if(u==v) return u; for(int i=M-1;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; }}; namespace AC { int cnt,rt; int f[N],ch[N][M],ed[N]; void init() { rt=cnt=0; } void insert(char* s,int id) { int l=strlen(s),x=rt; for(int i=0;i<l;i++) { int v=s[i]-‘a‘; if(!ch[x][v]) ch[x][v]=++cnt; x=ch[x][v]; }ed[id]=x; } void Build() { queue<int> q; f[rt]=rt; for(int i=0;i<M;i++) if(ch[rt][i]) q.push(ch[rt][i]),f[ch[rt][i]]=rt; for(int x;!q.empty();) { x=q.front(),q.pop(); for(int i=0;i<M;i++) { if(!ch[x][i]) { ch[x][i]=ch[f[x]][i];continue; } int v=ch[x][i]; f[v]=ch[f[x]][i],q.push(v); } } } void get_f() { for(int i=1;i<=cnt;i++) Tree::AddEdge(i,f[i]); Tree::DFS(0); Tree::init(); // for(int i=1;i<=cnt;i++) cout<<i<<" "<<f[i]<<endl;// for(int i=1;i<=cnt;i++) cout<<Tree::d[i]<<" ";cout<<endl;// for(int i=1;i<=cnt;i++) cout<<Tree::t1[i]<<" ";cout<<endl;// for(int i=1;i<=cnt;i++) cout<<Tree::t2[i]<<" ";cout<<endl; }}; int cmp(int x,int y) { return Tree::t1[x]<Tree::t1[y]; }vector<int> a;void add_str(char* s) { int l=strlen(s),x=AC::rt; a.clear(); for(int i=0;i<l;i++) { int v=s[i]-‘a‘; x=AC::ch[x][v]; a.push_back(x); } sort(a.begin(),a.end(),cmp); x=a.size();// for(int i=0;i<x;i++) cout<<a[i]<<" ";cout<<endl; Bit::Add(Tree::t1[a[0]],1); for(int i=1;i<x;i++) { Bit::Add(Tree::t1[Tree::LCA(a[i],a[i-1])],-1); Bit::Add(Tree::t1[a[i]],1); }} int n,q;char s[N]; int main() {// freopen("in.in","r",stdin); scanf("%d",&n); AC::init(); for(int i=1;i<=n;i++) { scanf("%s",s); AC::insert(s,i); } AC::Build(); AC::get_f(); Bit::init(AC::cnt+1);// int oo,ooo;// while(cin>>oo>>ooo) cout<<Tree::LCA(oo,ooo)<<endl; scanf("%d",&q); for(int opt,x;q--;) { scanf("%d",&opt); if(opt==1) { scanf("%s",s); add_str(s); } else { scanf("%d",&x); printf("%d\n",Bit::Qur(Tree::t2[AC::ed[x]])-Bit::Qur(Tree::t1[AC::ed[x]]-1)); } }return 0;}
BZOJ 3881: [Coci2015]Divljak
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。