洛谷 [P2486] 染色

树剖+线段树维护连续相同区间个数

注意什么时候长度要减一
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define ll long long

using namespace std;

const int MAXN=100005;

int top[MAXN],head[MAXN],nume,n,m,dep[MAXN],fa[MAXN],son[MAXN],siz[MAXN],id[MAXN],wei[MAXN],wein[MAXN],ind;

struct edge{

	int to,nxt;

}e[MAXN<<1];

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

void adde(int from,int to){

	e[++nume].to=to;

	e[nume].nxt=head[from];

	head[from]=nume;

}

void dfs1(int u,int rt){

	dep[u]=dep[rt]+1;

	fa[u]=rt;

	siz[u]=1;

	int ma=0;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==rt) continue;

		dfs1(v,u);

		siz[u]+=siz[v];

		if(siz[v]>ma){

			ma=siz[v];

			son[u]=v;

		}

	}

}

void dfs2(int u,int topf){

	top[u]=topf;

	id[u]=++ind;

	wein[ind]=wei[u];

	if(!son[u]) return;

	dfs2(son[u],topf);

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa[u]||v==son[u]) continue;

		dfs2(v,v);

	}

}

struct SGT{

	int sum[MAXN<<2],tag[MAXN<<2],lc[MAXN<<2],rc[MAXN<<2];

	void PushUp(int rt){

		sum[rt]=sum[rt<<1]+sum[rt<<1|1]-(rc[rt<<1]==lc[rt<<1|1]);

		lc[rt]=lc[rt<<1];rc[rt]=rc[rt<<1|1];

	}

	void build(int l,int r,int rt){

		if(l==r){

			sum[rt]=1;

			lc[rt]=rc[rt]=wein[l];

			return ;

		}

		int mid=(l+r)>>1;

		build(lson);

		build(rson);

		PushUp(rt);

	}

	void PushDown(int rt){

		if(tag[rt]){

			tag[rt<<1]=tag[rt<<1|1]=tag[rt];

			sum[rt<<1]=sum[rt<<1|1]=1;

			lc[rt<<1]=rc[rt<<1]=lc[rt<<1|1]=rc[rt<<1|1]=tag[rt];

			tag[rt]=0;

		}

	}

	void Update(int L,int R,int add,int l,int r,int rt){

		if(L<=l&&r<=R){

			sum[rt]=1;

			lc[rt]=rc[rt]=add;

			tag[rt]=add;

			return;

		}

		PushDown(rt);

		int mid=(l+r)>>1;

		if(L<=mid) Update(L,R,add,lson);

		if(mid<R) Update(L,R,add,rson);

		PushUp(rt);

	}

	int Query(int L,int R,int l,int r,int rt){

		if(L<=l&&r<=R){

			return sum[rt];

		}

		PushDown(rt);

		int mid=(l+r)>>1;

		int ans=0,f=0;

		if(L<=mid) ans+=Query(L,R,lson),f++;

		if(mid<R) ans+=Query(L,R,rson),f++;

		if(f==2){

			ans-=(rc[rt<<1]==lc[rt<<1|1]);

		}

		PushUp(rt);

		return ans;

	}

	int find(int loc,int l,int r,int rt){

		if(l==r){

			return rc[rt];

		}

		PushDown(rt);

		int mid=(l+r)>>1;

		int ans=0;

		if(loc<=mid) ans=find(loc,lson);

		else ans=find(loc,rson);

		PushUp(rt);

		return ans;

	}

}sgt;

void UpdateRange(int u,int v,int add){

	while(top[u]!=top[v]){

		if(dep[top[u]]<dep[top[v]]) swap(u,v);

		sgt.Update(id[top[u]],id[u],add,1,n,1);

		u=fa[top[u]];

	}

	if(dep[u]>dep[v]) swap(u,v);

	sgt.Update(id[u],id[v],add,1,n,1);

}

int QueryRange(int u,int v){

	int ans=0;

	while(top[u]!=top[v]){

		if(dep[top[u]]<dep[top[v]]) swap(u,v);

		ans+=sgt.Query(id[top[u]],id[u],1,n,1);

		ans-=(sgt.find(id[fa[top[u]]],1,n,1)==sgt.find(id[top[u]],1,n,1));

		u=fa[top[u]];

	}

	if(dep[u]>dep[v]) swap(u,v);

	ans+=sgt.Query(id[u],id[v],1,n,1);

	return ans;

}

int main(){

	n=init();m=init();

	for(int i=1;i<=n;i++) wei[i]=init();

	for(int i=1;i<n;i++){

		int u=init(),v=init();

		adde(u,v);adde(v,u);

	}

	dep[1]=1;

	dfs1(1,0);

	dfs2(1,1);

	sgt.build(1,n,1);

	char s[10];

	/*for(int i=1;i<=n;i++) printf("%d ",wein[id[i]]);

	cout<<endl;

	for(int i=1;i<=n;i++) printf("%d ",sgt.find(id[i],1,n,1));

	cout<<endl;*/

	for(int i=1;i<=m;i++){

		scanf("%s",s);

		if(s[0]=='C'){

			int a=init(),b=init(),t=init();

			UpdateRange(a,b,t);

			/*for(int i=1;i<=n;i++) printf("%d ",sgt.find(id[i],1,n,1));

			cout<<endl;*/

		}else {

			int a=init(),b=init();

			printf("%d\n",QueryRange(a,b));

		}

	}

	for(int i=1;i<=n;i++) ;

	return 0;

}
巴特西

洛谷 [P2486] 染色

树剖+线段树维护连续相同区间个数

最新文章

热门文章
