jzoj 5662. 【GDOI2018Day1模拟4.17】尺树寸泓

题目大意：

思路：

平衡树很简单了，学过的大概多知道，推一推会发现，他的sum是和只有旋转点会变，mul所有的父亲都会变，在多次旋转后可能为一条链，那么时间复杂度就会爆炸。
这时我们可以先求出中序遍历，那么平衡树的点在中序遍历中的相对位置不会变。子树也在包含他的连续区间里面。这样就只用维护每个点的sum值，然后区间乘法求出mul的值。

程序：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define mo 1000000007
#define N 2000005
#define LL long long
using namespace std;
struct data{int l,r;}son[N];
LL f[N],sum[N],a[N],fa[N],size[N],b[N],c[N];
int n,q,opt,x,s;
LL ans;
struct tree{int l,r; LL mul;}t[N*4];
int dfs(int x){
    size[x]=1;
    if (son[x].l) dfs(son[x].l);
    b[++s]=x;
    c[x]=s;
    if (son[x].r) dfs(son[x].r);
    sum[x]=(sum[son[x].l]+sum[son[x].r]+a[x])%mo;
    f[x]=((f[son[x].l]*f[son[x].r])%mo*sum[x])%mo;
    size[x]+=size[son[x].l]+size[son[x].r];
}

void ins(int rt,int l,int r){
    t[rt].l=l; t[rt].r=r;
    if (l==r){
        t[rt].mul=sum[b[l]];
        return;
    }
    int mid=(l+r)/2;
    ins(rt*2,l,mid);
    ins(rt*2+1,mid+1,r);
    t[rt].mul=(t[rt*2].mul*t[rt*2+1].mul)%mo;
}

void change(int rt,int l,int r,int x,int y){
    if (l==r){
        t[rt].mul=y;
        return;
    }
    int mid=(l+r)/2;
    if (mid>=x) change(rt*2,l,mid,x,y);
            else change(rt*2+1,mid+1,r,x,y);
    t[rt].mul=(t[rt*2].mul*t[rt*2+1].mul)%mo;   
}

void mul(int rt, int l,int r,int x,int y){
    if (l==x&&r==y) {
        ans*=t[rt].mul;
        ans=ans%mo; 
        return;
    };
    int mid=(l+r)/2;
    if (y<=mid)  mul(rt*2,l,mid,x,y);
    else if (x>mid)  mul(rt*2+1,mid+1,r,x,y);
    else  mul(rt*2,l,mid,x,mid),mul(rt*2+1,mid+1,r,mid+1,y);;
}

int rrotate(int x){
    int y=son[x].l;
    if (son[fa[x]].l==x) son[fa[x]].l=y;
                    else son[fa[x]].r=y;
    int u=size[y];
    size[y]=size[x];
    size[x]=size[x]-u+size[son[y].r];
    fa[son[y].r]=x;
    fa[y]=fa[x];
    fa[x]=y;
    son[x].l=son[y].r;
    son[y].r=x;
    sum[x]=(sum[son[x].l]+sum[son[x].r]+a[x])%mo;
    change(1,1,n,c[x],sum[x]);
    sum[y]=(sum[son[y].l]+sum[son[y].r]+a[y])%mo;
    change(1,1,n,c[y],sum[y]);
}

int lrotate(int x){
    int y=son[x].r;
    if (son[fa[x]].l==x) son[fa[x]].l=y;
                    else son[fa[x]].r=y;
    int u=size[y];
    size[y]=size[x];
    size[x]=size[x]-u+size[son[y].l];
    fa[son[y].l]=x;
    fa[y]=fa[x];
    fa[x]=y;
    son[x].r=son[y].l;
    son[y].l=x;
    sum[x]=(sum[son[x].l]+sum[son[x].r]+a[x])%mo;
    change(1,1,n,c[x],sum[x]);
    sum[y]=(sum[son[y].l]+sum[son[y].r]+a[y])%mo;
    change(1,1,n,c[y],sum[y]);
}



int main(){
    freopen("splay.in","r",stdin);
    freopen("splay.out","w",stdout);
    scanf("%d%d",&n,&q);
    f[0]=1;
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i],&son[i].l,&son[i].r);
        f[i]=1;
        fa[son[i].l]=i;
        fa[son[i].r]=i;
    }
    for (int i=0;i<N;i++)
     t[i].mul=1;
    dfs(1);
    ins(1,1,n);
    for (int i=1;i<=q;i++){
        scanf("%d%d",&opt,&x);
        if (opt==0) if (son[x].l) rrotate(x);
        if (opt==1) if (son[x].r) lrotate(x);
        if (opt==2) {
            ans=1;
            mul(1,1,n,c[x]-size[son[x].l],c[x]+size[son[x].r]);
            printf("%lld\n",ans);
        }
    }
}