[jzoj 5662] 尺树寸泓解题报告 (线段树+中序遍历)

佚名 7年前 (2019-04-08) 随笔 1466人围观抢沙发百度已收录

interlinkage:

https://jzoj.net/senior/#contest/show/2703/1

description:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

solution:

发现$dfs$序不好维护
注意到这是一棵平衡树，左旋右旋中序遍历不会改变，且一个点的子树在中序遍历上也是一个连续的区间
每次旋转只改变两个点的力量值
在中序遍历上建线段树维护单点修改,区间乘积查询就好

code:

#include<algorithm> #include<cstring> #include<iostream> #include<cstdio> #include<cmath> #include<queue>
using namespace std; typedef long long ll; const int N=2e5+15; const ll mo=1e9+7; int n,q,root,tim; int t[N][2],fa[N],id[N],dfn[N],size[N]; ll w[N],mul[N<<2],sum[N]; inline ll read() { char ch=getchar();ll s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void up1(int o) { size[o]=size[t[o][0]]+size[t[o][1]]+1; sum[o]=(sum[t[o][0]]+sum[t[o][1]]+w[o])%mo; } void dfs(int x) { if (t[x][0]) dfs(t[x][0]); dfn[++tim]=x;id[x]=tim; if (t[x][1]) dfs(t[x][1]); up1(x); } void up2(int o) { mul[o]=mul[o<<1]*mul[o<<1|1]%mo; } void build(int o,int l,int r) { if (l==r) { mul[o]=sum[dfn[l]]; return; } int mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); up2(o); } void rotate(int x,int op) { int y=fa[x],z=fa[y]; if (z) t[z][t[z][1]==y]=x; fa[x]=z; t[y][op]=t[x][!op];fa[t[x][!op]]=y; t[x][!op]=y;fa[y]=x; up1(y);up1(x); } void ins(int o,int l,int r,int pos) { if (l==r) { mul[o]=sum[dfn[pos]]; return; } int mid=l+r>>1; if (pos<=mid) ins(o<<1,l,mid,pos); else ins(o<<1|1,mid+1,r,pos); up2(o); } ll query(int o,int l,int r,int x,int y) { if (l>=x&&r<=y) return mul[o]; int mid=l+r>>1; ll re=1; if (x<=mid) re=re*query(o<<1,l,mid,x,y)%mo; if (y>mid) re=re*query(o<<1|1,mid+1,r,x,y)%mo; return re; } int main() { freopen("splay.in","r",stdin); freopen("splay.out","w",stdout); n=read();q=read(); for (int i=1;i<=n;i++) { w[i]=read();t[i][0]=read();t[i][1]=read(); if (t[i][0]) fa[t[i][0]]=i; if (t[i][1]) fa[t[i][1]]=i; } for (int i=1;i<=n;i++) if (!fa[i]) root=i; dfs(1); build(1,1,tim); while (q--) { int op=read(),x=read(); if (op<=1) { if (t[x][op]) x=t[x][op]; else continue; rotate(x,op); ins(1,1,tim,id[x]); if (t[x][!op]) ins(1,1,tim,id[t[x][!op]]); } if (op==2) { printf("%lld\n",query(1,1,tim,id[x]-size[t[x][0]],id[x]+size[t[x][1]])); } } return 0; }