【HDU4942】Game on S♂play（线段树）（LCT）

传送门

其实发现一次旋转修改会对所有祖先产生乘上一个值的影响应该就很好直接上LCT了，但是乘 0 0 0再除 0 0 0就很麻烦。

发现这个树是一个二叉查找树，于是在旋转过程中这个树表示的序列并不会变，于是每个子树对应的就是原序列上的一个区间。

旋转的时候修改一下权值和，管辖子树范围， 查询的时候直接询问区间乘积即可。

代码（中序遍历+线段树）：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
    inline char get_char(){
        static cs int Rlen=1<<22|1;
        static char buf[Rlen],*p1,*p2;
        return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; 
    }
    
    template<typename T>
    inline T get(){
        char c;
        while(!isdigit(c=gc()));T num=c^48;
        while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
        return num;
    }
    inline int getint(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;

cs int mod=1e9+7;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}

cs int N=1e5+5;

int n,q;

int w[N],sum[N],lc[N],rc[N],f[N];
int nd[N],tot,pos[N];
int lb[N],rb[N];

void dfs(int u){
    if(lc[u])f[lc[u]]=u,dfs(lc[u]);
    nd[pos[u]=++tot]=u;
    lb[u]=lc[u]?lb[lc[u]]:tot;
    if(rc[u])f[rc[u]]=u,dfs(rc[u]);
    rb[u]=rc[u]?rb[rc[u]]:tot;
    sum[u]=add(w[u],add(sum[lc[u]],sum[rc[u]]));
}

namespace SGT{
    int mult[N<<2],M;
    inline void build(int n){
        for(M=1;M<=n+1;M<<=1);
        for(int re i=M+1;i<=M+n;i++){
            mult[i]=sum[nd[i-M]];
        }
        for(int re i=M-1;i;--i)mult[i]=mul(mult[i<<1],mult[i<<1|1]);
    }
    
    inline void modify(int p,int v){
        for(mult[p+=M]=v,p>>=1;p;p>>=1)mult[p]=mul(mult[p<<1],mult[p<<1|1]);
    }
    
    inline int query(int l,int r){
        int ans=1;//cerr<<"l : "<<l<<" r : "<<r<<"\n";
        for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
            if(l&1^1)ans=mul(ans,mult[l^1]);
            if(r&1)  ans=mul(ans,mult[r^1]);
        }
        return ans;
    }
}

inline int query(int u){
    return SGT::query(lb[u],rb[u]);
}

inline void Zig(int u){
    if(!lc[u])return ;
    int y=lc[u],p=f[u];
    (rc[p]==u?rc[p]:lc[p])=y;
    f[y]=p,f[u]=y;if(rc[y])f[rc[y]]=u;
    lc[u]=rc[y],rc[y]=u;
    sum[y]=sum[u];
    sum[u]=add(w[u],add(sum[lc[u]],sum[rc[u]]));
    lb[u]=lc[u]?lb[lc[u]]:pos[u];
    rb[y]=rb[u];
    SGT::modify(pos[u],sum[u]);
    SGT::modify(pos[y],sum[y]);
}

inline void Zag(int u){
    if(!rc[u])return ;
    int y=rc[u],p=f[u];
    (rc[p]==u?rc[p]:lc[p])=y;
    f[y]=p,f[u]=y;if(lc[y])f[lc[y]]=u;
    rc[u]=lc[y],lc[y]=u;
    sum[y]=sum[u];
    sum[u]=add(w[u],add(sum[lc[u]],sum[rc[u]]));
    rb[u]=rc[u]?rb[rc[u]]:pos[u];
    lb[y]=lb[u];
    SGT::modify(pos[u],sum[u]);
    SGT::modify(pos[y],sum[y]);
}

inline void solve(){
    n=getint(),q=getint();
    for(int re i=1;i<=n;++i){
        w[i]=getint(),lc[i]=getint(),rc[i]=getint();
    }
    tot=0;dfs(1);SGT::build(n);f[1]=n+1;lc[n+1]=1;
    while(q--){
        switch(getint()){
            case 0:Zig(getint());break;
            case 1:Zag(getint());break;
            case 2:cout<<query(getint())<<"\n";break;
        }
    }
}

signed main(){
#ifdef zxyoi
    freopen("splay.in","r",stdin);
#endif
    int T=getint();
    for(int re i=1;i<=T;++i)cout<<"Case #"<<i<<":\n",solve();
    return 0;
} 
           

代码（LCT）：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<22|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	template<typename T>
	inline T get(){
		char c;
		while(!isdigit(c=gc()));T num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline int getint(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;

cs int N=2e5+5;
cs int mod=1e9+7;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline int power(int a,int b,int res=1){if(a<=1)return a;
	for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));
	return res;
}

int n,q;

int w[N],sum[N],ans[N];
int lc[N],rc[N],f[N];

namespace LCT{
	int fa[N];
	int son[N][2];
	int tag[N];
	
	inline bool isroot(int u){return son[fa[u]][0]!=u&&son[fa[u]][1]!=u;}
	inline bool which(int u){return son[fa[u]][1]==u;}
	
	inline void Rotate(int u){
		int p=fa[u],pp=fa[p];
		bool d=which(u);
		if(!isroot(p))son[pp][which(p)]=u;
		son[p][d]=son[u][!d];
		if(son[p][d])fa[son[p][d]]=p;
		son[u][!d]=p;
		fa[u]=pp,fa[p]=u;
	}
	
	inline void pushnow(int u,int v){
		tag[u]=mul(tag[u],v);
		ans[u]=mul(ans[u],v);
	}
	
	inline void pushdown(int u){
		if(tag[u]!=1){
			if(son[u][0])pushnow(son[u][0],tag[u]);
			if(son[u][1])pushnow(son[u][1],tag[u]);
			tag[u]=1;
		}
	}
	
	inline void Splay(int u){
		static int q[N],qn;
		q[qn=1]=u;
		for(int re p=u;!isroot(p);p=fa[p])q[++qn]=fa[p];
		while(qn)pushdown(q[qn--]);
		for(int re p=fa[u];!isroot(u);Rotate(u),p=fa[u])
		if(!isroot(p))Rotate(which(u)==which(p)?p:u);
	}
	
	inline void access(int u){
		for(int re ch=0;u;ch=u,u=fa[u])
		Splay(u),son[u][1]=ch;
	}
	
	inline void link(int u,int f){
		access(u),Splay(u),fa[u]=f;
	}
	
	inline void cut(int u,int f){
		access(f);
		Splay(u);
		fa[u]=0;
	}
	
	inline void pushtag(int u,int _v){
		access(u);Splay(u);
		pushnow(u,_v);
	}
	
	inline void init(int n){
		sum[0]=0,ans[0]=1,tag[0]=1;
		sum[n+1]=0,w[n+1]=1,ans[n+1]=1,tag[n+1]=1;
		for(int re i=1;i<=n;++i){
			w[i]=getint();
			lc[i]=getint(),rc[i]=getint();
			if(lc[i])f[lc[i]]=fa[lc[i]]=i;
			if(rc[i])f[rc[i]]=fa[rc[i]]=i;
			tag[i]=1;
		}
		f[1]=fa[1]=n+1;lc[n+1]=1;
		for(int re i=n;i;--i){
			sum[i]=add(w[i],add(sum[lc[i]],sum[rc[i]]));
			ans[i]=mul(sum[i],mul(ans[lc[i]],ans[rc[i]]));
		}
		sum[n+1]=add(w[n+1],add(sum[lc[n+1]],sum[rc[n+1]]));
		ans[n+1]=mul(sum[n+1],mul(ans[lc[n+1]],ans[rc[n+1]]));
	}
}

inline int query(int u){
	if(!u)return 1;
	LCT::access(u);
	LCT::Splay(u);
	return ans[u]; 
}

inline void Zig(int u){
	if(!lc[u])return ;
	int y=lc[u],p=f[u];
	query(u),query(y);
	int val=power(sum[y],mod-2);
	LCT::cut(u,p);LCT::cut(y,u);
	if(rc[y])LCT::cut(rc[y],y),LCT::link(rc[y],u);
	LCT::link(u,y);LCT::link(y,p);
	(rc[p]==u?rc[p]:lc[p])=y;
	f[y]=p,f[u]=y;if(rc[y])f[rc[y]]=u;
	lc[u]=rc[y],rc[y]=u;
	sum[y]=sum[u];
	sum[u]=add(w[u],add(sum[lc[u]],sum[rc[u]]));
	val=mul(val,sum[u]);
	LCT::pushtag(p,val);
	ans[u]=mul(sum[u],mul(query(lc[u]),query(rc[u])));
	ans[y]=mul(sum[y],mul(query(lc[y]),query(rc[y])));
}

inline void Zag(int u){
	if(!rc[u])return ;
	int y=rc[u],p=f[u];
	query(u),query(y);
	int val=power(sum[y],mod-2);
	LCT::cut(u,p);LCT::cut(y,u);
	if(lc[y])LCT::cut(lc[y],y),LCT::link(lc[y],u);
	LCT::link(u,y);LCT::link(y,p);
	(rc[p]==u?rc[p]:lc[p])=y;
	f[y]=p,f[u]=y;if(lc[y])f[lc[y]]=u;
	rc[u]=lc[y],lc[y]=u;
	sum[y]=sum[u];
	sum[u]=add(w[u],add(sum[lc[u]],sum[rc[u]]));
	val=mul(val,sum[u]);
	LCT::pushtag(p,val);
	ans[u]=mul(sum[u],mul(query(lc[u]),query(rc[u])));
	ans[y]=mul(sum[y],mul(query(lc[y]),query(rc[y])));
}

int qcnt;
signed main(){
	n=getint(),q=getint();
	LCT::init(n);
	while(q--){
		switch(getint()){
			case 0:Zig(getint());break;
			case 1:Zag(getint());break;
			case 2:cout<<query(getint())<<"\n";++qcnt;
		}
	}
	return 0;
}