AALC001 K - Multiset
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- K - Multiset
- 難易度
- -
はじめ 個の要素 をもつ整数の多重集合 に対して、次の 3 種類のクエリを合計 個処理する問題です(, )。
1 x: に を 1 個追加する。2 x: から を 1 個削除する( が含まれることは保証される)。3: の要素を昇順に並べた列を として、 を で割った余りを出力する。
クエリを先読みして、現れる値を座標圧縮します。値ごとに、その値の要素の「値の和 」と「(順位)×(値)の和 」を管理すると、答えは の総和です。同じ値の要素どうしは、どの順に並べても は変わりません。そのため、同じ値の要素の中での順番は自由に決めてよいです。
値 を追加するとき、 は同じ値の要素の中で先頭に入れることにします。すると、
- 以上の値の要素(同じ値の要素も含む)は順位が 1 つずつ増えるので、それぞれの値について が だけ増えます。
- 追加した要素の順位は「 未満の要素の個数 」なので、値 の に 、 に(順位) を足します。
削除は逆で、同じ値の要素の中の先頭を取り除くことにします。 以上の値の から を引き、値 の から 、 から「 未満の要素の個数」 を引きます。ここでの順位は、全体の順位を 1 つ下げた後の値です。
「 以上の値すべての に を足す」は区間への作用です。そのため、値ごとの を遅延評価セグメント木で管理します。作用 は で、合成は和です。 未満の要素の個数は、値ごとの個数を持つ別のセグメント木で求めます。
全体の計算量は です。
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();}コードでは を v という名前にしています。座標圧縮には Compress を使い、値を add で登録して build した後、cp.id(x) で値 の番号を得ます。seg0 は値ごとの個数を持つ区間和のセグメント木で、apply(k, c) は 番目の要素に を足す操作です。seg1 は値ごとの を持つ遅延評価セグメント木で、構造体には要素の型 S・作用の型 F と、op, e, mapping, composition, id をまとめています(ACL の lazy_segtree と同じ構成です)。初期の 個の要素も、追加クエリと同じ手順で 1 個ずつ入れています。
使用ライブラリ:cpp_include@397a51d