题目链接：
题目分析
这道题..是我悲伤的回忆..
线段树维护连通性，与 BZOJ-1018 类似，然而我省选之前并没有做过 1018，即使它在 ProblemSet 的第一页。
更悲伤的是，这道题有 40 分的暴力分，写个 Kruskal 就可以得到，然而我写了个更快的 DP 。
这本来没有什么问题，然而我的 DP 转移少些了一种情况，于是...爆零。没错，省选前20名可能就我没有得到这 40 分？
不想再多说什么了...希望以后不要再这样 SB 了，如果以后还有机会的话。
还是来说这道题吧。
首先 Orz lzr 神犇，我写的是他的做法。
对于一段区间，我们只需要知道它四个角上的四个格点之间的连通性就可以了，一共有 10 种可能的情况，然而这 10 种情况里有一些是同一种类的，于是可以分为 5 种。
然后注意划分区间的时候是选图中的红色格子，而不是选用题目直接描述的黑色格子。即长度为 1 的区间其实包含了 2 * 2 的 4 个格点。
这样的好处是，非常好写！用两个子区间合成一个新区间的答案时，左区间的右端点和右区间的左端点其实是同一列格点，是重合的，无缝对接，所以只要两端区间的联通状态确定了，整个区间的联通状态也就确定了。
不像另一种做法，还要考虑合并时中间的连边情况，非常非常非常复杂。
这样合并最多就 5 * 5 = 25 种，实际上有些合并是不合法的，最后只有 17 种合并。将它们手动写到一个表里就好了。
然后用线段树维护就好了，当修改一条竖边的边权时，相邻的两个格子都要重新计算。
代码
#include#include #include #include #include #include using namespace std;inline void Read(int &Num){ char c = getchar(); bool Neg = false; while (c < '0' || c > '9') { if (c == '-') Neg = true; c = getchar(); } Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); } if (Neg) Num = -Num;}inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;}const int MaxN = 60000 + 5, INF = 999999999;const int Magic[20][5] = { {1, 1, 1}, {1, 2, 2}, {1, 3, 3}, {1, 4, 4}, {1, 5, 5}, {2, 1, 2}, {2, 3, 2}, {2, 5, 4}, {3, 1, 3}, {3, 3, 3}, {3, 5, 5}, {4, 1, 4}, {4, 2, 2}, {4, 4, 4}, {5, 1, 5}, {5, 2, 3}, {5, 4, 5}};int n, m;int A[MaxN][3];struct ES{ int X[6];} T[MaxN * 4];ES operator + (ES e1, ES e2){ ES ret; for (int i = 1; i <= 5; ++i) ret.X[i] = INF; for (int i = 0; i < 17; ++i) ret.X[Magic[i][2]] = gmin(ret.X[Magic[i][2]], e1.X[Magic[i][0]] + e2.X[Magic[i][1]]); return ret;}ES Calc(int s){ ES ret; ret.X[1] = A[s][1] + A[s][2]; ret.X[2] = A[s][1] + A[s][2] + A[s][0] + A[s + 1][0] - gmax(gmax(A[s][1], A[s][2]), gmax(A[s][0], A[s + 1][0])); ret.X[3] = A[s + 1][0] + gmin(A[s][1], A[s][2]); ret.X[4] = A[s][0] + gmin(A[s][1], A[s][2]); ret.X[5] = gmin(A[s][1], A[s][2]); return ret;}void Build(int x, int s, int t){ if (s == t) { T[x] = Calc(s); return; } int m = (s + t) >> 1; Build(x << 1, s, m); Build(x << 1 | 1, m + 1, t); T[x] = T[x << 1] + T[x << 1 | 1];}void Change(int x, int s, int t, int Pos){ if (s == t) { T[x] = Calc(s); return; } int m = (s + t) >> 1; if (Pos <= m) Change(x << 1, s, m, Pos); else Change(x << 1 | 1, m + 1, t, Pos); T[x] = T[x << 1] + T[x << 1 | 1];}ES Get(int x, int s, int t, int l, int r){ if (l <= s && r >= t) return T[x]; int m = (s + t) >> 1; ES ret; if (r <= m) ret = Get(x << 1, s, m, l, r); else if (l >= m + 1) ret = Get(x << 1 | 1, m + 1, t, l, r); else ret = Get(x << 1, s, m, l, r) + Get(x << 1 | 1, m + 1, t, l, r); return ret;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n - 1; ++i) Read(A[i][1]); for (int i = 1; i <= n - 1; ++i) Read(A[i][2]); for (int i = 1; i <= n; ++i) Read(A[i][0]); Build(1, 1, n - 1); char Str[3]; ES Ans; int x, y, xx, yy, Num, l, r; for (int i = 1; i <= m; ++i) { scanf("%s", Str); if (Str[0] == 'C') { Read(x); Read(y); Read(xx); Read(yy); Read(Num); if (x == xx) { A[gmin(y, yy)][x] = Num; Change(1, 1, n - 1, gmin(y, yy)); } else { A[y][0] = Num; if (y != 1) Change(1, 1, n - 1, y - 1); if (y != n) Change(1, 1, n - 1, y); } } else { Read(l); Read(r); if (l == r) printf("%d\n", A[l][0]); else { Ans = Get(1, 1, n - 1, l, r - 1); printf("%d\n", Ans.X[2]); } } } return 0;}