[SDOI2011]染色
题目描述
输入输出格式
解法
ps:这题本来是树剖的，但我用lct写的，以下是lct的写法，树剖会有所不同
我们考虑把连接不同色点的边权值设为1,连接同色的点的边权设为0，这样我们就可以把问题转化为查询这条路径上所有的边权和，你要输出的就是这个答案加一。 对于维护，我们对每条路径维护一个最左端点的值和最右端点的值，这样就可以统计O(1)地合并信息，修改时做一个懒标记，下放时将当前ans清零再修改左右端点即可。 区间反转时左右端点也要反转 区间反转时左右端点也要反转 区间反转时左右端点也要反转 重要的话说三遍(我就被坑了好久)。代码
#include#define rg registerusing namespace std;int gi(){ char a=getchar();int b=0; while(a<'0'||a>'9')a=getchar(); while(a>='0'&&a<='9')b=b*10+a-'0',a=getchar(); return b;}const int N=1e6;int fa[N],ch[N][2],ans[N],w[N],l[N],r[N],lazy1[N],lazy2[N],fz[N],top;int get(int x){return ch[fa[x]][1]==x;}int isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void pushdown(int x){ rg int L=ch[x][0],R=ch[x][1]; if(lazy1[x]){ swap(ch[x][0],ch[x][1]); swap(l[L],r[L]); swap(l[R],r[R]); lazy1[L]^=1; lazy1[R]^=1; lazy1[x]^=1; } if(lazy2[x]){ w[x]=l[x]=r[x]=lazy2[L]=lazy2[R]=lazy2[x]; lazy2[x]=0; ans[x]=0; }}void pushup(int x){ pushdown(ch[x][0]); pushdown(ch[x][1]); ans[x]=0; if(ch[x][0]){ l[x]=l[ch[x][0]]; if(w[x]!=r[ch[x][0]])ans[x]++; } else l[x]=w[x]; if(ch[x][1]){ r[x]=r[ch[x][1]]; if(w[x]!=l[ch[x][1]])ans[x]++; } else r[x]=w[x]; ans[x]+=ans[ch[x][0]]+ans[ch[x][1]];}void rotate(int x){ int y=fa[x],z=fa[y],k=get(x); fa[x]=z;if(!isroot(y))ch[z][ch[z][1]==y]=x; ch[y][k]=ch[x][k^1];fa[ch[y][k]]=y; fa[y]=x;ch[x][k^1]=y; pushup(y);pushup(x);}void splay(int x){ for(int i=x;;i=fa[i]){ fz[++top]=i; if(isroot(i))break; } while(top){pushdown(fz[top--]);} while(!isroot(x)){ int y=fa[x]; if(!isroot(y)) if(get(x)==get(y))rotate(y); else rotate(x); rotate(x); }}void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);}void makeroot(int x){access(x);splay(x);lazy1[x]^=1;}void link(int x,int y){makeroot(x);fa[x]=y;}void split(int x,int y){makeroot(x);access(y);splay(y);}void update(int x,int y,int k){split(x,y);lazy2[y]=k;}void query(int x,int y){split(x,y);printf("%d\n",ans[y]+1);}int main(){ int n=gi(),m=gi(); for(int i=1;i<=n;++i){ w[i]=gi(); l[i]=r[i]=w[i]; } for(int i=1;i