首页 > 代码库 > 染色[SDOI2011]
染色[SDOI2011]
题目描述
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
输入
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。
输出
对于每个询问操作，输出一行答案。
样例输入
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
样例输出
3
1
2
提示
N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
题解
从开始打就感觉这题绝对会白打，果然如此。刚开始学树剖，对题型的了解还很不全面。 1.刚开始接触的 A难存的情缘 和 C货车运输 是边权下放、边权修改、路径查询 if(id[x]<id[y]) res=qd(res,query(id[x]+1,id[y],1,1,n))； void change(int p,int t,int r,int z,int y) { if(z==y) { mx[r]=t; return; } int mid=(z+y)/2; if(p<=mid) change(p,t,r*2,z,mid); else change(p,t,r*2+1,mid+1,y); mx[r]=qd(mx[r*2],mx[r*2+1]); } 2.后来做的 B树上操作 和 E 树的统计 是点权修改、子树修改、路径查询，用到延迟标记和dfs序 if(id[x]<=id[y]) res+=query(id[x],id[y],1,1,n); void change(int fr,int to,ll a,int r,int z,int y) { if(fr<=z&&to>=y) { lazy[r]+=a; t[r].sm+=(long long)(y-z+1)*a; return; } pushdown(r); int mi=(t[r].le+t[r].ri)>>1; if(fr<=mi) change(fr,to,a,r<<1,z,mi); if(to>mi) change(fr,to,a,(r<<1)|1,mi+1,y); pushup(r); } 3.一直到今天的考试，我才明白change函数也可以像query一样分层操作。路径修改，路径查询，并且加了方向与合并。特别的是，把链上翻时比较链端和链端的父亲，来确认是否能合并一个色段。 query(id[fa[fx]],id[fa[fx]],1,1,n); zd2=zd1; query(id[fx],id[fx],1,1,n); if(zd1==zd2) res--; 因为有hotel的经验，在线段树里记录左右端颜色并不难想到，延迟标记也是理所当然。其他步骤都比较容易，只有没打过的路径修改和查询合并是问题所在。只要fx和fa[fx]颜色相同，就可以合并一个色块。
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; const int sj=100010; int n,m,ys[sj],h[sj],e,a1,a2,a3,zd1,zd2; char ss; struct B { int u,v,ne; }b[sj*2]; void add(int x,int y) { e++; b[e].ne=h[x]; b[e].u=x; b[e].v=y; h[x]=e; } void init() { scanf("%d%d",&n,&m); memset(h,-1,sizeof(h)); for(int i=1;i<=n;i++) scanf("%d",&ys[i]); for(int i=1;i<n;i++) { scanf("%d%d",&a1,&a2); add(a1,a2); add(a2,a1); } } int fa[sj]={0},son[sj]={0},size[sj],dep[sj]={0}; void dfs1(int x) { size[x]=1; for(int i=h[x];i!=-1;i=b[i].ne) { int to=b[i].v; if(to!=fa[x]) { fa[to]=x; dep[to]=dep[x]+1; dfs1(to); size[x]+=size[to]; if(size[to]>size[son[x]]) son[x]=to; } } } int top[sj],pos[sj],id[sj],cnt,sd[sj]; void dfs2(int x,int y) { top[x]=y; id[x]=++cnt; sd[id[x]]=x; pos[cnt]=x; if(son[x]) dfs2(son[x],y); for(int i=h[x];i!=-1;i=b[i].ne) { int to=b[i].v; if(to!=fa[x]&&to!=son[x]) dfs2(to,to); } } struct Tree { int ds,zj,yj,zs,ys; }t[sj*4]; int lazy[sj*4]; void build(int x,int z,int y) { t[x].zj=z; t[x].yj=y; if(z==y) { t[x].ds=1; t[x].zs=t[x].ys=ys[pos[z]]; return; } int mid=(z+y)>>1,ze=x<<1,ye=(x<<1)|1; build(ze,z,mid); build(ye,mid+1,y); t[x].ds=t[ze].ds+t[ye].ds; if(t[ze].ys==t[ye].zs) t[x].ds--; t[x].ys=t[ye].ys; t[x].zs=t[ze].zs; } void jh(int &x,int &y) { int jy=y; y=x; x=jy; } void pushdown(int x) { if(lazy[x]!=-1) { int ze=x<<1,ye=(x<<1)|1; lazy[ze]=lazy[ye]=lazy[x]; t[ze].ds=t[ye].ds=1; t[ze].zs=t[ze].ys=lazy[x]; t[ye].zs=t[ye].ys=lazy[x]; lazy[x]=-1; } } void pushup(int x) { int ze=x<<1,ye=(x<<1)|1; t[x].ds=t[ze].ds+t[ye].ds; if(t[ze].ys==t[ye].zs) t[x].ds--; t[x].ys=t[ye].ys; t[x].zs=t[ze].zs; } int query(int s,int to,int r,int z,int y) { if(s==z&&to==y) { zd1=t[r].zs; return t[r].ds; } pushdown(r); int mid=(z+y)>>1; int ze=r<<1,ye=(r<<1)|1; if(to<=mid) return query(s,to,ze,z,mid); if(s>mid) return query(s,to,ye,mid+1,y); int res=query(s,mid,ze,z,mid)+query(mid+1,to,ye,mid+1,y); if(t[ze].ys==t[ye].zs) res--; return res; } int Q(int x,int y) { int res=0,fx=top[x],fy=top[y]; while(fx^fy) { if(dep[fx]<dep[fy]) { jh(x,y); jh(fx,fy); } res+=query(id[fx],id[x],1,1,n); query(id[fa[fx]],id[fa[fx]],1,1,n); zd2=zd1; query(id[fx],id[fx],1,1,n); if(zd1==zd2) res--; x=fa[fx]; fx=top[x]; } if(dep[x]>dep[y]) jh(x,y); if(id[x]<=id[y]) res+=query(id[x],id[y],1,1,n); return res; } void c(int s,int to,int a,int r,int z,int y) { if(s==z&&to==y) { lazy[r]=a; t[r].ds=1; t[r].ys=t[r].zs=a; return; } pushdown(r); int mid=(z+y)>>1; int ze=r<<1,ye=(r<<1)|1; if(to<=mid) c(s,to,a,ze,z,mid); if(s>mid) c(s,to,a,ye,mid+1,y); if(to>mid&&s<=mid) { c(s,mid,a,ze,z,mid); c(mid+1,to,a,ye,mid+1,y); } pushup(r); } void C(int x,int y,int a) { int fx=top[x],fy=top[y]; while(fx^fy) { if(dep[fx]<dep[fy]) { jh(x,y); jh(fx,fy); } c(id[fx],id[x],a,1,1,n); x=fa[fx]; fx=top[x]; } if(dep[x]>dep[y]) jh(x,y); if(id[x]<=id[y]) c(id[x],id[y],a,1,1,n); } void cl() { for(int i=1;i<=m;i++) { scanf("%s",&ss); scanf("%d%d",&a1,&a2); if(ss==‘Q‘) printf("%d\n",Q(a1,a2)); if(ss==‘C‘) { scanf("%d",&a3); C(a1,a2,a3); } } } int main() { //freopen("t3.txt","r",stdin); init(); dfs1(1); dfs2(1,1); memset(lazy,-1,sizeof(lazy)); build(1,1,n); cl(); //while(1); return 0; }
染色[SDOI2011]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。