首页 > 代码库 > 【BZOJ 2243】 [SDOI2011]染色
【BZOJ 2243】 [SDOI2011]染色
2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2291 Solved: 890
[Submit][Status]
Description
给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
Input
第一行包含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)路径上的颜色段数量。
Output
对于每个询问操作,输出一行答案。
Sample Input
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
1
2
HINT
数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间。
Source
第一轮day1
树链剖分+线段树的lazy标记传递
分别说一下对于两个操作我的做法:
1.C(Paint):
维护一个变量modi,表示被修改成了多少,若modi=-1则表示没有被修改。
只要在线段树中找到要修改的区间,把modi赋值即可;修改之后要Push_up
2.Q(Query):
首先找到lca,然后对于u和v所在的重链进行相同的计算:
只要top[u]!=top[lca]就加上当前点到top[u]的颜色段数量。
注意要记录p,表示前一次计算中的最高点是谁。那么如果当前计算的最低点的颜色等于p的颜色,ans--。
top[u]=top[lca]后,再加上u到lca的颜色段数量,对p进行同样的处理。
最后从u和从v的计算结果相加再减1(因为lca被重复算了两次)就是答案。
<见代码中注释>
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <cmath> #define pb push_back #define N 100005 using namespace std; struct segtree { int modi,l,r,lc,rc,cs; }a[N*3]; vector<int> v[N]; int siz[N],n,m,son[N],fa[N],dep[N],top[N],id[N],co[N],cc[N],num; void dfs1(int x,int f,int de) { siz[x]=1; son[x]=0; fa[x]=f; dep[x]=de; for (int i=0;i<v[x].size();i++) if (v[x][i]!=fa[x]) { int u=v[x][i]; dfs1(u,x,de+1); siz[x]+=siz[u]; if (siz[son[x]]<siz[u]) son[x]=u; } } void dfs2(int x,int tp) { top[x]=tp; id[x]=++num; if (son[x]) dfs2(son[x],tp); for (int i=0;i<v[x].size();i++) { int u=v[x][i]; if (u==fa[x]||u==son[x]) continue; dfs2(u,u); } } void push_down(int x) { if (!x) return; if (a[x].modi!=-1) { a[x].lc=a[x].rc=a[x].modi; a[x].cs=1; if (a[x].l==a[x].r) //注意对叶子结点的特殊处理 { a[x].modi=-1; return; } a[x<<1].modi=a[x<<1|1].modi=a[x].modi; a[x].modi=-1; } } void push_up(int x) { if (!x||a[x].l==a[x].r) return; push_down(x<<1),push_down(x<<1|1); //一定要先下传 a[x].lc=a[x<<1].lc,a[x].rc=a[x<<1|1].rc; a[x].cs=a[x<<1].cs+a[x<<1|1].cs; if (a[x].cs>1&&a[x<<1].rc==a[x<<1|1].lc) a[x].cs--; } void Build(int x,int l,int r) { a[x].l=l,a[x].r=r,a[x].modi=-1; if (l==r) { a[x].lc=a[x].rc=cc[l]; a[x].cs=1; return; } int m=(l+r)>>1; Build(x<<1,l,m); Build(x<<1|1,m+1,r); push_up(x); } void Modify(int x,int l,int r,int c) { if (a[x].l>=l&&a[x].r<=r) { a[x].modi=c; return; } push_down(x); int m=(a[x].l+a[x].r)>>1; if (l<=m) Modify(x<<1,l,r,c); if (r>m) Modify(x<<1|1,l,r,c); push_up(x); } void Paint(int u,int v,int c) { int tp1=top[u],tp2=top[v]; while (tp1!=tp2) { if (dep[tp1]<dep[tp2]) swap(tp1,tp2),swap(u,v); Modify(1,id[tp1],id[u],c); u=fa[tp1]; tp1=top[u]; } if (u==v) { Modify(1,id[u],id[u],c); return; } if (dep[u]>dep[v]) swap(u,v); Modify(1,id[u],id[v],c); return; } int Count(int x,int l,int r) { push_down(x); if (a[x].l==l&&a[x].r==r) return a[x].cs; int m=(a[x].l+a[x].r)>>1; if (r<=m) return Count(x<<1,l,r); if (l>m) return Count(x<<1|1,l,r); int ans=Count(x<<1,l,m)+Count(x<<1|1,m+1,r); if (a[x<<1].rc==a[x<<1|1].lc&&ans>1) ans--; return ans; } int Getcolor(int x,int p) { push_down(x); if (a[x].l==p&&a[x].r==p) return a[x].lc; int m=(a[x].l+a[x].r)>>1; if (p<=m) return Getcolor(x<<1,p); else return Getcolor(x<<1|1,p); } int Query(int u,int v) { int uu=u,vv=v; int ans=0,tp1=top[u],tp2=top[v]; while (tp1!=tp2) //找lca { if (dep[tp1]<dep[tp2]) swap(tp1,tp2),swap(uu,vv); uu=fa[tp1]; tp1=top[uu]; } int lca=tp1,h; //这里的h是lca,lca是top[lca] if (dep[uu]>dep[vv]) h=vv; else h=uu; tp1=top[u],tp2=top[v]; int p=0; while (tp1!=lca) //从u开始算 { ans=ans+Count(1,id[tp1],id[u]); if (p&&Getcolor(1,p)==Getcolor(1,id[u])) ans--; p=id[tp1]; u=fa[tp1]; tp1=top[u]; } ans+=Count(1,id[h],id[u]); if (p&&Getcolor(1,p)==Getcolor(1,id[u])) ans--; p=0; while (tp2!=lca) //从v开始算 { ans=ans+Count(1,id[tp2],id[v]); if (p&&Getcolor(1,p)==Getcolor(1,id[v])) ans--; p=id[tp2]; v=fa[tp2]; tp2=top[v]; } ans+=Count(1,id[h],id[v]); if (p&&Getcolor(1,p)==Getcolor(1,id[v])) ans--; ans--; //lca这个点被计算了两次 return ans; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&co[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v[x].pb(y),v[y].pb(x); } num=0; dfs1(1,0,1); dfs2(1,1); for (int i=1;i<=n;i++) cc[id[i]]=co[i]; Build(1,1,n); while (m--) { char s[10]; int x,y,z; scanf("%s",s); if (s[0]=='C') { scanf("%d%d%d",&x,&y,&z); Paint(x,y,z); } else { scanf("%d%d",&x,&y); printf("%d\n",Query(x,y)); } } return 0; }
感悟:
1.CE了半个小时没查出来错。
查了一下说是函数名和编译器模板重复了,把所有函数过程的首字母大写之后就过了。
以后所有函数过程的首字母都大写吧!
2.WA:query中我算成了u和v都到达top[lca]的颜色段数了,其实到lca就行了。。
还是得细心啊。。。
3.对于有lazy标记的题目在Push_down和Push_up要特殊考虑叶子结点没有儿子以及a[0]的问题!
【BZOJ 2243】 [SDOI2011]染色