コンテンツにスキップ

AALC001 F - Run

サイト
AtCoder
コンテスト
AALC001
問題
F - Run
難易度
-

長さ NN の非負整数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) の中で、同じ値が連続している部分の長さの最大値を出力する。

セグメント木の各ノードに、担当区間について次の値を持たせます。

  • sz\mathrm{sz}:区間の長さ
  • left\mathrm{left}:左端から続く同じ値の連続部分の(値, 長さ)
  • right\mathrm{right}:右端まで続く同じ値の連続部分の(値, 長さ)
  • ans\mathrm{ans}:区間内の連続部分の長さの最大値

隣り合う区間 XX(左)と YY(右)をつなげるときは、次のように考えます。

  • ans\mathrm{ans} は、ansX\mathrm{ans}^X と ansY\mathrm{ans}^Y の大きい方が基本です。さらに、XX の右端の値と YY の左端の値が同じなら、rightX\mathrm{right}^X と leftY\mathrm{left}^Y がつながった長さも候補になります。
  • left\mathrm{left} は基本的に leftX\mathrm{left}^X です。ただし、XX 全体が同じ値で(leftX\mathrm{left}^X の長さが szX\mathrm{sz}^X)、その値が YY の左端の値と同じなら、leftY\mathrm{left}^Y の長さを足します。
  • right\mathrm{right} も同様です。

単位元(長さ 00 の区間)は、合成するときに相手をそのまま返すように特別扱いします。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

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