AtCoder 265G 线段树

题意

传送门 AtCoder 265G 012 Inversion

题解

直接维护逆序对数量比较困难，考虑到元素值域很小，直接将不同数值对解耦进行维护。具体而言，线段树维护区间 $0,1,2$ 的数量，以及满足 $i<j$ 时 $a[i]=x,a[j]=1$ 的数对数量 $num[x][y]$。总时间复杂度 $O(d^{2}n\log n)$，其中，$d$ 是数组取值的规模。

#include 
using namespace std;
using ll = long long;
struct ST {
    struct LzNode {
        vector<int> p;
        LzNode() : p(3) {
            reset();
        }
        void reset() {
            iota(p.begin(), p.end(), 0);
        }
        void update(vector<int> &f) {
            vector<int> tmp(3);
            for (int i = 0; i < 3; ++i) {
                tmp[i] = f[p[i]];
            }
            swap(tmp, p);
        }
    };
    struct Node {
        vector<int> cnt;
        vector<vector<ll>> num;
        Node() : cnt(3), num(3, vector<ll>(3)) {}
        Node operator+(const Node &o) {
            Node res;
            for (int i = 0; i < 3; ++i) {
                res.cnt[i] = cnt[i] + o.cnt[i];
            }
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    res.num[i][j] = num[i][j] + o.num[i][j];
                }
            }
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    res.num[i][j] += (ll)cnt[i] * o.cnt[j];
                }
            }
            return res;
        }
        void update(vector<int> &p) {
            Node res;
            for (int i = 0; i < 3; ++i) {
                res.cnt[p[i]] += cnt[i];
            }
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    res.num[p[i]][p[j]] += num[i][j];
                }
            }
            swap(*this, res);
        }
    };
    vector<Node> dat;
    vector<LzNode> lz;
    ST(vector<int> &a) {
        int n = a.size();
        int k = 1;
        while (k < n) {
            k *= 2;
        }
        k *= 2;
        dat = vector<Node>(k);
        lz = vector<LzNode>(k);
        function<void(int, int, int)> init = [&](int p, int l, int r) {
            if (r - l == 1) {
                dat[p].cnt[a[l]] += 1;
                return;
            }
            int m = (l + r) / 2;
            int chl = p * 2 + 1, chr = p * 2 + 2;
            init(chl, l, m);
            init(chr, m, r);
            dat[p] = dat[chl] + dat[chr];
        };
        init(0, 0, n);
    }
    void pushdown(int p, int l, int r) {
        int chl = p * 2 + 1, chr = p * 2 + 2;
        auto &f = lz[p].p;
        lz[chl].update(f);
        lz[chr].update(f);
        dat[chl].update(f);
        dat[chr].update(f);
        lz[p].reset();
    }
    void change(int a, int b, vector<int> &f, int p, int l, int r) {
        if (r <= a || b <= l) {
            return;
        }
        if (a <= l && r <= b) {
            lz[p].update(f);
            dat[p].update(f);
            return;
        }
        int m = (l + r) / 2;
        int chl = p * 2 + 1, chr = p * 2 + 2;
        pushdown(p, l, r);
        change(a, b, f, chl, l, m);
        change(a, b, f, chr, m, r);
        dat[p] = dat[chl] + dat[chr];
    }
    Node query(int a, int b, int p, int l, int r) {
        if (r <= a || b <= l) {
            return Node();
        }
        if (a <= l && r <= b) {
            return dat[p];
        }
        int m = (l + r) / 2;
        int chl = p * 2 + 1, chr = p * 2 + 2;
        pushdown(p, l, r);
        return query(a, b, chl, l, m) + query(a, b, chr, m, r);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ST tr(a);
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            l -= 1;
            auto nd = tr.query(l, r, 0, 0, n);
            ll res = 0;
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < i; ++j) {
                    res += nd.num[i][j];
                }
            }
            cout << res << '\n';
        } else {
            int l, r;
            vector<int> b(3);
            cin >> l >> r;
            l -= 1;
            for (int i = 0; i < 3; ++i) {
                cin >> b[i];
            }
            tr.change(l, r, b, 0, 0, n);
        }
    }

    return 0;
}
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156