コンテンツにスキップ

AALC001 D - Inversion Count

サイト
AtCoder
コンテスト
AALC001
問題
D - Inversion Count
難易度
-

0,1,20, 1, 2 からなる長さ NN の数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) の転倒数を出力する。

セグメント木の各ノードに、担当区間について次の値を持たせます。

  • cntv\mathrm{cnt}_v:値 vv(v=0,1,2v = 0, 1, 2)の個数
  • inv\mathrm{inv}:区間内の転倒数

隣り合う区間 XX(左)と YY(右)をつなげたときの転倒数は、「XX の中の転倒数」「YY の中の転倒数」「XX と YY にまたがる転倒数」の和です。またがる転倒は、XX の値 ii と YY の値 jj で i>ji > j となる組なので、その個数は ∑i>jcntiX cntjY\sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j です。

invXY=invX+invY+∑i>jcntiX cntjY\mathrm{inv}^{XY} = \mathrm{inv}^X + \mathrm{inv}^Y + \sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j

これで 2 つの区間の情報を O(1)O(1) で合成できるので、セグメント木に載せられます。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

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