首页 > 代码库 > [BZOJ 2243] [SDOI 2011] 染色
[BZOJ 2243] [SDOI 2011] 染色
题目链接:BZOJ - 2243
题目分析
树链剖分...写了200+行...Debug了整整一天+...
静态读代码读了 5 遍 ,没发现错误,自己做小数据也过了。
提交之后全 WA 。
————————————— 杯具的分割线 —————————————————
然后看了别人代码。。然后发现。。
我写线段树区间修改竟然没打标记!!!!直接就修改上了!!!最裸的线段树都不会写了!!!
Warning!Warning!Warning!
代码
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 100000 + 5;int n, m, Index;int Father[MaxN], Son[MaxN], Depth[MaxN], Top[MaxN], A[MaxN], Size[MaxN], Pos[MaxN];int Color[MaxN];struct Edge{ int v; Edge *Next;} E[MaxN * 2], *P = E, *Point[MaxN];inline void AddEdge(int x, int y) { ++P; P -> v = y; P -> Next = Point[x]; Point[x] = P;}int DFS_1(int x, int Dep, int Fa) { Depth[x] = Dep; Father[x] = Fa; Size[x] = 1; int SonSize, MaxSonSize; SonSize = MaxSonSize = 0; for (Edge *j = Point[x]; j; j = j -> Next) { if (j -> v == Fa) continue; SonSize = DFS_1(j -> v, Dep + 1, x); if (SonSize > MaxSonSize) { Son[x] = j -> v; MaxSonSize = SonSize; } Size[x] += SonSize; } return Size[x];}void DFS_2(int x) { if (x == 0) return; if (x == Son[Father[x]]) Top[x] = Top[Father[x]]; else Top[x] = x; Pos[x] = ++Index; Color[Pos[x]] = A[x]; DFS_2(Son[x]); for (Edge *j = Point[x]; j; j = j -> Next) { if (j -> v == Father[x] || j -> v == Son[x]) continue; DFS_2(j -> v); }}struct ES { int Lx, Rx, Tx; ES() {} ES(int a, int b, int c) { Lx = a; Rx = b; Tx = c; }} T[MaxN * 4], D[MaxN * 4];ES Plus(ES e1, ES e2) { ES ret; if (e1.Tx == 0) return e2; if (e2.Tx == 0) return e1; ret = ES(e1.Lx, e2.Rx, e1.Tx + e2.Tx); if (e1.Rx == e2.Lx) --ret.Tx; return ret;}inline void Update(int x) { T[x] = Plus(T[x << 1], T[x << 1 | 1]);}void Plant_Tree(int x, int s, int t) { if (s == t) { T[x] = ES(Color[s], Color[s], 1); D[x] = ES(0, 0, 0); return; } int m = (s + t) >> 1; Plant_Tree(x << 1, s, m); Plant_Tree(x << 1 | 1, m + 1, t); Update(x);}inline void Paint(int x, ES Dlt) { T[x] = Dlt; D[x] = Dlt;}inline void PushDown(int x) { if (D[x].Tx == 0) return; Paint(x << 1, D[x]); Paint(x << 1 | 1, D[x]); D[x] = ES(0, 0, 0);}void Change_Tree(int x, int s, int t, int l, int r, int Col) { if (l <= s && r >= t) { ES Temp = ES(Col, Col, 1); Paint(x, Temp); return; } PushDown(x); int m = (s + t) >> 1; if (l <= m) Change_Tree(x << 1, s, m, l, r, Col); if (r >= m + 1) Change_Tree(x << 1 | 1, m + 1, t, l, r, Col); Update(x);}void Change_Color(int x, int y, int z) { int fx, fy; while (true) { fx = Top[x]; fy = Top[y]; if (Depth[fx] < Depth[fy]) { swap(fx, fy); swap(x, y); } if (fx == fy) { if (Pos[x] < Pos[y]) Change_Tree(1, 1, n, Pos[x], Pos[y], z); else Change_Tree(1, 1, n, Pos[y], Pos[x], z); break; } else { Change_Tree(1, 1, n, Pos[fx], Pos[x], z); x = Father[fx]; } }}ES Query_Tree(int x, int s, int t, int l, int r) { if (l <= s && r >= t) return T[x]; PushDown(x); int m = (s + t) >> 1; ES ret = ES(0, 0, 0); if (l <= m) ret = Plus(ret, Query_Tree(x << 1, s, m, l, r)); if (r >= m + 1) ret = Plus(ret, Query_Tree(x << 1 | 1, m + 1, t, l, r)); return ret;}int Query(int x, int y) { int fx, fy, ret; ES Ansx, Ansy, Temp; Ansx = Ansy = ES(0, 0, 0); while (true) { fx = Top[x]; fy = Top[y]; if (Depth[fx] < Depth[fy]) { swap(fx, fy); swap(x, y); swap(Ansx, Ansy); } if (fx == fy) { ret = Ansx.Tx + Ansy.Tx; if (Pos[x] < Pos[y]) { Temp = Query_Tree(1, 1, n, Pos[x], Pos[y]); ret += Temp.Tx; if (Ansy.Lx == Temp.Rx) --ret; if (Ansx.Lx == Temp.Lx) --ret; } else { Temp = Query_Tree(1, 1, n, Pos[y], Pos[x]); ret += Temp.Tx; if (Ansx.Lx == Temp.Rx) --ret; if (Ansy.Lx == Temp.Lx) --ret; } break; } else { Ansx = Plus(Query_Tree(1, 1, n, Pos[fx], Pos[x]), Ansx); x = Father[fx]; } } return ret;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); int a, b, c; for (int i = 1; i <= n - 1; ++i) { scanf("%d%d", &a, &b); AddEdge(a, b); AddEdge(b, a); } DFS_1(1, 0, 0); Index = 0; DFS_2(1); Plant_Tree(1, 1, n); char ch; int Ans; for (int i = 1; i <= m; ++i) { ch = ‘#‘; while (ch != ‘C‘ && ch != ‘Q‘) ch = getchar(); if (ch == ‘C‘) { scanf("%d%d%d", &a, &b, &c); Change_Color(a, b, c); } else { scanf("%d%d", &a, &b); Ans = Query(a, b); printf("%d\n", Ans); } } return 0;}
[BZOJ 2243] [SDOI 2011] 染色
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。