两年前就在为写线段树苦恼，两年后居然还在被线段树困扰！！于是在这个被 bct 出的超绝 1 数据结构 + 3 DP（含 2 期望）的模拟赛整疯的一天，我决定进行线段树专练。

题单链接：线段树练习

P5057 [CQOI2006] 简单题

题目链接

题意简述

数组 $a$ 为布尔类型，有 $n$ 个元素，初始全为 $0$ ，进行 $m$ 次下列任一操作，输出操作 2 的结果：

  1. 让其中一段连续序列数字反转。
  2. 询问某个元素的值。

练习过程

对照着自己之前 P3372 的代码写，考虑主要是把计算改成 ^1 的操作，有下面几个问题不是很清楚：

  1. 需不需要 lazy 。
  2. 非叶子节点的 data 内应填什么值。
  3. 需不需要 pushup。
  4. query 应返回什么值。

所以先凭着感觉走了。。。

第一版 CODE 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int N = 1e5 + 29;

int n, m, k;
int a[N];
struct tree {
    int l, r;
    int data;
} tr[N << 2];

void pushdown(int u) {
    if (!tr[u].data) return;
    tr[u << 1].data ^= 1;
    tr[u << 1 | 1].data ^= 1;
}

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) tr[u].data = 0;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return;
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].data ^= 1;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, mid);
    if (r > mid) modify(u << 1 | 1, mid + 1, r);
}

void query(int u, int x) {
    if (u == x) return;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) query(u << 1, x);
    else query(u << 1 | 1, x);
}

void tbcsolve() {
    cin >> n >> m;
    build(1, 1, n);
    rep (i, 1, m) {
        int t; cin >> t;
        if (t == 1) {
            int l, r; cin >> l >> r;
            modify(1, l, r);
        }
        else {
            int x; cin >> x;
            query(1, x);
            cout << tr[x].data << endl;
        }
    }
}

但是注意到此代码是没有输出的……

经过编译运行发现代码卡在了 build 时，静态查错发现是 l == r 时没有 return。

`build` 更正 
1
2
3
4
5
6
7
8
9
void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].data = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

但是仍然没有输出……此处进行 1 操作没有问题，卡在了 query。

debug 发现在 pushdown 的时候存在异常，但是没看出来是什么问题，于是求助了万能的 hm2ns，发现是我判的太阴间导致对叶子节点 pushdown 了。

好吧是我的 query 实在是写的太阴间了……

`query` 更正 
1
2
3
4
5
6
7
bool query(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].data;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) return query(u << 1, x);
    else return query(u << 1 | 1, x);
}

超级好消息：跑出结果啦！！！

But 这跑的也不对啊……

调了四个多小时……终于发现了……

是这个 modify 里面的递归，l 和 r 要原封不动地放进去递归。

但是 sheep32768 说我之前那样写也没什么问题。可改了之后就过了……

其实我也不理解为什么不能用 mid

`modify` 更正 
1
2
3
4
5
6
7
8
9
10
11
void modify(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return;
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].data ^= 1;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r);
    if (r > mid) modify(u << 1 | 1, l, r);
}

AC 记录

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const int N = 1e5 + 29;

int n, m, k;
int a[N];
struct tree {
    int l, r;
    int data;
} tr[N << 2];

void pushdown(int u) {
    if (!tr[u].data) return;
    tr[u << 1].data ^= 1;
    tr[u << 1 | 1].data ^= 1;
    tr[u].data = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].data = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return;
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].data ^= 1;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r);
    if (r > mid) modify(u << 1 | 1, l, r);
}

bool query(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].data;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) return query(u << 1, x);
    else return query(u << 1 | 1, x);
}

void tbcsolve() {
    cin >> n >> m;
    build(1, 1, n);
    rep (i, 1, m) {
        int t; cin >> t;
        if (t == 1) {
            int l, r; cin >> l >> r;
            modify(1, l, r);
        }
        else {
            int x; cin >> x;
            cout << query(1, x) << endl;
        }
    }
}

P4588 [TJOI2018] 数学计算

题目链接

题意简述

有一个数 $x$ ，进行 $Q$ 次操作，操作有两种类型：

  1. 1 m ：将 $x$ 的值乘上 $m$ ，并输出 $x \mod M$
  2. 2 pos ：将 $x$ 的值除以第 $pos$ 次操作所乘的值，并输出 $x \mod M$

练习过程

一开始并没看出来是线段树，经过一段时间的思考和猜测之后有了思路：

将每次 1 操作作为叶子节点的值，那么根节点即为 $x$ 的值；

对于 2 操作只需把 $pos$ 位置上的值改成 1 即可。

很幸运第一个代码就顺利通过了样例：

第一版也是最后一版 code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
const int N = 1e5 + 29;

int q, mod;
struct tree {
    int l, r;
    int data;
} tr[N << 2];

void pushup(int u) {
    tr[u].data = tr[u << 1].data * tr[u << 1 | 1].data % mod;
}

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].data = 1;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, int k) {
    if (tr[u].l == tr[u].r) {
        tr[u].data = k % mod;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(u << 1, x, k);
    else modify(u << 1 | 1, x, k);
    pushup(u);
}

void query(int u, int pos) {
    if (tr[u].l == tr[u].r) {
        tr[u].data = 1;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (pos <= mid) query(u << 1, pos);
    else query(u << 1 | 1, pos);
    pushup(u);
}

void tbcsolve() {
    cin >> q >> mod;
    build(1, 1, q);
    rep(i, 1, q) {
        int op; cin >> op;
        if (op == 1) {
            int x; cin >> x;
            modify(1, i, x);
            cout << tr[1].data % mod << endl;
        }
        else {
            int pos; cin >> pos;
            query(1, pos);
            cout << tr[1].data % mod << endl;
        }
    }
}

signed main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int Trubiacy_ = 1;
    cin >> Trubiacy_;
    while (Trubiacy_--) {
        tbcsolve();
    }
    return 0;
}

啊啊啊？！！这居然就过了？！！【震惊.jpg

AC 记录

AC 代码

如上。