ABC484 F - Make them monochrome
または正整数からなる数列 に対し、次のクエリを処理する問題です()。
1 i x: を に変更する。2 l r:区間 の各 を好きな正整数に置き換えたとき、区間内をすべて同じ値にできるか判定する。
正整数が1種類以下ならよい
Section titled “正整数が1種類以下ならよい” は自由に置き換えられるので、区間内にもともとある正整数がすべて同じなら Yes です。正整数がなければ、すべての を例えば にできます。異なる正整数が 種類以上あれば、どちらも変更できないので No です。
この条件を、区間内の異なる値を大きい順に 種類まで取得して判定します。各値の出現回数も一緒に保持します。
- 種類しかなければ、そのまま同じ値か、すべて なので
Yes。 - 上位 種類の出現回数の和が区間長より小さければ、ほかにも値があり、少なくとも 種類あるので
No。 - ちょうど 種類なら、小さい方が の場合だけ
Yes。
はすべての正整数より小さいので、最後の条件で「 と正整数 種類だけ」を判定できます。
上位2種類をセグメント木で管理する
Section titled “上位2種類をセグメント木で管理する”各区間に、値が大きい順の 種類と、それぞれの出現回数を持たせます。左右の区間を結合するときは、同じ値の個数を足し合わせ、上位 種類だけを残します。
片方の区間で上位 種類に入らない値は、その区間だけでそれより大きい値が 種類あります。よって、結合後の上位 種類にも入りません。このため、各区間で上位 種類だけを残しても、結合後の値と個数を正確に求められます。
この情報をセグメント木に持たせると、値の変更は 点更新、判定は区間取得で処理できます。結合する情報の大きさは定数なので、各クエリは 、全体では です。空間計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/priority_counter.hpp"#include "shogo-library/data_structures/segtree.hpp"
void solve() { LL(N, Q); VL(A, N); using S = MaxCounter<ll, 2>; RSumQ<S> seg(A); rep(Q) { LL(q); if (q == 1) { LL(i, x); i--; seg.set(i, S{x}); } else { LL(l, r); l--; auto tmp = seg.prod(l, r); if (tmp.size() == 1) { print("Yes"); continue; } if (tmp[0].second + tmp[1].second < r - l) { print("No"); continue; } if (tmp[1].first == -1) { print("Yes"); } else { print("No"); } } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}自作ライブラリの MaxCounter<ll, 2> は値の大きい順に 種類までを、その個数とともに保持します。+ でこの情報を結合できるため、RSumQ に載せています。tmp.size() は保持している種類数なので、元の区間に 種類以上ある場合も になります。