主要思路:线段树
线段树大法好
我觉得这道题就是把区间修改,区间查询的普通线段树改了改懒标记就完了
不会线段树?不着急啊,我们有入门宝典——
具体线段树入门:
Blog发完就跑
记得,这里的xor如果xor两次就相当于没操作,所以我们在维护懒标记时可以再偷点懒,每次懒标记取反。
我们区间取反时,实际上是原来是0,现在变为1,原来是1,现在变为0,他们的数目是互补的,所以区间取反后1的数目就是之前0的数目
代码:
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define go(i, j, n, k) for (int i = j; i <= n; i += k) #define fo(i, j, n, k) for (int i = j; i >= n; i -= k) #define rep(i, x) for (int i = h[x]; i; i = e[i].nxt) #define mn 222222 #define inf 2147483647 #define ll long long #define ld long double #define fi first #define se second #define root 1, n, 1 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define bson l, r, rt //#define LOCAL #define mod #define Debug(...) fprintf(stderr, __VA_ARGS__) inline int read(){ int f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } //This is AC head above... int z[mn << 2], col[mn << 2], a[mn]; inline void update(int rt){ z[rt] = z[rt << 1] + z[rt << 1 | 1]; } inline void color(int l,int r,int rt){ z[rt] = (r - l + 1) - z[rt]; col[rt] ^= 1; } inline void push_col(int l,int r,int rt){ if(col[rt]){ int m = (l + r) >> 1; color(lson); color(rson); col[rt] = 0; } } inline void build(int l,int r,int rt){ if(l==r){ z[rt] = a[l]; return; } int m = (l + r) >> 1; build(lson); build(rson); update(rt); } inline void modify(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr){ col[rt] ^= 1; z[rt] = (r - l + 1) - z[rt]; return; } int m = (l + r) >> 1; push_col(bson); if(nowl<=m) modify(lson, nowl, nowr); if(m<nowr) modify(rson, nowl, nowr); update(rt); } inline int query(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr){ return z[rt]; } int m = (l + r) >> 1; push_col(bson); if(nowl<=m){ if(m<nowr) return query(lson, nowl, nowr) + query(rson, nowl, nowr); else return query(lson, nowl, nowr); }else return query(rson, nowl, nowr); } int n, m; inline void debug(){ go(i, 1, n, 1) printf("%d ", a[i]); puts(""); } int main(){ n = read(), m = read(); string c; cin >> c; go(i, 0, n - 1, 1) a[i + 1] = c[i] - '0'; //debug(); build(root); go(i,1,m,1){ int s = read(), x = read(), y = read(); if(!s) modify(root, x, y); else cout << query(root, x, y) << "\n"; } #ifdef LOCAL Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }