長さ の非負整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l r: の中で、同じ値が連続している部分の長さの最大値を出力する。
セグメント木の各ノードに、担当区間について次の値を持たせます。
- :区間の長さ
- :左端から続く同じ値の連続部分の(値, 長さ)
- :右端まで続く同じ値の連続部分の(値, 長さ)
- :区間内の連続部分の長さの最大値
隣り合う区間 (左)と (右)をつなげるときは、次のように考えます。
- は、 と の大きい方が基本です。さらに、 の右端の値と の左端の値が同じなら、 と がつながった長さも候補になります。
- は基本的に です。ただし、 全体が同じ値で( の長さが )、その値が の左端の値と同じなら、 の長さを足します。
- も同様です。
単位元(長さ の区間)は、合成するときに相手をそのまま返すように特別扱いします。全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001F { struct S { ll sz; pl left, right; ll ans; S() : sz{}, left{}, right{}, ans{} {} S(ll x) : sz{1}, left{x, 1}, right{x, 1}, ans{1} {} }; static S op(const S &a, const S &b) { if (b.sz == 0) return a; if (a.sz == 0) { return b; } S res = S(); res.sz = a.sz + b.sz; res.ans = max(a.ans, b.ans); if (a.right.first == b.left.first) { chmax(res.ans, a.right.second + b.left.second); } res.left = a.left; if (a.left.second == a.sz && a.left.first == b.left.first) { res.left.second += b.left.second; chmax(res.ans, res.left.second); } res.right = b.right; if (b.right.second == b.sz && b.right.first == a.right.first) { res.right.second += a.right.second; chmax(res.ans, res.right.second); } return res; } static S e() { return S(); }};
void solve() { LL(N, Q); VL(A, N); vec<AALC0001F::S> init; init.reserve(N); rep(i, N) init.emplace_back(A[i]); SegTree<AALC0001F> 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).ans); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。pl は std::pair<ll, ll> で、first が値、second が長さです。
使用ライブラリ:cpp_include@402f0cf