ABC265G. 012 Inversion
延迟线段树
每个点需要维护以下信息：
- \(0/1/2\) 的个数
- 有序对 \((0, 0)\), \((0, 1)\), \((0, 2)\)，\((1, 0)\)，\((1, 1)\)，\((1, 2)\)，\((2, 0)\)，\((2, 1)\)，\((2, 2)\) 的个数
对于操作二其实就是延迟线段树里的函数 \(F\)
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
struct S {
array<int, 3> c;
array<array<ll, 3>, 3> d;
S() {
fill(c.begin(), c.end(), 0);
rep(i, 3)rep(j, 3) d[i][j] = 0;
}
};
S op(S a, S b) {
rep(i, 3)rep(j, 3) {
a.d[i][j] += b.d[i][j];
a.d[i][j] += (ll)a.c[i]*b.c[j];
}
rep(i, 3) a.c[i] += b.c[i];
return a;
}
S e() { return S(); }
struct F {
array<int, 3> a;
F(): a({0, 1, 2}) {}
};
S mapping(F f, S x) {
S res;
rep(i, 3)rep(j, 3) {
res.d[f.a[i]][f.a[j]] += x.d[i][j];
}
rep(i, 3) res.c[f.a[i]] += x.c[i];
return res;
}
F comp(F f2, F f1) {
rep(i, 3) f1.a[i] = f2.a[f1.a[i]];
return f1;
}
F id() { return F(); }
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
rep(i, n) cin >> a[i];
lazy_segtree<S, op, e, F, mapping, comp, id> t(n);
rep(i, n) {
S s;
s.c[a[i]] = 1;
t.set(i, s);
}
rep(qi, q) {
int type, l, r;
cin >> type >> l >> r;
--l;
if (type == 1) {
S s = t.prod(l, r);
ll ans = s.d[1][0] + s.d[2][0] + s.d[2][1];
cout << ans << '\n';
}
else {
F f;
rep(i, 3) cin >> f.a[i];
t.apply(l, r, f);
}
}
return 0;
}