「TJOI2018」数学计算 - 线段树

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

小豆现在有一个数 \(x\) ，初始值为 \(1\) 。 小豆有 \(Q\) 次操作，操作有两种类型:

  • 1 m： \(x = x \times m\) ，输出 \(x \bmod M\) ；

  • 2 pos： \(x = x /\) 第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），输出 \(x\bmod M\) 。

解题思路

这道题由于 \(M\) 不一定是质数，我们无法用逆元解。于是我们可以将乘的数都存起来。

我们可以开一颗线段树，对于第 \(i\) 次询问：

  • 类型 \(1\)：在线段树第 \(i\) 点赋值为 \(m\)；
  • 类型 \(2\)：在线段树第 \(\text{pos}\) 点赋值为 \(1\)。

线段树维护区间乘积，每次操作输出整颗线段树的乘积即可。

代码演示

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
#include <cstdio>

const int MAXN = 1e5;

int Q, M;

struct SegT {
    int l, r;
    SegT *lc, *rc;
    long long val;

    SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), val(1) {}

    void update(const int pos, const long long delta) {
        if (pos > this->r || pos < this->l) return;
        else if (pos == this->l && pos == this->r) val = delta;
        else {
            lc->update(pos, delta);
            rc->update(pos, delta);
            val = lc->val * rc->val % M;
        }
    }

    long long query(const int l, const int r) {
        if (l > this->r || r < this->l) return 1;
        else if (l <= this->l && r >= this->r) return val;
        else return lc->query(l, r) * rc->query(l, r) % M;
    }

    static SegT *build(const int l, const int r) {
        if (l > r) return nullptr;
        else if (l == r) return new SegT(l, r, nullptr, nullptr);
        else {
            const int mid = l + (r - l) / 2;
            return new SegT(l, r, build(l, mid), build(mid + 1, r));
        }
    }
} *segment;

int main() {
    int t;

    scanf("%d", &t);

    while (t--) {
        scanf("%d %d", &Q, &M);

        segment = SegT::build(1, Q);

        for (int i = 1; i <= Q; i++) {
            int op;
            long long m;
            scanf("%d %lld", &op, &m);

            if (op == 1) segment->update(i, m);
            else if (op == 2) segment->update(m, 1);

            printf("%lld\n", segment->query(1, Q));
        }
    }

    return 0;
}