题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1080 被坑出翔了 ，本来刚刚学会了懒惰标记，以为这道题也用得上懒惰标记（每一个结点记录的是区间内1的个数，取反的话直接区间总长度减去当前权值），但是写完以后，debug了三个多小时都没有成功，最后才发现，由于用了懒惰标记，叶子结点从来没有被更新过，当取反偶数次，然后询问到某一个没有被更新过的叶子结点的时候，就相当于进行了第一次取反，这样一来就变成了奇数次取反，刚好相反啊亲……所以最终的结果就是这个想法宣告失败（如果不用懒惰标记而是每次都更新到底的话就能成功……但是这会使得程序非常蛋疼，万一超时了呢。。一会儿写写试试） 然后我接受了一个新的想法（是的，接受。。），就是除了叶子结点记录的是本身以外，其他的结点记录的都是一共取了多少次反，这样一来边往下找边加和最后对2取一个余数、、尼玛。。。
  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
|