首页 > 代码库 > bzoj3786 星际探索 splay dfs序
bzoj3786 星际探索 splay dfs序
这道题 首先 因为他求的是当前点到根节点的路径和 我们可以将题目转换为括号序列的写法 将点拆为左括号以及右括号 左括号为正 右括号为负 这样题目就变为了求前缀和了 如果一个点是这个点的子树 那么他的左右括号就一定包含在所求区间里 会被抵消掉而不影响结果。 这样我们可以利用dfs序建树 操作为区间加 单点修改 树的合并以及分裂 一起区间和 当然区间加因为我们维护的是括号序列 所以区间加的时候我们就要将左括号加w而右括号减w 但是我们因此我们还要记录这个点子树及其本身的左右括号差 区间加就加上左括号数减右括号数的差 乘以w就可以了 当然还要维护这两个括号本身的信息 毕竟这是一个闭区间 区间的分裂和合并的话 （左括号为x 右括号为y） 将x旋到root 切开他的左子树 左子树根为p1 将y旋到root 切开他的右子树 右子树跟为p3 xy所在的树跟为p3 然后将p1和p3合并 合并的话将p1的树上最右下方的点旋到p1 这样他就不存在右子树 强制将p3连到右子树 然后将新的依赖关系的点k旋到p1 切开右子树 强制讲p2连到右子树 然后按前面的方法把剩下的两棵树连在一起 就okay了 说起来难其实就三个函数的事情 不超过二十行 看代码比较好理解呐 剩下的加油咯
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=600555; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } long long tag[M],v[M],ans[M]; int tot,n,m,root,d[M],q[M],fa[M],pd[M]; int first[M],sum,c[M][2]; struct node{int to,next,w;}e[M]; void insert(int a,int b){sum++; e[sum].to=b; e[sum].next=first[a]; first[a]=sum;} void add(int z,long long w){ if(!z) return ; tag[z]+=w; v[z]+=w*pd[z]; ans[z]+=w*d[z]; } void qadd(int z,int w){ if(!z) return ; v[z]+=w*pd[z]; ans[z]+=w*pd[z]; } void up(int k){ int l=c[k][0],r=c[k][1]; d[k]=pd[k]+d[l]+d[r]; ans[k]=ans[l]+ans[r]+v[k]; } void down(int k){ if(tag[k]){ add(c[k][0],k[tag]); add(c[k][1],k[tag]); tag[k]=0; } } void rotate(int x,int& k){ int y=fa[x],z=fa[y],l=0,r=1; if(c[y][1]==x) l=1,r=0; if(y==k) k=x; else{if(c[z][0]==y) c[z][0]=x; else c[z][1]=x;} fa[y]=x; fa[x]=z; fa[c[x][r]]=y; c[y][l]=c[x][r]; c[x][r]=y; up(y); up(x); } int stk[M],stp=0; void sp(int x,int& k){ for(int w=x;w;w=w[fa])stk[stp++]=w; while(stp)down(stk[--stp]); while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if(c[z][0]==y^c[y][0]==x) rotate(y,k); else rotate(x,k); } rotate(x,k); } } void dfs(int k){ q[++tot]=k; for(int i=first[k];i;i=e[i].next) dfs(e[i].to); q[++tot]=k+n; } int build(int l,int r){ if(l>r) return 0; int m=(l+r)>>1,now=q[m]; c[now][0]=build(l,m-1); c[now][1]=build(m+1,r); for(int i=0;i<2;i++) if(c[now][i]) fa[c[now][i]]=now; up(now); return now; } int find(int k){ while(c[k][1]) k=c[k][1]; return k; } void cut_l(int x,int rt,int& r1,int& r2){ sp(x,rt); r1=c[x][0]; r2=x; c[r2][0]=fa[r1]=0; up(x); } void cut_r(int x,int rt,int& r1,int& r2){ sp(x,rt); r1=x; r2=c[x][1]; c[r1][1]=fa[r2]=0; up(x); } int mg(int r1,int r2){ int w=find(r1); sp(w,r1); c[w][1]=r2;fa[r2]=w; up(w); return w; } void papa(int x,int f){ int y=x+n,p1,p2,p3; cut_l(x,root,p1,p2); cut_r(y,p2,p2,p3); cut_r(f,mg(p1,p3),p1,p3); root=mg(mg(p1,p2),p3); } int main() { int k,w; char ch[10]; n=read(); for(int i=2;i<=n;i++) k=read(),insert(k+1,i+1); for(int i=2;i<=n+1;i++) w=read(),v[i]=w,v[i+n]=-w,pd[i]=1,pd[i+n]=-1; q[++tot]=1; dfs(2); q[++tot]=2*n+2; root=build(1,2*n+2); m=read(); while(m--){ scanf("%s",ch); if(ch[0]==‘Q‘){k=read()+1; sp(k,root); printf("%lld\n",ans[c[k][0]]+v[k]);} if(ch[0]==‘C‘){ int x=read()+1,y=read()+1; papa(x,y);} if(ch[0]==‘F‘){ k=read()+1; w=read(); int y=k+n,z; sp(k,root); sp(y,c[root][1]); z=c[y][0]; qadd(k,w); qadd(y,w); add(z,w); up(y); up(k); } } return 0; }
bzoj3786 星际探索 splay dfs序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。