This question has done quite feeling ... as if the tree line is always flexible, but I think it should also be the rule-based allocation of gvim to write their own, feeling pretty good this time also learned a little bit tricky is infinite WA violence can write a program on the beat, This question is though can not step by step for tracking data, but this is still on the beat inspired me a lot

Segment tree cover should be recorded that the current node to overwrite, and then the type of coverage or Trilogy: distribution of information before entering the child nodes, recursively call the child node, merging information from a child node to return

/* * Author: rush * Created Time: 2010 Last 01 Day Saturday 15 Seventeen 10 Seconds * File Name: icpc/hdu/3397.cpp */ #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using std::swap; using std::max; int max3(int a, int b, int c) { return max(a, max(b, c)); } int max4(int a, int b, int c, int d) { return max(a, max3(b, c, d)); } const int size = 100000 + 5; struct node_t { int L0, M0, R0; int L1, M1, R1; int ONE; int range; int cover; // The coverage (-1 Is not covered, 0, 1, 2 as ) void reset(const int _r) { range = _r; L0 = M0 = R0 = range; L1 = M1 = R1 = 0; ONE = 0; } void perform(int op) { switch (op) { case 0: L0 = M0 = R0 = range; L1 = M1 = R1 = 0; ONE = 0; cover = 0; break; case 1: L0 = M0 = R0 = 0; L1 = M1 = R1 = range; ONE = range; cover = 1; break; case 2: swap(L0, L1), swap(M0, M1), swap(R0, R1); ONE = range - ONE; // Here is the key, according to the coverage of prior to determine the coverage of now , // In fact, for case 0 and case 1 Also has this problem, but because it is directly alter the final value is 0 Or 1, // As opposed to case 2 such changes according to the situation before , So there is no such points processing switch (cover) { case -1: cover = 2; break; case 0: cover = 1; break; case 1: cover = 0; break; case 2: cover = -1; break; } break; } } } tree[size * 3]; int n, m; void plant(int low, int high, int node) { tree[node].reset(high - low + 1); tree[node].cover = -1; int mid = (low + high) / 2; // low < high Just to be able to handle [x, x] The interval ( That is, for a single point of interval ) if (low < high) { plant(low, mid, node * 2); plant(mid + 1, high, node * 2 + 1); } } int left, right; void update(int low, int high, int node, int op) { if (left <= low && high <= right) { tree[node].perform(op); } else if (left <= high && low <= right) { int mid = (low + high) / 2; // Before entering the recursive, if the current node to be overwritten , It is passed to the child node if (tree[node].cover != -1) { tree[node * 2].perform(tree[node].cover); tree[node * 2 + 1].perform(tree[node].cover); tree[node].cover = -1; } // Recursive calls around the child nodes, do not judge here low < high Because if there is a single-point interval , // The point is this function of the first if taking into account the update(low, mid, node * 2, op); update(mid + 1, high, node * 2 + 1, op); // The child nodes from the left and right back, update parent node information node_t &pnt = tree[node], &lch = tree[node * 2], &rch = tree[node * 2 + 1]; pnt.L0 = lch.L0 + (lch.L0 == lch.range ? rch.L0 : 0); pnt.M0 = max3(lch.M0, lch.R0 + rch.L0, rch.M0); pnt.R0 = rch.R0 + (rch.R0 == rch.range ? lch.R0 : 0); pnt.L1 = lch.L1 + (lch.L1 == lch.range ? rch.L1 : 0); pnt.M1 = max3(lch.M1, lch.R1 + rch.L1, rch.M1); pnt.R1 = rch.R1 + (rch.R1 == rch.range ? lch.R1 : 0); pnt.ONE = lch.ONE + rch.ONE; } } // In fact, only need to record the interval was asked into which 2 * log n Subinterval. , // So it is not normal practice, but like me they're marked the same is true of the int a[32 * 2], la; void query(int low, int high, int node) { if (left <= low && high <= right) { a[la++] = node; } else if (left <= high && low <= right) { int mid = (low + high) / 2; // The query is also required when the parent node information passed to the child node , // This is because the previous update function can only be guaranteed from 2*logn Subinterval to information is correct // The update does not do ( If you have done is to index the complexity of the ) if (tree[node].cover != -1) { tree[node * 2].perform(tree[node].cover); tree[node * 2 + 1].perform(tree[node].cover); tree[node].cover = -1; } query(low, mid, node * 2); query(mid + 1, high, node * 2 + 1); } } int main() { freopen("data.in", "r", stdin); freopen("my.out", "w", stdout); int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); plant(0, n - 1, 1); int t; for (int i = 0; i < n; ++i) { scanf("%d", &t); left = right = i; update(0, n - 1, 1, t); } for (int i = 0; i < m; ++i) { scanf("%d%d%d", &t, &left, &right); if (t < 3) { update(0, n - 1, 1, t); } else { la = 0; query(0, n - 1, 1); if (t == 3) { int ans3 = 0; for (int j = 0; j < la; ++j) ans3 += tree[a[j]].ONE; printf("%d\n", ans3); } else { int ans4 = 0; for (int j = 0; j < la; ++j) ans4 = max(ans4, tree[a[j]].M1); int tmp = 0; for (int j = 0; j < la; ++j) if (tree[a[j]].ONE == tree[a[j]].range) { tmp += tree[a[j]].range; } else { tmp += tree[a[j]].L1; ans4 = max(ans4, tmp); tmp = tree[a[j]].R1; } ans4 = max(ans4, tmp); printf("%d\n", ans4); } } } } return 0; }