コンテンツにスキップ

AALC001 K - Multiset

サイト
AtCoder
コンテスト
AALC001
問題
K - Multiset
難易度
-

はじめ NN 個の要素 A1,…,ANA_1, \dots, A_N をもつ整数の多重集合 SS に対して、次の 3 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5, 0≤Ai,x≤1090 \le A_i, x \le 10^9)。

  • 1 x:SS に xx を 1 個追加する。
  • 2 x:SS から xx を 1 個削除する(xx が含まれることは保証される)。
  • 3:SS の要素を昇順に並べた列を x1,…,xkx_1, \dots, x_k として、∑i=1kixi\sum_{i=1}^{k} i x_i を 998244353998244353 で割った余りを出力する。

クエリを先読みして、現れる値を座標圧縮します。値ごとに、その値の要素の「値の和 uu」と「(順位)×(値)の和 ww」を管理すると、答えは ww の総和です。同じ値の要素どうしは、どの順に並べても ∑ixi\sum i x_i は変わりません。そのため、同じ値の要素の中での順番は自由に決めてよいです。

値 xx を追加するとき、xx は同じ値の要素の中で先頭に入れることにします。すると、

  • xx 以上の値の要素(同じ値の要素も含む)は順位が 1 つずつ増えるので、それぞれの値について ww が uu だけ増えます。
  • 追加した要素の順位は「xx 未満の要素の個数 +1+ 1」なので、値 xx の uu に xx、ww に(順位)×x\times x を足します。

削除は逆で、同じ値の要素の中の先頭を取り除くことにします。xx 以上の値の ww から uu を引き、値 xx の uu から xx、ww から「xx 未満の要素の個数」×x\times x を引きます。ここでの順位は、全体の順位を 1 つ下げた後の値です。

「xx 以上の値すべての ww に c⋅uc \cdot u を足す」は区間への作用です。そのため、値ごとの (u,w)(u, w) を遅延評価セグメント木で管理します。作用 cc は (u,w)↦(u,w+cu)(u, w) \mapsto (u, w + c u) で、合成は和です。xx 未満の要素の個数は、値ごとの個数を持つ別のセグメント木で求めます。

全体の計算量は O((N+Q)log⁡(N+Q))O((N + Q) \log (N + Q)) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/utility/compress.hpp"
using mint = modint998244353;
struct AALC0001K {
struct S {
mint u, v;
S() : u{}, v{} {}
};
using F = mint;
static S op(const S &a, const S &b) {
S res;
res.u = a.u + b.u;
res.v = a.v + b.v;
return res;
}
static S e() { return S(); }
static S mapping(const F &f, const S &x) {
S res;
res.u = x.u;
res.v = x.u * f + x.v;
return res;
}
static F composition(const F &f, const F &g) { return f + g; }
static F id() { return 0; }
};
void solve() {
LL(N, Q);
VL(A, N);
Compress<ll> cp;
for (ll a : A)
cp.add(a);
val<2> query;
query.reserve(Q);
rep(Q) {
LL(q);
if (q <= 2) {
LL(x);
query.push_back({q, x});
cp.add(x);
} else {
query.push_back({q, 0});
}
}
cp.build();
RSumQ<ll> seg0(cp.size());
LazySegTree<AALC0001K> seg1(cp.size());
for (ll a : A) {
ll k = cp.id(a);
seg1.apply(k, cp.size(), 1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k) + 1;
g.u += a;
g.v += f * a;
seg1.set(k, g);
seg0.apply(k, 1);
}
for (auto [q, x] : query) {
if (q == 1) {
ll k = cp.id(x);
seg1.apply(k, cp.size(), 1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k) + 1;
g.u += x;
g.v += f * x;
seg1.set(k, g);
seg0.apply(k, 1);
} else if (q == 2) {
ll k = cp.id(x);
seg1.apply(k, cp.size(), -1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k);
g.u -= x;
g.v -= f * x;
seg1.set(k, g);
seg0.apply(k, -1);
} else {
print(seg1.all_prod().v);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

コードでは ww を v という名前にしています。座標圧縮には Compress を使い、値を add で登録して build した後、cp.id(x) で値 xx の番号を得ます。seg0 は値ごとの個数を持つ区間和のセグメント木で、apply(k, c) は kk 番目の要素に cc を足す操作です。seg1 は値ごとの (u,w)(u, w) を持つ遅延評価セグメント木で、構造体には要素の型 S・作用の型 F と、op, e, mapping, composition, id をまとめています(ACL の lazy_segtree と同じ構成です)。初期の NN 個の要素も、追加クエリと同じ手順で 1 個ずつ入れています。

使用ライブラリ:cpp_include@397a51d