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 <bits/stdc++.h>
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;
}