題目鏈接：http://www.lightoj.com/volume_showproblem.php?problem=1080 被坑出翔了 ，本來(lái)剛剛學(xué)會(huì)了懶惰標(biāo)記，以為這道題也用得上懶惰標(biāo)記（每一個(gè)結(jié)點(diǎn)記錄的是區(qū)間內(nèi)1的個(gè)數(shù)，取反的話(huà)直接區(qū)間總長(zhǎng)度減去當(dāng)前權(quán)值），但是寫(xiě)完以后，debug了三個(gè)多小時(shí)都沒(méi)有成功，最后才發(fā)現(xiàn)，由于用了懶惰標(biāo)記，葉子結(jié)點(diǎn)從來(lái)沒(méi)有被更新過(guò)，當(dāng)取反偶數(shù)次，然后詢(xún)問(wèn)到某一個(gè)沒(méi)有被更新過(guò)的葉子結(jié)點(diǎn)的時(shí)候，就相當(dāng)于進(jìn)行了第一次取反，這樣一來(lái)就變成了奇數(shù)次取反，剛好相反啊親……所以最終的結(jié)果就是這個(gè)想法宣告失敗（如果不用懶惰標(biāo)記而是每次都更新到底的話(huà)就能成功……但是這會(huì)使得程序非常蛋疼，萬(wàn)一超時(shí)了呢。。一會(huì)兒寫(xiě)寫(xiě)試試） 然后我接受了一個(gè)新的想法（是的，接受。。），就是除了葉子結(jié)點(diǎn)記錄的是本身以外，其他的結(jié)點(diǎn)記錄的都是一共取了多少次反，這樣一來(lái)邊往下找邊加和最后對(duì)2取一個(gè)余數(shù)、、尼瑪。。。
  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
|