首页 > 代码库 > bzoj-2243 2243: [SDOI2011]染色(树链剖分)
bzoj-2243 2243: [SDOI2011]染色(树链剖分)
题目链接：
2243: [SDOI2011]染色
Submit: 6267 Solved: 2291
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]之间。
题意：
思路：
树链剖分的入门题？反正上次写hdu边那个一个T,今天写这个点的版本的还好;调了一会就过了;
AC代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;#define lson o<<1#define rson o<<1|1const int maxn=1e5+10;int n,m,a[maxn];int siz[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn],tid[maxn],Rank[maxn],tim=0;vector<int>ve[maxn];void dfs1(int cur,int father,int deep){ fa[cur]=father; siz[cur]=1; dep[cur]=deep; int len=ve[cur].size(); for(int i=0;i<len;i++) { int x=ve[cur][i]; if(x==father)continue; dfs1(x,cur,deep+1); siz[cur]+=siz[x]; if(son[cur]==-1||siz[x]>siz[son[cur]])son[cur]=x; }}void dfs2(int cur,int tp){ top[cur]=tp; tid[cur]=++tim; Rank[tim]=cur; if(son[cur]==-1)return ; dfs2(son[cur],tp); int len=ve[cur].size(); for(int i=0;i<len;i++) { int x=ve[cur][i]; if(x==fa[cur]||x==son[cur])continue; dfs2(x,x); }}struct Tree{ int l,r,sum,lc,rc,mark; }tr[maxn*4];inline void pushup(int o){ tr[o].sum=tr[lson].sum+tr[rson].sum; tr[o].lc=tr[lson].lc;tr[o].rc=tr[rson].rc; if(tr[lson].rc==tr[rson].lc)tr[o].sum--;}inline void pushdown(int o){ if(tr[o].mark>=0) { tr[lson].sum=tr[rson].sum=1; tr[lson].lc=tr[lson].rc=tr[o].mark; tr[rson].lc=tr[rson].rc=tr[o].mark; tr[lson].mark=tr[rson].mark=tr[o].mark; tr[o].mark=-1; }}void build(int o,int L,int R){ tr[o].l=L;tr[o].r=R; tr[o].mark=-1; if(L>=R) { tr[o].sum=1; tr[o].lc=tr[o].rc=a[Rank[L]]; return ; } int mid=(L+R)>>1; build(lson,L,mid); build(rson,mid+1,R); pushup(o);}void update(int o,int L,int R,int num){ if(L<=tr[o].l&&R>=tr[o].r) { tr[o].sum=1; tr[o].lc=tr[o].rc=num; tr[o].mark=num; return ; } int mid=(tr[o].l+tr[o].r)>>1; pushdown(o); if(L<=mid)update(lson,L,R,num); if(R>mid)update(rson,L,R,num); pushup(o);}int query(int o,int L,int R,int & Lc,int & Rc){ if(L<=tr[o].l&&R>=tr[o].r) { if(L==tr[o].l)Lc=tr[o].lc; if(R==tr[o].r)Rc=tr[o].rc; return tr[o].sum; } int mid=(tr[o].l+tr[o].r)>>1; pushdown(o); if(R<=mid)return query(lson,L,R,Lc,Rc); else if(L>mid)return query(rson,L,R,Lc,Rc); else { int ans=query(lson,L,R,Lc,Rc)+query(rson,L,R,Lc,Rc); if(tr[lson].rc==tr[rson].lc)ans--; return ans; }}void change(int u,int v,int w){ int fu=top[u],fv=top[v]; while(fu!=fv) { if(dep[fu]<dep[fv])swap(u,v),swap(fu,fv); update(1,tid[fu],tid[u],w); u=fa[fu]; fu=top[u]; } if(dep[u]<dep[v])swap(u,v); update(1,tid[v],tid[u],w);}int solve(int u,int v){ int ans=0,fu=top[u],fv=top[v]; int preul=-1,preur=-1,prevl=-1,prevr=-1; int nowul=-1,nowur=-1,nowvl=-1,nowvr=-1; while(fu!=fv) { if(dep[fu]>dep[fv]) { ans+=query(1,tid[fu],tid[u],nowul,nowur); if(nowur==preul&&preul!=-1)ans--; preul=nowul;preur=nowur; u=fa[fu]; fu=top[u]; } else { ans+=query(1,tid[fv],tid[v],nowvl,nowvr); if(nowvr==prevl&&prevl!=-1)ans--; prevl=nowvl;prevr=nowvr; v=fa[fv]; fv=top[v]; } } if(dep[u]>dep[v]) { ans+=query(1,tid[v],tid[u],nowul,nowur); if(nowur==preul&&preul!=-1)ans--; if(nowul==prevl&&prevl!=-1)ans--; } else { ans+=query(1,tid[u],tid[v],nowvl,nowvr); if(nowvr==prevl&&prevl!=-1)ans--; if(nowvl==preul&&preul!=-1)ans--; } return ans;}int main(){ int u,v,w; char s[5]; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); ve[u].push_back(v); ve[v].push_back(u); } memset(son,-1,sizeof(son)); dfs1(1,0,0); dfs2(1,1); build(1,1,n); while(m--) { scanf("%s%d%d",s,&u,&v); if(s[0]==‘C‘) { scanf("%d",&w); change(u,v,w); } else printf("%d\n",solve(u,v)); } return 0;}
bzoj-2243 2243: [SDOI2011]染色(树链剖分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。