首页 > 代码库 > BZOJ2243: [SDOI2011]染色
BZOJ2243: [SDOI2011]染色
2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 1861 Solved: 739
[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
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]之间。
Source
第一轮day1
解法：树链剖分，用线段树维护信息，重点就是合并两个线段
假设是 11211333 3321122
一个seg记录最左边的颜色，最右边的颜色， 答案，三个值
合并的话就是seg[rt].ans = seg[rt << 1].ans + seg[rt << 1 | 1].ans - (seg[rt << 1].r == seg[rt << 1 | 1].l);
有个trick，颜色是[0,10^9]的，所以0那个地方要注意注意~，下放标记的时候嗯啊
还有个要注意的是，算答案的时候要动态合并
就说你提取出来哪些线段，想象一下整个过程，是x,y不断往lca走的过程，那么开两个值分别记录x走的时候最“上”端的颜色，y最上端的颜色，最后一步lca那个特殊判一下就行
/*Author:wuhuajun*/#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#define lson l, mid, rt << 1#define rson mid+1, r, rt << 1 | 1using namespace std; typedef long long ll;typedef double dd;const int maxn=100010; int edge, n, fa[maxn], sz[maxn], son[maxn], dep[maxn], hash[maxn], top[maxn];int h[maxn], num, a[maxn], x, y, tx, ty, Q, col, ans, lcol, rcol;char s[22]; struct Edge{ int to, ne;} e[maxn * 2]; struct Seg{ int ans, l, r, same; void clear() { ans = l = r = same = 0; }} seg[maxn << 2]; void close(){ exit(0);} void addedge(int x,int y){ e[edge].to = y; e[edge].ne = h[x]; h[x] = edge++;} void dfs(int k,int from){ sz[k] = 1; son[k] = 0; dep[k] = dep[from] + 1; for (int p=h[k];p!=-1;p=e[p].ne) { int to = e[p].to; if (from == to) continue; fa[to] = k; dfs(to, k); sz[k] += sz[to]; if (sz[to] > sz[son[k]]) son[k] = to; }} void build(int k,int from){ hash[k] = ++num; top[k] = from; if (son[k]) build(son[k], from); for (int p=h[k];p!=-1;p=e[p].ne) { int to = e[p].to; if (to != fa[k] && to != son[k]) build(to, to); }} //{{{Segment部分 void pushup(int rt){ seg[rt].l = seg[rt << 1].l; seg[rt].r = seg[rt << 1 | 1].r; seg[rt].ans = seg[rt << 1].ans + seg[rt << 1 | 1].ans - (seg[rt << 1].r == seg[rt << 1 | 1].l);} void same(int rt,int col){ seg[rt].same = col; seg[rt].l = seg[rt].r = col; seg[rt].ans = 1;} void pushdown(int rt){ if (seg[rt].same) { same(rt << 1, seg[rt].same); same(rt << 1 | 1, seg[rt].same); seg[rt].same = 0; }} void change(int L,int R,int val,int l,int r,int rt){ if (L <= l && r <= R) { same(rt, val); return; } int mid = (l + r) >> 1; pushdown(rt); if (L <= mid) change(L,R,val,lson); if (mid + 1 <= R) change(L,R,val,rson); pushup(rt);} Seg query(int L,int R,int l,int r,int rt){ if (L <= l && r <= R) { return seg[rt]; } int mid = (l + r) >> 1; Seg ans,a,b; ans.clear(); a.clear(); b.clear(); pushdown(rt); if (L <= mid) a = query(L,R,lson); if (mid + 1 <= R) b = query(L,R,rson); ans.ans = a.ans + b.ans; ans.l = a.l; ans.r = b.r; if (b.l == 0) ans.r = a.r; if (a.l == 0) ans.l = b.l; if (b.l != 0 && a.l != 0) { ans.ans -= (a.r == b.l); } pushup(rt); return ans;}//}}}//void work(){ tx = top[x]; ty = top[y]; while (tx != ty) { if (dep[tx] < dep[ty]) { swap(tx, ty); swap(x, y); } change(hash[tx], hash[x], col, 1, n, 1); x = fa[tx]; tx = top[x]; } if (dep[x] > dep[y]) swap(x, y); change(hash[x], hash[y], col, 1, n, 1);} int get_ans(){ ans = 0; tx = top[x]; ty = top[y]; lcol = rcol = 0; while (tx != ty) { if (dep[tx] < dep[ty]) { Seg haha = query(hash[ty], hash[y], 1, n, 1); //printf("ty:%d y:%d lcol:%d rcol:%d l:%d r:%d haha.ans:%d\n",ty,y,lcol,rcol,haha.l,haha.r,haha.ans); ans += haha.ans; if (haha.r == rcol) ans--; rcol = haha.l; y = fa[ty]; ty = top[y]; } else { Seg haha = query(hash[tx], hash[x], 1, n, 1); //printf("tx:%d x:%d lcol:%d rcol:%d l:%d r:%d haha.ans:%d\n",tx,x,lcol,rcol,haha.l,haha.r,haha.ans); ans += haha.ans; if (haha.r == lcol) ans--; lcol = haha.l; x = fa[tx]; tx = top[x]; } } if (dep[x] > dep[y]) { Seg haha = query(hash[y], hash[x], 1, n, 1); //printf("y:%d x:%d rcol:%d haha.r:%d haha.ans:%d\n",y,x,rcol,haha.r,haha.ans); ans += haha.ans; if (haha.r == lcol) ans--; if (haha.l == rcol) ans--; } else { Seg haha = query(hash[x], hash[y], 1, n, 1); //printf("x:%d y:%d lcol:%d haha.r:%d haha.ans:%d\n",x,y,lcol,haha.r,haha.ans); ans += haha.ans; if (haha.r == rcol) ans--; if (haha.l == lcol) ans--; } //puts(""); return ans;} void init(){ scanf("%d %d",&n,&Q); for (int i=1;i<=n;i++) { scanf("%d", &a[i]); a[i]++; } memset(h,-1,sizeof(h)); for (int i=1;i<=n-1;i++) { scanf("%d %d",&x, &y); addedge(x, y); addedge(y, x); } dfs(1, 0); build(1, 1); for (int i=1;i<=n;i++) change(hash[i], hash[i], a[i], 1, n, 1); /* for (int i=1;i<=n;i++) { printf("i:%d top:%d hash:%d\n",i, top[i], hash[i]); } */ while (Q--) { scanf("%s %d %d",s,&x,&y); if (s[0] == ‘C‘) { scanf("%d",&col); col++; work(); continue; } printf("%d\n",get_ans()); }} int main (){ init(); close(); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。