コンテンツにスキップ

ABC484 F - Make them monochrome

サイト
AtCoder
コンテスト
ABC484
問題
F - Make them monochrome
難易度
1280

−1-1 または正整数からなる数列 AA に対し、次のクエリを処理する問題です(N,Q≤3×105N,Q\le3\times10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:区間 [l,r][l,r] の各 −1-1 を好きな正整数に置き換えたとき、区間内をすべて同じ値にできるか判定する。

−1-1 は自由に置き換えられるので、区間内にもともとある正整数がすべて同じなら Yes です。正整数がなければ、すべての −1-1 を例えば 11 にできます。異なる正整数が 22 種類以上あれば、どちらも変更できないので No です。

この条件を、区間内の異なる値を大きい順に 22 種類まで取得して判定します。各値の出現回数も一緒に保持します。

  • 11 種類しかなければ、そのまま同じ値か、すべて −1-1 なので Yes。
  • 上位 22 種類の出現回数の和が区間長より小さければ、ほかにも値があり、少なくとも 33 種類あるので No。
  • ちょうど 22 種類なら、小さい方が −1-1 の場合だけ Yes。

−1-1 はすべての正整数より小さいので、最後の条件で「−1-1 と正整数 11 種類だけ」を判定できます。

上位2種類をセグメント木で管理する

Section titled “上位2種類をセグメント木で管理する”

各区間に、値が大きい順の 22 種類と、それぞれの出現回数を持たせます。左右の区間を結合するときは、同じ値の個数を足し合わせ、上位 22 種類だけを残します。

片方の区間で上位 22 種類に入らない値は、その区間だけでそれより大きい値が 22 種類あります。よって、結合後の上位 22 種類にも入りません。このため、各区間で上位 22 種類だけを残しても、結合後の値と個数を正確に求められます。

この情報をセグメント木に持たせると、値の変更は 11 点更新、判定は区間取得で処理できます。結合する情報の大きさは定数なので、各クエリは O(log⁡N)O(\log N)、全体では O(N+Qlog⁡N)O(N+Q\log N) です。空間計算量は O(N)O(N) です。

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> は値の大きい順に 22 種類までを、その個数とともに保持します。+ でこの情報を結合できるため、RSumQ に載せています。tmp.size() は保持している種類数なので、元の区間に 33 種類以上ある場合も 22 になります。