CPTH/tests/SegmentTree/SegmentTree.cpp at master · ouuan/CPTH · GitHub

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
72
73
74
75
76
77
78
79
80
81
82
83
#include "../../headers/SegmentTree.h"

#include <iostream>

using namespace std;
using namespace CPTH;

typedef long long ll;

int n, m, p;

struct Modification
{
    int add, mul;
    Modification(int _add = 0, int _mul = 1)
    {
        add = _add;
        mul = _mul;
    }
    void operator+=(const Modification &y)
    {
        add = ((ll)add * y.mul + y.add) % p;
        mul = (ll)mul * y.mul % p;
    }
};

void update(SegmentTreeNode<int, Modification> &node, const Modification &mod)
{
    node.val = ((ll)node.val * mod.mul + (ll)mod.add * (node.right - node.left)) % p;
    node.mod += mod;
}

int main()
{
    cin >> n >> m >> p;

    vector<int> a(n);
    for (auto &x : a)
    {
        cin >> x;
        x %= p;
    }

    SegmentTree<int, Modification> t(
        a,
        [](int x, int y) {
            return (x + y) % p;
        },
        update);

    while (m--)
    {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1)
        {
            int x;
            cin >> x;
            if (l == r)
                t.modify(l, {0, x});
            else
                t.modify(l, r + 1, {0, x});
        }
        else if (opt == 2)
        {
            int x;
            cin >> x;
            if (l == r)
                t.modify(l, {x, 1});
            else
                t.modify(l, r + 1, {x, 1});
        }
        else
        {
            if (l == r)
                cout << t.query(l) << endl;
            else
                cout << t.query(l, r + 1) << endl;
        }
    }

    return 0;
}