题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1080 被坑出翔了 ,本来刚刚学会了懒惰标记,以为这道题也用得上懒惰标记(每一个结点记录的是区间内1的个数,取反的话直接区间总长度减去当前权值),但是写完以后,debug了三个多小时都没有成功,最后才发现,由于用了懒惰标记,叶子结点从来没有被更新过,当取反偶数次,然后询问到某一个没有被更新过的叶子结点的时候,就相当于进行了第一次取反,这样一来就变成了奇数次取反,刚好相反啊亲……所以最终的结果就是这个想法宣告失败(如果不用懒惰标记而是每次都更新到底的话就能成功……但是这会使得程序非常蛋疼,万一超时了呢。。一会儿写写试试) 然后我接受了一个新的想法(是的,接受。。),就是除了叶子结点记录的是本身以外,其他的结点记录的都是一共取了多少次反,这样一来边往下找边加和最后对2取一个余数、、尼玛。。。
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define lson l, m, rt << 1 9 #define rson m + 1, r, rt << 1 | 1 10 const int maxn = 100010; 11 char s[maxn]; 12 int sum[maxn << 2]; 13 void build(int l, int r, int rt) 14 { 15 if (l == r) 16 { 17 sum[rt] = s[l - 1] - '0'; 18 return; 19 } 20 sum[rt] = 0; 21 int m = (l + r) >> 1; 22 build(lson); 23 build(rson); 24 } 25 void update(int ll, int rr, int l, int r, int rt) 26 { 27 if (ll <= l && rr >= r) 28 { 29 sum[rt]++; 30 return; 31 } 32 int m = (l + r) >> 1; 33 if (ll <= m) update(ll, rr, lson); 34 if (rr > m) update(ll, rr, rson); 35 } 36 void query(int p, int v, int l, int r, int rt) 37 { 38 v += sum[rt]; 39 if (l == r) 40 { 41 printf("%d\n", v % 2); 42 return; 43 } 44 int m = (l + r) >> 1; 45 if (p <= m) query(p, v, lson); 46 else query(p, v, rson); 47 } 48 int main() 49 { 50 int t; 51 scanf("%d", &t); 52 for (int i = 1; i <= t; i++) 53 { 54 printf("Case %d:\n", i); 55 scanf("%s", s); 56 int n = strlen(s); 57 build(1, n, 1); 58 int m; scanf("%d", &m); 59 char c[2]; 60 while (m--) 61 { 62 scanf("%s", c); 63 if (c[0] == 'I') 64 { 65 int x, y; 66 scanf("%d%d", &x, &y); 67 update(x, y, 1, n, 1); 68 } 69 if (c[0] == 'Q') 70 { 71 int x; 72 scanf("%d", &x); 73 query(x, 0, 1, n, 1); 74 } 75 } 76 } 77 return 0; 78
|