AALC001 D - Inversion Count
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- D - Inversion Count
- 難易度
- -
からなる長さ の数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l r: の転倒数を出力する。
セグメント木の各ノードに、担当区間について次の値を持たせます。
- :値 ()の個数
- :区間内の転倒数
隣り合う区間 (左)と (右)をつなげたときの転倒数は、「 の中の転倒数」「 の中の転倒数」「 と にまたがる転倒数」の和です。またがる転倒は、 の値 と の値 で となる組なので、その個数は です。
これで 2 つの区間の情報を で合成できるので、セグメント木に載せられます。全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001D { struct S { al<3> cnt; ll inv; S() : cnt{}, inv{} {} S(ll x) : cnt{}, inv{} { assert(0 <= x && x < 3); cnt[x] = 1; } }; static S op(const S &a, const S &b) { S res; res.inv = a.inv + b.inv; rep(i, 3) { res.cnt[i] = a.cnt[i] + b.cnt[i]; rep(j, i) { res.inv += a.cnt[i] * b.cnt[j]; } } return res; } static S e() { return S(); }};
void solve() { LL(N, Q); VL(A, N); vec<AALC0001D::S> init; init.reserve(N); for (ll a : A) init.push_back(a); SegTree<AALC0001D> seg(init); rep(Q) { LL(q); if (q == 1) { LL(i, x); seg.set(i - 1, x); } else if (q == 2) { LL(l, r); print(seg.prod(l - 1, r).inv); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。al<3> は std::array<ll, 3> です。
使用ライブラリ:cpp_include@402f0cf