首页 > 代码库 > bzoj2243 [SDOI2011]染色
bzoj2243 [SDOI2011]染色
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
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
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
3
1
2
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
树链剖分继续搞起
线段树的标记的各种转移有点麻烦
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 100010using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,cnt,tt,save_lc,save_rc,mn,mx;struct edge{ int to,next;}e[2*N];struct segtree{ int l,r,sum,lc,rc,tag;}tree[4*N];int head[N],v[N];int mrk[N],son[N],depth[N],fa[N][21];int place[N],pplace[N],belong[N];char ch[10];inline void ins(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v){ ins(u,v); ins(v,u);}inline void dfs1(int x,int dep){ if (mrk[x])return; mrk[x]=1;son[x]=1;depth[x]=dep; for (int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for (int i=head[x];i;i=e[i].next) if (!mrk[e[i].to]) { fa[e[i].to][0]=x; dfs1(e[i].to,dep+1); son[x]+=son[e[i].to]; }}inline void dfs2(int x,int chain){ place[x]=++tt;pplace[tt]=x; belong[x]=chain; int mx=-inf,res=-1; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) { if (son[e[i].to]>mx) { mx=son[e[i].to]; res=e[i].to; } } if (res==-1)return; dfs2(res,chain); for(int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]&&e[i].to!=res) dfs2(e[i].to,e[i].to);}inline int LCA(int a,int b){ if (depth[a]<depth[b])swap(a,b); int res=depth[a]-depth[b]; for (int i=0;i<20;i++) if (res & (1<<i))a=fa[a][i]; for (int i=19;i>=0;i--) if (fa[a][i]!=fa[b][i]) { a=fa[a][i]; b=fa[b][i]; } if(a==b)return a; return fa[a][0];}inline void update(int k){ tree[k].lc=tree[k<<1].lc; tree[k].rc=tree[k<<1|1].rc; tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; if (tree[k<<1].rc==tree[k<<1|1].lc)tree[k].sum--;}inline void pushdown(int k){ int tag=tree[k].tag;tree[k].tag=-1; if (tag==-1||tree[k].l==tree[k].r)return; tree[k<<1].tag=tree[k<<1|1].tag=tag; tree[k<<1].sum=tree[k<<1|1].sum=1; tree[k<<1].lc=tree[k<<1|1].lc=tag; tree[k<<1].rc=tree[k<<1|1].rc=tag;}inline void buildtree(int now,int l,int r){ tree[now].l=l;tree[now].r=r; tree[now].tag=-1; if (l==r) { tree[now].lc=v[pplace[l]]; tree[now].rc=v[pplace[l]]; tree[now].sum=1; return; } int mid=(l+r)>>1; buildtree(now<<1,l,mid); buildtree(now<<1|1,mid+1,r); update(now);}inline int ask_in_tree(int now,int x,int y){ pushdown(now); int l=tree[now].l,r=tree[now].r; if (l==x&&r==y) { if (l<mn) { save_lc=tree[now].lc; mn=l; } if (r>mx) { save_rc=tree[now].rc; mx=r; } return tree[now].sum; } int mid=(l+r)>>1; if (y<=mid)return ask_in_tree(now<<1,x,y); if (x>mid)return ask_in_tree(now<<1|1,x,y); else { int res=ask_in_tree(now<<1,x,mid)+ask_in_tree(now<<1|1,mid+1,y); if (tree[now<<1].rc==tree[now<<1|1].lc)res--; return res; }}inline void change_in_tree(int now,int x,int y,int dat){ pushdown(now); int l=tree[now].l,r=tree[now].r; if (l==x&&r==y) { tree[now].lc=tree[now].rc=dat; tree[now].sum=1; tree[now].tag=dat; return; } int mid=(l+r)>>1; if (y<=mid)change_in_tree(now<<1,x,y,dat); else if (x>mid)change_in_tree(now<<1|1,x,y,dat); else { change_in_tree(now<<1,x,mid,dat); change_in_tree(now<<1|1,mid+1,y,dat); } update(now);}inline int ask(int from,int to){ int l,r,s=0,last=-1; while (belong[from]!=belong[to]) { l=place[belong[from]]; r=place[from]; mx=-inf;mn=inf;save_lc=save_rc=-1; s+=ask_in_tree(1,l,r); if (last!=-1&&last==save_rc)s--; last=save_lc; from=fa[belong[from]][0]; } l=place[to]; r=place[from]; mx=-inf;mn=inf;save_lc=save_rc=-1; s+=ask_in_tree(1,l,r); if (last!=-1&&last==save_rc)s--; return s;}inline void change(int from,int to,int dat){ int l,r; while (belong[from]!=belong[to]) { l=place[belong[from]]; r=place[from]; change_in_tree(1,l,r,dat); from=fa[belong[from]][0]; } l=place[to]; r=place[from]; change_in_tree(1,l,r,dat);}int main(){ n=read();m=read(); for(int i=1;i<=n;i++)v[i]=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); insert(x,y); } dfs1(1,1); dfs2(1,1); buildtree(1,1,n); for (int i=1;i<=m;i++) { scanf("%s",ch); if (ch[0]==‘Q‘) { int x=read(),y=read(),lca=LCA(x,y); printf("%d\n",ask(x,lca)+ask(y,lca)-1); } if (ch[0]==‘C‘) { int x=read(),y=read(),z=read(),lca=LCA(x,y); change(x,lca,z); change(y,lca,z); } } return 0;}
bzoj2243 [SDOI2011]染色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。