?
题意：给定n个数，由0，1构成。共有5种操作。每个操作输入3个数，op，a，b。
op == 0，将区间[a，b]赋值为0； op == 1，将区间[a，b]赋值为1； op == 2，将区间[a，b]内的01反转； op == 3，查询区间[a，b]中1的个数； op == 4，查询区间[a，b]中连续1的最大长度；
思路：区间合并 + 区间更新。每个结点存7个数：
区间内1的个数c1。 从区间左端点开始连续1的最大长度l1。 以区间右端点结束连续1的最大长度r1。 区间内连续1的最大长度m1。 从区间左端点开始连续0的最大长度l0。 以区间右端点结束连续0的最大长度r0。 区间内连续0的最大长度m0。
记录0的连续是为了反转后统计结果方便。
代码：
#include
#include
#include
#include
#include
#include
using namespace std; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 const int N = 1e5 + 10; const int INF = 0x7f7f7f7f; struct Node { int c1; int l1, r1, m1; int l0, r0, m0; Node() {} Node(int a, int b, int c, int d, int e, int f, int g) { c1 = a; l1 = b; r1 = c; m1 = d; l0 = e; r0 = f; m0 = g; } void reversal(int s) { c1 = s; swap(l1, l0); swap(r1, r0); swap(m1, m0); } }; Node node[N << 2]; int cover[N << 2]; int XOR[N << 2]; void pushup(int rt, int l, int r) { int m = (l + r) >> 1; int lenl = m - l + 1; int lenr = r - m; node[rt].c1 = node[rt << 1].c1 + node[rt << 1 | 1].c1; if (node[rt << 1].l1 == lenl) node[rt].l1 = node[rt << 1].l1 + node[rt << 1 | 1].l1; else node[rt].l1 = node[rt << 1].l1; if (node[rt << 1 | 1].r1 == lenr) node[rt].r1 = node[rt << 1 | 1].r1 + node[rt << 1].r1; else node[rt].r1 = node[rt << 1 | 1].r1; if (node[rt << 1].l0 == lenl) node[rt].l0 = node[rt << 1].l0 + node[rt << 1 | 1].l0; else node[rt].l0 = node[rt << 1].l0; if (node[rt << 1 | 1].r0 == lenr) node[rt].r0 = node[rt << 1 | 1].r0 + node[rt << 1].r0; else node[rt].r0 = node[rt << 1 | 1].r0; node[rt].m1 = max(node[rt << 1].r1 + node[rt << 1 | 1].l1, max(node[rt << 1].m1, node[rt << 1 | 1].m1)); node[rt].m0 = max(node[rt << 1].r0 + node[rt << 1 | 1].l0, max(node[rt << 1].m0, node[rt << 1 | 1].m0)); } void pushdown(int rt, int l, int r) { int m = (l + r) >> 1; int lenl = m - l + 1; int lenr = r - m; if (cover[rt] != -1) { if (cover[rt] == 1) { node[rt << 1] = Node(lenl, lenl, lenl, lenl, 0, 0, 0); node[rt << 1 | 1] = Node(lenr, lenr, lenr, lenr, 0, 0, 0); } else { node[rt << 1] = Node(0, 0, 0, 0, lenl, lenl, lenl); node[rt << 1 | 1] = Node(0, 0, 0, 0, lenr, lenr, lenr); } cover[rt << 1] = cover[rt << 1 | 1] = cover[rt]; XOR[rt << 1] = XOR[rt << 1 | 1] = 0; cover[rt] = -1; } if (XOR[rt] != 0) { node[rt << 1].reversal(lenl - node[rt << 1].c1); node[rt << 1 | 1].reversal(lenr - node[rt << 1 | 1].c1); if (cover[rt << 1] != -1) cover[rt << 1] = 1 - cover[rt << 1]; else XOR[rt << 1] = 1 - XOR[rt << 1]; if (cover[rt << 1 | 1] != -1) cover[rt << 1 | 1] = 1 - cover[rt << 1 | 1]; else XOR[rt << 1 | 1] = 1 - XOR[rt << 1 | 1]; XOR[rt] = 0; } } void build(int l, int r, int rt) { cover[rt] = -1; XOR[rt] = 0; if (l == r) { int x; scanf(%d, &x); node[rt] = Node(x, x, x, x, 1 - x, 1 - x, 1 - x); return ; } int m = (l + r) >> 1; build(lson); build(rson); pushup(rt, l, r); } void update(int op, int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { if (op == 2) { node[rt].reversal(r - l + 1 - node[rt].c1); if (cover[rt] != -1) cover[rt] = 1 - cover[rt]; else XOR[rt] = 1 - XOR[rt]; } else { node[rt] = (op == 0 ? Node(0, 0, 0, 0, r - l + 1, r - l + 1, r - l + 1) : Node(r - l + 1, r - l + 1, r - l + 1, r - l + 1, 0, 0, 0)); cover[rt] = op; XOR[rt] = 0; } return ; } pushdown(rt, l, r); int m = (l + r) >> 1; if (L <= m) update(op, L, R, lson); if (R > m) update(op, L, R, rson); pushup(rt, l, r); } Node query(int op, int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { return node[rt]; } pushdown(rt, l, r); int m = (l + r) >> 1; Node ql = Node(0, 0, 0, 0, 0, 0, 0); Node qr = Node(0, 0, 0, 0, 0, 0, 0); if (L <= m) ql = query(op, L, R, lson); if (R > m) qr = query(op, L, R, rson); pushup(rt, l, r); if (op == 3) { return Node(ql.c1 + qr.c1, 0, 0, 0, 0, 0, 0); } else { Node res = Node(0, 0, 0, 0, 0, 0, 0); res.m1 = max(ql.r1 + qr.l1, max(ql.m1, qr.m1)); if (ql.l1 == m - l + 1) res.l1 = ql.l1 + qr.l1; else res.l1 = ql.l1; if (qr.r1 == r - m) res.r1 = qr.r1 + ql.r1; else res.r1 = qr.r1; return res; } } int main() { int t_case; scanf(%d, &t_case); for (int i_case = 1; i_case <= t_case; i_case++) { int n, m; scanf(%d%d, &n, &m); build(1, n, 1); for (int i = 0; i < m; i++) { int op, a, b; scanf(%d%d%d, &op, &a, &b); a++; b++; if (op <= 2) { update(op, a, b, 1, n, 1); } else { Node res = query(op, a, b, 1, n, 1); if (op == 3) printf(%d , res.c1); else printf(%d , res.m1); } } } return 0; }
?