题目描述
AKN 觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下
- 拥有一个伤害串，是一个长度为 nnn 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符，即下标从 111 开始。
- 给定一个范围 [l, r][l,~r][l, r]，伤害为伤害串的这个范围内中字符 1 的个数
- 会修改伤害串中的数值，修改的方法是把 [l, r][l,~r][l, r] 中所有原来的字符 0 变成 1，将 1 变成 0。
AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。
输入格式
输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 nnn，和操作的个数 mmm。
输入第二行是一个长度为 nnn 的字符串 SSS，代表伤害串。
第 333 到第 (m+2)(m + 2)(m+2) 行，每行有三个用空格隔开的整数 op,l,rop, l, rop,l,r。代表第 iii 次操作的方式和区间，规则是：
- 若 op=0op = 0op=0，则表示将伤害串的 [l, r][l,~r][l, r] 区间内的 0 变成 1，1 变成 0。
- 若 op=1op = 1op=1，则表示询问伤害串的 [l, r][l,~r][l, r] 区间内有多少个字符 1。
输出格式
对于每次询问，输出一行一个整数，代表区间内 1 的个数。
输入输出样例
输入 #1 复制
10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6
输出 #1 复制
3
6
1
板子题，spread的时候右儿子少打了+1调试了半天==
这也是一道需要用到lazy tag的线段树题，不同的是lazy tag的含义。注意到对区间操作奇数次会得到翻转的区间，操作偶数次会得到原来的区间，因此设置标记为1代表对区间取反，为0代表不变。又注意到对于维护的区间内1的个数和sum，如果取反，sum可以轻松的更新为区间长度-sum，因此上述标记的定义也就顺理成章了。
#include <bits/stdc++.h> #define SIZE 200005 using namespace std; struct SegmentTree { int p; int l; int r; int sum; bool flag; //延迟标记 } t[SIZE * 4]; bool a[SIZE]; int n, m; string s; void build(int p, int l, int r) { t[p].l = l, t[p].r = r, t[p].flag = 0; if(l == r) { t[p].sum = a[l]; return; } int mid = (l + r) >> 1; build(2 * p, l, mid); build(2 * p + 1, mid + 1, r); t[p].sum = t[2 * p].sum + t[2 * p + 1].sum; } void spread(int p)//下传延迟标记 { if(t[p].flag) { t[2 * p].sum = (t[2 * p].r - t[2 * p].l + 1) - t[2 * p].sum; t[2 * p + 1].sum = (t[2 * p + 1].r - t[2 * p + 1].l + 1) - t[2 * p + 1].sum; t[2 * p].flag = 1 ^ t[2 * p].flag; t[2 * p + 1].flag = 1 ^ t[2 * p + 1].flag; t[p].flag = 0; } } void change(int p, int l, int r)//区间翻转 { if(t[p].l >= l && t[p].r <= r) { t[p].sum = (t[p].r - t[p].l + 1) - t[p].sum; t[p].flag = 1 ^ t[p].flag; return; } spread(p); int mid = (t[p].l + t[p].r) >> 1; if(l <= mid) change(2 * p, l, r); if(r > mid) change(2 * p + 1, l, r); t[p].sum = t[2 * p].sum + t[2 * p + 1].sum; } int ask(int p, int l, int r) { if(t[p].l >= l && t[p].r <= r) return t[p].sum; spread(p); int mid = (t[p].l + t[p].r) >> 1; int val = 0; if(l <= mid) val += ask(2 * p, l, r); if(r > mid) val += ask(2 * p + 1, l, r); return val; } int main() { cin >> n >> m; cin >> s; int i; for(i = 1; i <= n; i++) a[i] = s[i-1] - '0'; build(1, 1, n); for(i = 1; i <= m; i++) { int op, l ,r; scanf("%d%d%d", &op, &l, &r); if(op == 0) change(1, l, r); else cout<<ask(1, l, r)<<endl; } } //10 6 //1011101001 //0 1 4 //1 2 6