首页 > 代码库 > [BZOJ 2243][SDOI2011]染色（树链剖分+线段树）
[BZOJ 2243][SDOI2011]染色（树链剖分+线段树）
Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
Solution
解决了一个困扰我很多年的问题=w=
（这题应该是刚学树剖的时候写的，然而莫名其妙的T掉了3个点，以为被卡常了，于是开始了卡常大作战…改了一下午之后就放弃了…今天翻出来发现是重儿子找错了，改了改就A了…另外感觉当时的代码风格真是十分不堪，当时的我真naive）
具体的一些细节我已经忘了QwQ
#include<iostream>#include<cstdio>#include<cstring>#define MAXN 100005#define RG registerusing namespace std;int n,m,head[MAXN],cnt=0,ans,col[MAXN];int sz=0,pos[MAXN],top[MAXN],dep[MAXN],son[MAXN],father[MAXN],siz[MAXN],inv[MAXN];inline int read(){ int f=1,x=0;char c=getchar(); while(c<‘0‘||x>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return f*x;}struct Node1{ int next,to;}Edges[MAXN*2];inline void addedge(int u,int v){ Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v;}inline void dfs1(int u){ siz[u]=1; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==father[u])continue; father[v]=u;dep[v]=dep[u]+1; dfs1(v);siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; }}inline void dfs2(int u,int t){ sz++,pos[u]=sz; inv[sz]=u,top[u]=t; if(son[u])dfs2(son[u],t); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==father[u]||v==son[u])continue; dfs2(v,v); }}struct Node2{ int lc,rc,num,lazy;}t[MAXN*3];inline void pushdown(int idx,int l,int r){ if(l!=r&&t[idx].lazy) { t[idx<<1].lazy=t[idx<<1|1].lazy=t[idx<<1].num=t[idx<<1|1].num=1; t[idx].lazy=0; t[idx<<1].lc=t[idx<<1|1].lc=t[idx<<1].rc=t[idx<<1|1].rc=t[idx].lc; }}inline void update(int idx){ t[idx].lc=t[idx<<1].lc; t[idx].rc=t[idx<<1|1].rc; t[idx].num=t[idx<<1].num+t[idx<<1|1].num-(t[idx<<1].rc==t[idx<<1|1].lc);}inline void build(int idx,int l,int r){ t[idx].lazy=0; if(l==r) { t[idx].lc=t[idx].rc=col[inv[l]]; t[idx].num=1; return; } int mid=(l+r)>>1; build(idx<<1,l,mid),build(idx<<1|1,mid+1,r); update(idx);}inline void color(int idx,int l,int r,int a,int b,int c){ if(l==a&&r==b) { t[idx].num=t[idx].lazy=1; t[idx].lc=t[idx].rc=c; return; } pushdown(idx,l,r); int mid=(l+r)>>1; if(a>mid)color(idx<<1|1,mid+1,r,a,b,c); else if(b<=mid)color(idx<<1,l,mid,a,b,c); else { color(idx<<1|1,mid+1,r,mid+1,b,c); color(idx<<1,l,mid,a,mid,c); } update(idx);}inline int query(int idx,int l,int r,int a,int b){ if((l==a&&r==b)||t[idx].lazy)return t[idx].num; pushdown(idx,l,r); int mid=(l+r)>>1,ans=0; if(a>mid)return query(idx<<1|1,mid+1,r,a,b); else if(b<=mid)return query(idx<<1,l,mid,a,b); else { ans+=query(idx<<1,l,mid,a,mid); ans+=query(idx<<1|1,mid+1,r,mid+1,b); ans-=t[idx<<1].rc==t[idx<<1|1].lc; } return ans;}inline int getcolor(int idx,int l,int r,int a){ if(l==r||t[idx].lazy)return t[idx].lc; int mid=(l+r)>>1; if(a<=mid)return getcolor(idx<<1,l,mid,a); else return getcolor(idx<<1|1,mid+1,r,a);}inline void solve1(int x,int y,int z){ while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); color(1,1,sz,pos[top[x]],pos[x],z); x=father[top[x]]; } if(pos[x]<pos[y])swap(x,y); color(1,1,sz,pos[y],pos[x],z);}inline void solve2(int x,int y){ ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=query(1,1,sz,pos[top[x]],pos[x]); if(getcolor(1,1,sz,pos[top[x]])==getcolor(1,1,sz,pos[father[top[x]]]))ans--; x=father[top[x]]; } if(pos[x]<pos[y])swap(x,y); ans+=query(1,1,sz,pos[y],pos[x]); printf("%d\n",ans);}int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); for(RG int i=1;i<=n;++i)col[i]=read(); int x,y,z; for(RG int i=1;i<n;++i) { x=read(),y=read(); addedge(x,y),addedge(y,x); } dfs1(1),dfs2(1,1); build(1,1,sz); char opt; for(RG int i=1;i<=m;++i) { opt=getchar(); while(opt!=‘C‘&&opt!=‘Q‘)opt=getchar(); if(opt==‘C‘) x=read(),y=read(),z=read(),solve1(x,y,z); else if(opt==‘Q‘) x=read(),y=read(),solve2(x,y); } return 0; }
[BZOJ 2243][SDOI2011]染色（树链剖分+线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。