首页 > 代码库 > BZOJ3467 : Crash和陶陶的游戏
BZOJ3467 : Crash和陶陶的游戏
首先离线建出两棵树，对树$B$中每个点预处理出其往上$2^k$步的父亲以及中间的串的Hash值。
通过这个可以在$O(\log n)$的时间内比较两个串的字典序，以此将它们按字典序排序。
然后将树$A$压缩成Trie，并求出根到每个点的Hash值，同时预处理出每个串在$B$数组中出现的区间。
具体的求法是：$x$的区间一定是$x$的父亲的区间的子区间，在内部二分找到区间的左右端点即可。
然后按顺序依次模拟每个操作：
$1.$如果是往树$A$中添加节点$x$，那么对答案的贡献是$B$数组中对应区间内已加入的点数。
$2.$如果是往树$B$中添加节点$x$，那么可以倍增枚举在Trie中最长可以走多远，根据Hash值可以很方便地进行定位，对答案的贡献是某个点到根节点路径上已经加入的点数。
这都可以通过树状数组维护。
时间复杂度$O(n\log^2n)$。
#include<cstdio>#include<algorithm>typedef unsigned long long ll;const int N=100010,K=16,D=233;int n,i,x,y,op[N][2];char ch;ll ans=1;int c0=1,cnt=1,id[N],p[N],w[N],dep[N],g[N][26],st[N],en[N],q[N],in[N],ou[N],dfn;ll v[N];int c1=1,s[N],rk[N],f[N][K+1];ll h[N][K+1],pw[K+1];struct BIT{ int n,b[N<<1]; void add(int x,int p){for(;x<=n;x+=x&-x)b[x]+=p;} int ask(int x){int t=0;for(;x;x-=x&-x)t+=b[x];return t;}}b0,b1;inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline int add0(int x,int y){ if(!g[x][y]){ g[x][y]=++c0; p[c0]=x; w[c0]=y+1; dep[c0]=dep[x]+1; v[c0]=v[x]*D+y+1; } return id[++cnt]=g[x][y];}inline int add1(int x,int y){ int z=++c1; f[z][0]=x; h[z][0]=y+1; for(int i=1;i<=K;i++){ f[z][i]=f[f[z][i-1]][i-1]; h[z][i]=h[z][i-1]*pw[i-1]+h[f[z][i-1]][i-1]; } return z;}inline bool cmpq(int x,int y){return v[x]<v[y];}inline bool cmps(int x,int y){ for(int i=K;~i;i--)if(h[x][i]==h[y][i])x=f[x][i],y=f[y][i]; return h[x][0]<h[y][0];}inline int kth(int x,int k){ k--; for(int i=K;~i;i--)if(k>>i&1)k-=1<<i,x=f[x][i]; return h[x][0];}inline void cal(int x){ int A=st[p[x]],B=en[p[x]],L=B+1,R=A-1; int d=dep[x],c=w[x],l=A,r=B,mid; while(l<=r)if(kth(s[mid=(l+r)>>1],d)>=c)r=(L=mid)-1;else l=mid+1; l=A,r=B; while(l<=r)if(kth(s[mid=(l+r)>>1],d)<=c)l=(R=mid)+1;else r=mid-1; st[x]=L,en[x]=R;}inline int getid(ll x){ int l=1,r=c0,mid; while(l<=r){ if(v[q[mid=(l+r)>>1]]==x)return q[mid]; if(v[q[mid]]<x)l=mid+1;else r=mid-1; } return 0;}void dfs(int x){ in[x]=++dfn; for(int i=0;i<26;i++)if(g[x][i])dfs(g[x][i]); ou[x]=++dfn;}inline void ext0(int x){ b0.add(in[x],1); b0.add(ou[x],-1); if(st[x]>en[x])return; ans+=b1.ask(en[x])-b1.ask(st[x]-1);}inline void ext1(int x){ b1.add(rk[x],1); int o=1,t;ll pre=0,now; for(int i=K;~i;i--)if(t=getid(now=pre*pw[i]+h[x][i]))o=t,pre=now,x=f[x][i]; ans+=b0.ask(in[o]);}int main(){ read(n); for(pw[0]=D,i=1;i<=K;i++)pw[i]=pw[i-1]*pw[i-1]; for(id[1]=i=1;i<=n;i++){ read(x),read(y);op[i][0]=--x; while(!((ch=getchar())>=‘a‘&&ch<=‘z‘)); ch-=‘a‘; op[i][1]=x?add1(y,ch):add0(id[y],ch); } for(i=1;i<=c0;i++)q[i]=i; std::sort(q+1,q+c0+1,cmpq); for(i=1;i<=c1;i++)s[i]=i; std::sort(s+1,s+c1+1,cmps); for(i=1;i<=c1;i++)rk[s[i]]=i; st[1]=1,en[1]=c1; for(i=2;i<=c0;i++)cal(i); dfs(1); b0.n=c0*2; b1.n=c1; b0.add(1,1); b1.add(1,1); for(i=1;i<=n;i++){ op[i][0]?ext1(op[i][1]):ext0(op[i][1]); printf("%llu\n",ans); } return 0;}
BZOJ3467 : Crash和陶陶的游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。