bzoj 2243:[SDOI 2011]染色

2243:[SDOI 2011]染色
Time Limit: 20 Sec  
Memory Limit: 512 MB
Submit: 3271  
Solved: 1262
[ Submit][ Status][ Discuss]
Description
n個のノードを持つルートなしツリーとm個の操作が与えられ、操作は2種類ある.
1、ノードaからノードbへの経路上のすべての点を色cに染める.
2、問い合わせノードaからノードbへの経路上の色セグメントの数(連続して同じ色が同じセグメントとみなされる)は、例えば「112212」が3セグメントからなる:「11」、「222」、「1」である.
このm操作を順番に完了するプログラムを書いてください.
Input
第1行は2つの整数nとmを含み、それぞれノード数と操作数を表す.
2行目はn個の正の整数でn個のノードの初期色を表す
次の行には、xとyの間に無方向のエッジがあることを示す2つの整数xとyが含まれています.
次の行は、行ごとに1つのアクションを示します.
「C a b c」は、ノードaからノードbへの経路上のすべての点(aおよびbを含む)を色cに染める染色動作であることを示す.
「Q a b」は、ノードaからノードb(aおよびbを含む)への経路上の色セグメントの数を問い合わせる問合せ動作であることを示す.
Output
各質問操作について、1行の答えを出力します.
Sample Input
6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5
Sample Output
3 1 2
HINT
数N<=10^5、オペランドM<=10^5、すべての色Cは整数で[0,10^9]の間にある.
Source
第1ラウンドday 1
考え方:この问题のメンテナンスは比较的に复雑で、LCTと木のチェーンの分割はすべて书くことができて、木のチェーンの分割はやはり少し书きやすいです.
ツリーチェーン分割を書くと、線分ツリーに左右の端点の色、色の個数、上書きマークが記録され、updateではドッキング先の2点の色が同じかどうかを判断し、同じ色の数は左半分+右半分-1に等しい.木の鎖の分割統計の解答の時も同様で、左右の端点の色を記録して、同じで1を減らします.
LCTを書くと、splayで記録されているものと木の鎖の断面の差は多くありませんが、updateでは2回、上半分と自分と下半分をマージします.マークも2種類あります.1つは1つの点をルートにする反転で、1つはカバーです.
long long...
ツリー分割コード:

#include
#include
#include
#define ll long long
#define ls p<<1
#define rs ((p<<1)|1)
using namespace std;
const ll maxm=200010,maxn=100010,maxt=maxn<<3;
ll n,m,pre[maxm],now[maxn],son[maxm],col[maxn],tot,root;
ll fa[maxn],hson[maxn],w[maxn],top[maxn],dep[maxn],size[maxn],T,q,a[maxn];
char s[10];
void add(ll a,ll b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
struct node{ll lcol,rcol,val,cov;};
struct Tree{
	node t[maxt];
	void update(ll p){
		t[p].lcol=t[ls].lcol;
		t[p].rcol=t[rs].rcol;
		t[p].val=t[ls].val+t[rs].val-(t[ls].rcol==t[rs].lcol);
	}
	void down(ll p){
		if (t[p].cov){
			t[ls].cov=t[rs].cov=t[p].cov;
			t[ls].lcol=t[ls].rcol=t[rs].lcol=t[rs].rcol=t[p].cov;
			t[ls].val=t[rs].val=1;
			t[p].cov=0;
		}
	}
	void build(ll p,ll l,ll r){
		if (l==r){
			t[p].lcol=t[p].rcol=a[l],t[p].val=1;
			return;
		}
		ll mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		update(p);
	}
	void change(ll p,ll l,ll r,ll a,ll b,ll v){
		if (l==a&&r==b){
			t[p].val=1,t[p].lcol=t[p].rcol=t[p].cov=v;
//			printf("%d %d %d %d %d
",l,r,a,b,v);
			return;
		}
		ll mid=(l+r)>>1;
		down(p);
		if (b<=mid) change(ls,l,mid,a,b,v);
		else if (a>mid) change(rs,mid+1,r,a,b,v);
		else change(ls,l,mid,a,mid,v),change(rs,mid+1,r,mid+1,b,v);
		update(p);
	}
	node query(ll p,ll l,ll r,ll a,ll b){
		if (a==l&&b==r) return t[p];//printf("%d %d %d %d %d
",l,r,a,b,t[p].val),
		ll mid=(l+r)>>1;
		down(p);//printf("%d %d %d %d %d
",p,l,r,a,b);
		if (b<=mid) return query(ls,l,mid,a,b);
		else if (a>mid) return query(rs,mid+1,r,a,b);
		else{
			node tmp,t1=query(ls,l,mid,a,mid),t2=query(rs,mid+1,r,mid+1,b);
			tmp.lcol=t1.lcol,tmp.rcol=t2.rcol;
			tmp.val=t1.val+t2.val-(t1.rcol==t2.lcol);
			return tmp;
		}
	}
}Seg;

void dfs(ll x){
	size[x]=1,hson[x]=0;
	for (ll y=now[x];y;y=pre[y])
		if (son[y]!=fa[x]){
			fa[son[y]]=x,dep[son[y]]=dep[x]+1,dfs(son[y]);
			if (size[son[y]]>size[hson[x]]) hson[x]=son[y];
			size[x]+=size[son[y]];
		}
}

void btree(ll x,ll tp){
	w[x]=++m,a[m]=col[x],top[x]=tp;
	if (hson[x]) btree(hson[x],top[x]);
	for (ll y=now[x];y;y=pre[y])
		if (son[y]!=fa[x]&&son[y]!=hson[x])
			btree(son[y],son[y]);
}

void cover(ll a,ll b,ll c){
	ll f1=top[a],f2=top[b];
	while (f1!=f2){
		if (dep[f1]dep[b]) swap(a,b);
//	printf("%d %d %d
",w[a],w[b],c);
	Seg.change(1,1,m,w[a],w[b],c);
}

ll answer(ll a,ll b){
	ll f1=top[a],f2=top[b],acol=-1,bcol=-1,ans=0;//   a  b      
	node tmp;
	while (f1!=f2){
		if (dep[f1]

転載先:https://www.cnblogs.com/thythy/p/5493598.html