------------------------------------------------------------------------------------
线段树的区间操作：修改区间内的值，反转区间内的值，区间查询；
------------------------------------------------------------------------------------
Description
维护一个只有0和1的整数序列，支持以下操作：
1 x y v : 将区间[x,y]之间的所有整数都变为v（v为0或1）；
2 x y : 将区间[x,y]之间所有的1变为0，所有的0变为1；
3 x y : 查询区间[x,y]内的1的个数。
Input
输入文件包含多组测试数据。
对于每组测试数据，第一行为一个整数N(1<=N<=10^5)，表示这个序列一共有N个整数。接下来一行有N个值为0或1的整数，分别描述了序列中的N个整数。再接下来一行有一个整数M(1<=M<=10^5)，表示一共有M个操作。
Output
对于每个查询均用一行输出查询的结果。
Sample Input
4
0 0 1 0
6
3 1 4
2 1 4
3 1 4
1 1 2 0
1 3 3 1
3 1 4
Sample Output
1
3
2
------------------------------------------------------------------------------------
# include <stdio.h> # define N 100015 # define NON 0x7fffffff int n, m, num[N]; int ones[4 * N], set[4 * N], rev[4 * N]; void update(int r) { ones[r] = ones[r << 1] + ones[(r << 1) | 1]; } void pushdown(int r, int x, int y) { int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1; if (set[r] != NON) { rev[ls] = rev[rs] = 0; set[ls] = set[rs] = set[r], set[r] = NON; ones[ls] = (mid-x+1) * set[ls]; ones[rs] = (y-mid) * set[rs]; } if (rev[r]) { rev[ls] ^= 1; rev[rs] ^= 1; ones[ls] = mid-x+1 - ones[ls]; ones[rs] = y - mid - ones[rs]; rev[r] = 0; } } void build(int r, int x, int y) { set[r] = NON, rev[r] = 0; if (x == y) { ones[r] = num[x]; return ; } int mid = (x + y) >> 1, ls = r << 1, rs = (r << 1) | 1; build(ls, x, mid); build(rs, mid+1, y); update(r); } void change(int r, int x, int y, int s, int t, int val) { if (s<=x && y<=t) { ones[r] = (y-x+1) * val; set[r] = val; rev[r] = 0; return ; } pushdown(r, x, y); int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1; if (s <= mid) change(ls, x, mid, s, t, val); if (mid+1 <= t) change(rs, mid+1, y, s, t, val); update(r); } void flip(int r, int x, int y, int s, int t) { if (s<=x && y<=t) { rev[r] ^= 1; ones[r] = y-x+1 - ones[r]; return ; } pushdown(r, x, y); int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1; if (s <= mid) flip(ls, x, mid, s, t); if (mid+1 <= t) flip(rs, mid+1, y, s, t); update(r); } void query(int r, int x, int y, int s, int t, int &ans) { if (s<=x && y<=t) { ans += ones[r]; return ; } pushdown(r, x, y); int mid = (x+y) >> 1, ls = r << 1, rs = (r << 1) | 1; if (s <= mid) query(ls, x, mid, s, t, ans); if (mid+1 <= t) query(rs, mid+1, y, s, t, ans); } void init(void) { for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } scanf("%d", &m); build(1, 1, n); } void solve(void) { int id, val, s, t, ans; for (int i = 1; i <= m; ++i) { scanf("%d", &id); switch(id) { case 1: {scanf("%d%d%d", &s, &t, &val); change(1, 1, n, s, t, val); break;} case 2: {scanf("%d%d", &s, &t); flip(1, 1, n, s, t); break;} case 3: {scanf("%d%d", &s, &t); ans = 0; query(1, 1, n, s, t, ans); printf("%d\n", ans); break;} } } return ; } int main() { while (~scanf("%d", &n)) { init(); solve(); } return 0; }