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

interlinkage:

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

description:

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+;

const ll mo=1e9+;

int n,q,root,tim;

int t[N][],fa[N],id[N],dfn[N],size[N];

ll w[N],mul[N<<],sum[N];

inline ll read()

{

    char ch=getchar();ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void up1(int o)

{

    size[o]=size[t[o][]]+size[t[o][]]+;

    sum[o]=(sum[t[o][]]+sum[t[o][]]+w[o])%mo;

}

void dfs(int x)

{

    if (t[x][]) dfs(t[x][]);

    dfn[++tim]=x;id[x]=tim;

    if (t[x][]) dfs(t[x][]);

    up1(x);

}

void up2(int o)

{

    mul[o]=mul[o<<]*mul[o<<|]%mo;

}

void build(int o,int l,int r)

{

    if (l==r)

    {

        mul[o]=sum[dfn[l]];

        return;

    }

    int mid=l+r>>;

    build(o<<,l,mid);

    build(o<<|,mid+,r);

    up2(o);

}

void rotate(int x,int op)

{

    int y=fa[x],z=fa[y];

    if (z) t[z][t[z][]==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>>;

    if (pos<=mid) ins(o<<,l,mid,pos);

    else ins(o<<|,mid+,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>>;

    ll re=;

    if (x<=mid) re=re*query(o<<,l,mid,x,y)%mo;

    if (y>mid) re=re*query(o<<|,mid+,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=;i<=n;i++)

    {

        w[i]=read();t[i][]=read();t[i][]=read();

        if (t[i][]) fa[t[i][]]=i;

        if (t[i][]) fa[t[i][]]=i;

    }

    for (int i=;i<=n;i++) if (!fa[i]) root=i;

    dfs();

    build(,,tim);

    while (q--)

    {

        int op=read(),x=read();

        if (op<=)

        {

            if (t[x][op]) x=t[x][op];

            else continue;

            rotate(x,op);

            ins(,,tim,id[x]);

            if (t[x][!op]) ins(,,tim,id[t[x][!op]]);

        }

        if (op==)

        {

            printf("%lld\n",query(,,tim,id[x]-size[t[x][]],id[x]+size[t[x][]]));

        }

    }

    return ;

}