LCT

cwy posted @ 2018年1月11日 19:44 in 板子 , 46 阅读

BZOJ2157

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
struct node{
	int ch[2],fa,v,mx,mn,s;
	int tgx,tgy;
	bool rev;
	node(){tgx=1;}
}t[200010];
int n,m,stk[200010],top,x,y,w;
char s[666];
bool isroot(int x){
	return (t[t[x].fa].ch[0]!=x && t[t[x].fa].ch[1]!=x);
}
void pushup(int x){
	t[x].s=0;
	t[x].mx=-INF;
	t[x].mn=INF;
	if (x>n){
		t[x].s=t[x].v;
		t[x].mx=max(t[x].mx,t[x].v);
		t[x].mn=min(t[x].mn,t[x].v);
	}
	FOR(i,0,1)
		if (t[x].ch[i]){
			t[x].mx=max(t[t[x].ch[i]].mx,t[x].mx);
			t[x].mn=min(t[t[x].ch[i]].mn,t[x].mn);
			t[x].s+=t[t[x].ch[i]].s;
		}
}
void TAG(int x,int p,int q){
	t[x].v=t[x].v*p+q;
	t[x].s=t[x].s*p+q;
	if (t[x].mx>=t[x].mn){
		t[x].mx=t[x].mx*p+q;
		t[x].mn=t[x].mn*p+q;
		if (t[x].mx<t[x].mn) swap(t[x].mx,t[x].mn);
	}
	//(*x+y)*p+q
	t[x].tgx*=p;
	t[x].tgy=t[x].tgy*p+q;
}
void REV(int x){
	swap(t[x].ch[0],t[x].ch[1]);
	t[x].rev^=1;
}
void pushdown(int x){
	if (t[x].rev){
		if (t[x].ch[0]) REV(t[x].ch[0]);
		if (t[x].ch[1]) REV(t[x].ch[1]);
		t[x].rev=0;
	}
	if (t[x].tgx!=1 || t[x].tgy!=0){
		if (t[x].ch[0]) TAG(t[x].ch[0],t[x].tgx,t[x].tgy);
		if (t[x].ch[1]) TAG(t[x].ch[1],t[x].tgx,t[x].tgy);
		t[x].tgx=1,t[x].tgy=0;
	}
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (!isroot(fa)) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x){
	stk[top=1]=x;
	int y=x;
	while (!isroot(y)) stk[++top]=t[y].fa,y=t[y].fa;
	FORD(rp,top,1) pushdown(stk[rp]);
	while (!isroot(x)){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (!isroot(fa))
			(x==t[fa].ch[0]^fa==t[gfa].ch[0])?rot(x):rot(fa);
		rot(x);
	}
}
void access(int x){
	int te=0;
	while (x){
		splay(x);
		t[x].ch[1]=te;
		pushup(x);
		te=x;
		x=t[x].fa;
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	REV(x);
}
void link(int x,int y){
	makeroot(x);
	t[x].fa=y;
}

int main(){
	scanf("%d",&n);
	m=n;
	FOR(i,1,n-1){
		getint(x),getint(y),getint(w);
		++x,++y;
		t[++m].v=w;
		t[m].mx=t[m].mn=t[m].s=w;
		link(m,x),link(m,y);
	}
	scanf("%d",&m);
	while (m--){
		scanf("%s",s);
		if (s[0]=='C'){
			getint(x),getint(y);
			x+=n;
			makeroot(x);
			access(x);
			splay(x);
			TAG(x,1,y-t[x].v);
		}
		else if (s[0]=='N'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			TAG(y,-1,0);
		}
		else if (s[0]=='S'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].s);
		}
		else if (s[1]=='A'){
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].mx);
		}
		else{
			getint(x),getint(y);
			++x,++y;
			makeroot(x);
			access(y);
			splay(y);
			printf("%d\n",t[y].mn);
		}
	}
	return 0;
}

http://codeforces.com/contest/763/submission/34110258

带平衡树代码容易写错的一个地方:写t[xx].yy的时候可能中途旋转了,所以要开个临时变量记下。

http://codeforces.com/contest/603/submission/34171363

维护树的size的时候,要记w,sz分别表示LCT中子树的非重儿子size、总size。

然后在cut,link,access的时候要多写几句话。

注意link,为了使得x接到y上去的时候y的祖先不需要pushup,所以要让y没有父亲,即access(y),splay(y)

Avatar_small
cwy 说:
2018年1月12日 13:46

Wow! You can code a LCT under 10min! It will be certain that you can receive an IOI Gold Medal!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter