luogu P2486 [SDOI2011]染色
这道题第一眼看过去
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。显然嘛
树剖
搞呗
线段树挨个统计颜色段数
但是搞的时候需要记录一下线段树每个节点的左右子节点的颜色
因为如果左边子树的右儿子颜色和右边子树左儿子颜色一样ans要--
同时剖出来的链也要判断一下与上一次剖到的链的颜色是否相同
代码挺长的
写完debug整的我眼睛疼死
![luogu P2486 [SDOI2011]染色 随笔 第1张 luogu P2486 [SDOI2011]染色 随笔 第1张](https://www.liuyixiang.com/zb_users/theme/Lucky/style/image/grey.gif)
#include<cstdio> #include<algorithm> #define sev en using namespace std; #define N 100010 int n,m; struct EDGE { int to,nxt; } e[N << 1]; int head[N],cnt; int a[N]; void add(int x,int y) { e[++cnt].to = y; e[cnt].nxt = head[x]; // e[cnt].w = z; head[x] = cnt; } int dep[N],fa[N],siz[N],heavy[N]; void dfs1(int x,int f,int d) { fa[x] = f; dep[x] = d; siz[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int v = e[i].to; if(v == fa[x]) continue; dfs1(v,x,d + 1); siz[x] += siz[v]; if(siz[v] > siz[heavy[x]]) heavy[x] = v; } return ; } int dfn[N],top[N]; void dfs2(int u,int t) { dfn[u] = ++cnt; top[u] = t; a[cnt] = u; if(!heavy[u]) return ; dfs2(heavy[u],t); for(int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if(v == fa[u] || v == heavy[u]) continue; dfs2(v,v); } return ; } int sum[N << 2],left[N << 2],right[N << 2]; void pushup(int now) { sum[now] = sum[now << 1] + sum[now << 1 | 1]; left[now] = left[now << 1]; right[now] = right[now << 1 | 1]; if(left[now << 1 | 1] == right[now << 1]) sum[now]--; return ; } int col[N]; void build(int now,int l,int r) { if(l == r) { sum[now] = 1; left[now] = right[now] = col[a[l]]; return ; } int mid = (l + r) >> 1; build(now << 1,l,mid); build(now << 1 | 1,mid + 1,r); pushup(now); return ; } int lazy[N << 2]; void pushdown(int now,int l,int r) { sum[now << 1] = sum[now << 1 | 1] = 1; left[now << 1] = right[now << 1] = left[now << 1 | 1] = right[now << 1 | 1] = lazy[now << 1] = lazy[now << 1 | 1] = lazy[now]; lazy[now] = 0; return ; } void modify(int now,int l,int r,int x,int y,int c) { if(l == x && r == y) { sum[now] = 1; lazy[now] = left[now] = right[now] = c; return ; } if(lazy[now]) pushdown(now,l,r); int mid = (l + r) >> 1; if(x > mid) modify(now << 1 | 1,mid + 1,r,x,y,c); else if(y <= mid) modify(now << 1,l,mid,x,y,c); else { modify(now << 1,l,mid,x,mid,c); modify(now << 1 | 1,mid + 1,r,mid + 1,y,c); } pushup(now); return ; } void get_modify(int x,int y,int c) { while(top[x] != top[y]) { if(dep[top[x]] > dep[top[y]]) swap(x,y); modify(1,1,n,dfn[top[y]],dfn[y],c); y = fa[top[y]]; } if(dep[x] > dep[y]) swap(x,y); modify(1,1,n,dfn[x],dfn[y],c); return ; } int query(int now,int l,int r,int x,int y) { if(l == x && r == y) return sum[now]; if(lazy[now]) pushdown(now,l,r); int mid = (l + r) >> 1; if(x > mid) return query(now << 1 | 1,mid + 1,r,x,y); else if(y <= mid) return query(now << 1,l,mid,x,y); else{ int ans = query(now << 1,l,mid,x,mid) + query(now << 1 | 1,mid + 1,r,mid + 1,y); if(right[now << 1] == left[now << 1 | 1]) ans--; return ans; } } int update(int now,int l,int r,int x){ if(l == r) return left[now]; if(lazy[now]) pushdown(now,l,r); int mid = (l + r) >> 1; if(x > mid) return update(now << 1 | 1,mid + 1,r,x); else return update(now << 1,l,mid,x); } int get_query(int x,int y) { int ans = 0,L,R; while(top[x] != top[y]) { if(dep[top[x]] > dep[top[y]]) swap(x,y); ans += query(1,1,n,dfn[top[y]],dfn[y]); L = update(1,1,n,dfn[top[y]]); R = update(1,1,n,dfn[fa[top[y]]]); y = fa[top[y]]; if(L == R) ans--; } if(dep[x] > dep[y]) swap(x,y); ans += query(1,1,n,dfn[x],dfn[y]); if(ans) return ans; else return 1; } int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&col[i]); for(int i = 1; i < n; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } cnt = 0; dfs1(1,0,1); dfs2(1,1); build(1,1,n); for(int i = 1; i <= m; i++) { char op[5]; int l,r,c; scanf("%s",op); if(op[0] == 'C') { scanf("%d%d%d",&l,&r,&c); get_modify(l,r,c); } if(op[0] == 'Q') { scanf("%d%d",&l,&r); printf("%d\n",get_query(l,r)); } } return 0; }因为太长了所以终于折叠了一次代码显得这篇blog很短
ok啦
说起来
今天zzb就走了
我快乐!
然后突然发现没写过树剖和点分治的blog
咕咕咕万一以后写了呢emmmm

更多精彩