コンテンツにスキップ

セグメント木

タグ「セグメント木」の記事 19 件

ABC477 F - Count Cells in a Window

NN 行 MM 列のグリッドがあり、上から ii 行目は左から LiL_i 列目から RiR_i 列目までのマスが黒、それ以外のマスが白です。QQ 個のクエリで A,B,C,DA, B, C, D が与えられるので、AA 行目から BB 行目、CC 列目から DD 列目までの長方形に含まれる黒いマスの個数をそれぞれ答える問題です(1≤N,M,Q≤2×1051 \le N, M, Q \le 2 \times 10^5)。

上から kk 行目までのうち、CC 列目から DD 列目までにある黒いマスの個数を f(k)f(k) とすると、クエリの答えは f(B)−f(A−1)f(B) - f(A - 1) です。

列ごとの黒いマスの個数を表す長さ MM の配列を用意し、11 行目から順に、ii 行目を加えるたびに LiL_i 列目から RiR_i 列目までに 11 を足していきます。kk 行目まで加えたところでこの配列の CC 列目から DD 列目までの和をとれば、f(k)f(k) が求まります。

そこで、各クエリを「A−1A - 1 行目まで加えたときに ff を引く」と「BB 行目まで加えたときに ff を足す」の 2 つに分け、行の順にまとめて処理します(クエリを先に全部読んでおくので、オフラインで解くことになります)。

必要な操作は、配列の区間に 11 を足すことと、区間の和を求めることです。これは区間加算・区間和の遅延評価セグメント木か、BIT を 2 本使う方法で、どちらも O(log⁡M)O(\log M) でできます。クエリを行の順にソートするのとあわせて、全体の計算量は O(N+M+Qlog⁡Q+(N+Q)log⁡M)O(N + M + Q \log Q + (N + Q) \log M) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, Q);
VAL(LR, N, 2);
VAL(ABCD, Q, 4);
val<5> tmp;
for (auto &[l, r] : LR)
l--;
rep(i, Q) {
auto &[a, b, c, d] = ABCD[i];
a--, c--;
tmp.push_back({a, c, d, -1, i});
tmp.push_back({b, c, d, 1, i});
}
sort(tmp);
RAddSumQ<ll> seg(M);
ll k = 0;
vl ans(Q);
for (auto [x, c, d, y, i] : tmp) {
while (k < x) {
auto [l, r] = LR[k++];
seg.apply(l, r, 1);
}
ans[i] += y * seg.prod(c, d);
}
rep(i, Q) print(ans[i]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

VAL(LR, N, 2) は長さ 22 の配列を NN 個読み込むマクロです。列は 0 始まりの半開区間 [Li−1,Ri)[L_i - 1, R_i)、[C−1,D)[C - 1, D) で扱っています。

tmp には各クエリを (行数, C, D, 符号, クエリ番号) の 2 つに分けて入れ、行数の順にソートしています。k はすでに加えた行数で、行数 x のクエリを処理する前に x 行目まで加えます。RAddSumQ は区間加算・区間和の遅延評価セグメント木で、apply(l, r, 1) で区間に 11 を足し、prod(c, d) で区間の和を求めています。

使用ライブラリ:cpp_include@6519da7

DOJ Beginner Contest 13 F - Advance

NN 個の地域があり、軍隊が地域 ii を通るときは、まず兵士 BiB_i 人を守備隊として残し(その直後に 11 人以上残っていなければなりません)、そのあと兵士 AiA_i 人が合流します。次の 2 種類のクエリを QQ 個処理する問題です(1≤N,Q≤2000001 \le N, Q \le 200000、0≤Ai,Bi≤1090 \le A_i, B_i \le 10^9)。

  • 1 i a b:AiA_i を aa に、BiB_i を bb に変える。
  • 2 l r:地域 l,l+1,…,rl, l+1, \dots, r を順に通るとき、地域 ll に入る時点で必要な兵士の最小人数を答える。

区間を通る過程を「入るときに必要な最小人数 xx」と「ちょうど xx 人で入ったときに出ていく人数 yy」の組 (x,y)(x, y) で表します。xx 人より多く入れば、その分だけ出ていく人数も増えるので、この 2 つで区間の通り方が決まります。

地域 ii 1 つだけなら、BiB_i 人を残したあとに 11 人以上必要なので x=Bi+1x = B_i + 1 で、そのとき y=Ai+1y = A_i + 1 です。

区間 (x1,y1)(x_1, y_1) を通ったあとに区間 (x2,y2)(x_2, y_2) を通るとき、つなげた区間の組は次のようになります。

  • y1≥x2y_1 \ge x_2 のとき:x1x_1 人で入れば 2 つ目の区間にも入れるので、(x1, y1−x2+y2)(x_1, \ y_1 - x_2 + y_2)。
  • y1<x2y_1 < x_2 のとき:2 つ目の区間に入るのに x2−y1x_2 - y_1 人足りないので、最初にその分多く入る必要があり、(x1+x2−y1, y2)(x_1 + x_2 - y_1, \ y_2)。

この演算は結合的です(区間をつなげる順によらず、実際に通ったときの結果を表しているため)。単位元は (0,0)(0, 0) です。よってセグメント木に載せれば、クエリ 1 は 1 点の更新、クエリ 2 は区間の積の xx で、それぞれ O(log⁡N)O(\log N) で処理できます。

値は最大で (109+1)×200000≈2×1014(10^9 + 1) \times 200000 \approx 2 \times 10^{14} 程度なので、64 bit 整数で足ります。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct M {
using S = pl;
S op(const S &l, const S &r) const {
if (l.second >= r.first) {
return {l.first, l.second - r.first + r.second};
} else {
return {l.first + r.first - l.second, r.second};
}
}
S e() const {
return {0, 0};
}
};
void solve() {
LL(N, Q);
vec<M::S> init;
init.reserve(N);
rep(i, N) {
LL(a, b);
init.push_back({b + 1, a + 1});
}
SegTree<M> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, a, b);
seg.set(i - 1, {b + 1, a + 1});
} else {
LL(l, r);
print(seg.prod(l - 1, r).first);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree<M> は、モノイド M の演算 op と単位元 e を使うセグメント木です。要素の first が xx(必要な最小人数)、second が yy(出ていく人数)です。

使用ライブラリ:cpp_include@4b58304

AALC001 M - NAND

00 以上 2302^{30} 未満の整数からなる長さ NN の数列 AA に対して、次の 2 種類のクエリを QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。ここで NAND は、2 進法 30 桁で表したときの桁ごとの NAND(両方 11 なら 00、そうでなければ 11)です。

  • 1 p x:ApA_p を xx に変更する。
  • 2 l r:Bl=AlB_l = A_l とし、i=l+1,…,ri = l + 1, \ldots, r の順に BiB_i を Bi−1B_{i-1} と AiA_i の NAND とする。BrB_r を出力する。

NAND は桁ごとに独立なので、30 桁それぞれについて別々に考えます。ある桁に注目すると、Bi−1B_{i-1} のその桁 bb から BiB_i のその桁を求める操作は、AiA_i のその桁で決まる {0,1}\{0, 1\} 上の写像になります。

  • AiA_i の桁が 11 のとき:b↦¬bb \mapsto \lnot b(0↦10 \mapsto 1, 1↦01 \mapsto 0)
  • AiA_i の桁が 00 のとき:b↦1b \mapsto 1(0↦10 \mapsto 1, 1↦11 \mapsto 1)

クエリ 2 の答えのその桁は、AlA_l のその桁に、Al+1,…,ArA_{l+1}, \ldots, A_r に対応する写像を順に適用したものです。写像の合成は結合的なので、各桁ごとに写像を要素とするセグメント木を作れば、区間 [l+1,r][l + 1, r] の写像の合成を O(log⁡N)O(\log N) で求められます。l=rl = r のときは区間が空になり、合成は恒等写像なので Bl=AlB_l = A_l がそのまま答えになります。

クエリ 1 では 30 本のセグメント木それぞれで 1 点更新をします。全体の計算量は、桁数を W=30W = 30 として O(W(N+Qlog⁡N))O(W (N + Q \log N)) です。

C++
#include "shogo-library/algebra/monoid.hpp"
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
ary<SegTree<monoid::Mapping<2>>, 30> seg;
rep(d, 30) {
vec<monoid::Mapping<2>::S> init;
init.reserve(N);
for (ll a : A) {
if ((a >> d) & 1) {
init.push_back({1, 0});
} else {
init.push_back({1, 1});
}
}
seg[d] = SegTree<monoid::Mapping<2>>(init);
}
rep(Q) {
LL(q);
if (q == 1) {
LL(p, x);
p--;
rep(d, 30) {
if ((x >> d) & 1) {
seg[d].set(p, {1, 0});
} else {
seg[d].set(p, {1, 1});
}
}
A[p] = x;
} else {
LL(l, r);
l--;
ll ans = 0;
rep(d, 30) {
ll t = seg[d].prod(l + 1, r)[(A[l] >> d) & 1];
ans |= t << d;
}
print(ans);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree にはモノイドを表す構造体を渡します(1 点更新・区間積のセグメント木で、prod(l, r) は半開区間 [l,r)[l, r) の積です)。monoid::Mapping<2> は {0,1}\{0, 1\} 上の写像の合成のモノイドで、写像 ff を std::array<int, 2> の (f(0),f(1))(f(0), f(1)) で表します。区間の積は左の要素の写像から順に適用した合成なので、prod(l + 1, r) に AlA_l の桁を渡せば BrB_r の桁が得られます。

使用ライブラリ:cpp_include@397a51d

AALC001 L - Swap between Arrays

長さ NN の整数列 AA, BB, CC に対して、次の 4 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤1051 \le N, Q \le 10^5, −109≤Ai,Bi,Ci≤109-10^9 \le A_i, B_i, C_i \le 10^9)。

  • 1 l r:l≤k≤rl \le k \le r のすべての kk について、AkA_k と BkB_k を入れ替える。
  • 2 l r:同様に BkB_k と CkC_k を入れ替える。
  • 3 l r:同様に CkC_k と AkA_k を入れ替える。
  • 4 i:∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる jj(i≤j≤Ni \le j \le N)の最小値を出力する。なければ N+1N + 1 を出力する。

まず、入れ替えがない場合のクエリ 4 を考えます。∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる最小の jj は、「区間 [i,j][i, j] の接頭辞の和がすべて 00 以下である間、右に伸ばす」という二分探索で求まります。セグメント木の各ノードに区間の和と接頭辞の和の最大値を持たせれば、セグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で求まります。接頭辞の和の最大値は、区間 XX(左)と YY(右)について max⁡(preX,sumX+preY)\max(\mathrm{pre}^X, \mathrm{sum}^X + \mathrm{pre}^Y) で合成できます。

入れ替えに対応するために、AA, BB, CC の 3 本それぞれについて、和と接頭辞の和の最大値をノードに持たせます。区間内の AkA_k と BkB_k をすべて入れ替えると、ノードが持つ AA の値と BB の値もそのまま入れ替わります。そのため、入れ替えは「3 本の情報を並べ替える」作用として遅延評価セグメント木に載せられます。作用は (0,1,2)(0, 1, 2) の置換 ff で表し、新しい ii 本目には元の fif_i 本目の値が入るとします。作用 gg の後に ff を行うと、新しい ii 本目には元の gfig_{f_i} 本目の値が入るので、合成は (gf0,gf1,gf2)(g_{f_0}, g_{f_1}, g_{f_2}) です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
void solve() {
using M = monoid::PrefixSumMax<ll>;
using A = acted_monoid::Rearrange<M, 3>;
LL(N, Q);
vec<A::S> init(N);
rep(j, 3) rep(i, N) {
LL(x);
init[i][j] = M::S(x);
}
LazySegTree<A> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(l, r);
seg.apply(l - 1, r, A::swap(0, 1));
} else if (q == 2) {
LL(l, r);
seg.apply(l - 1, r, A::swap(1, 2));
} else if (q == 3) {
LL(l, r);
seg.apply(l - 1, r, A::swap(0, 2));
} else {
LL(i);
print(1 + seg.max_right(i - 1, [](const auto &p) { return p[0].max <= 0; }));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

monoid::PrefixSumMax<ll> は区間の和 sum と接頭辞の和の最大値 max をもつモノイドで、M::S(x) が値 xx の 1 要素を表します。max は空の接頭辞(和 00)も含めた接頭辞の和の最大値なので、単位元では 00 になります。acted_monoid::Rearrange<M, 3> は、これを 3 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドで、A::swap(i, j) が成分 ii と jj を入れ替える作用です。入力は AA, BB, CC の順に 1 本ずつ読み、kk 番目の要素の成分 0, 1, 2 に入れています。LazySegTree の max_right は ACL と同じ仕様です。

max_right(i - 1, f) は、0 始まりの半開区間 [i−1,r′)[i - 1, r') の接頭辞の和がすべて 00 以下となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素まで足すと初めて和が正になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。

使用ライブラリ:cpp_include@397a51d

AALC001 K - Multiset

はじめ NN 個の要素 A1,…,ANA_1, \dots, A_N をもつ整数の多重集合 SS に対して、次の 3 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5, 0≤Ai,x≤1090 \le A_i, x \le 10^9)。

  • 1 x:SS に xx を 1 個追加する。
  • 2 x:SS から xx を 1 個削除する(xx が含まれることは保証される)。
  • 3:SS の要素を昇順に並べた列を x1,…,xkx_1, \dots, x_k として、∑i=1kixi\sum_{i=1}^{k} i x_i を 998244353998244353 で割った余りを出力する。

クエリを先読みして、現れる値を座標圧縮します。値ごとに、その値の要素の「値の和 uu」と「(順位)×(値)の和 ww」を管理すると、答えは ww の総和です。同じ値の要素どうしは、どの順に並べても ∑ixi\sum i x_i は変わりません。そのため、同じ値の要素の中での順番は自由に決めてよいです。

値 xx を追加するとき、xx は同じ値の要素の中で先頭に入れることにします。すると、

  • xx 以上の値の要素(同じ値の要素も含む)は順位が 1 つずつ増えるので、それぞれの値について ww が uu だけ増えます。
  • 追加した要素の順位は「xx 未満の要素の個数 +1+ 1」なので、値 xx の uu に xx、ww に(順位)×x\times x を足します。

削除は逆で、同じ値の要素の中の先頭を取り除くことにします。xx 以上の値の ww から uu を引き、値 xx の uu から xx、ww から「xx 未満の要素の個数」×x\times x を引きます。ここでの順位は、全体の順位を 1 つ下げた後の値です。

「xx 以上の値すべての ww に c⋅uc \cdot u を足す」は区間への作用です。そのため、値ごとの (u,w)(u, w) を遅延評価セグメント木で管理します。作用 cc は (u,w)↦(u,w+cu)(u, w) \mapsto (u, w + c u) で、合成は和です。xx 未満の要素の個数は、値ごとの個数を持つ別のセグメント木で求めます。

全体の計算量は O((N+Q)log⁡(N+Q))O((N + Q) \log (N + Q)) です。

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();
}

コードでは ww を v という名前にしています。座標圧縮には Compress を使い、値を add で登録して build した後、cp.id(x) で値 xx の番号を得ます。seg0 は値ごとの個数を持つ区間和のセグメント木で、apply(k, c) は kk 番目の要素に cc を足す操作です。seg1 は値ごとの (u,w)(u, w) を持つ遅延評価セグメント木で、構造体には要素の型 S・作用の型 F と、op, e, mapping, composition, id をまとめています(ACL の lazy_segtree と同じ構成です)。初期の NN 個の要素も、追加クエリと同じ手順で 1 個ずつ入れています。

使用ライブラリ:cpp_include@397a51d

AALC001 J - Long Binary String

長さ 101810^{18} の 0, 1 からなる文字列 SS があり、はじめはすべて 0 です。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤Q≤2×1051 \le Q \le 2 \times 10^5)。

  • 1 l r:Sl,…,SrS_l, \dots, S_r を反転する。
  • 2 l r:Sl,…,SrS_l, \dots, S_r に含まれる 1 の個数を出力する。

クエリを先読みして座標圧縮します。区間を 0 始まりの半開区間 [l−1,r)[l - 1, r) で表し、すべてのクエリの端点 l−1l - 1, rr を集めてソートし、重複を除いたものを v0<v1<⋯<vm−1v_0 < v_1 < \dots < v_{m-1} とします。すると、どのクエリの区間も小区間 [vj−1,vj)[v_{j-1}, v_j) をいくつか並べたものになります。また、各小区間の中の文字はつねにすべて同じように反転されます。

そこで、小区間 [vj−1,vj)[v_{j-1}, v_j) を 1 つの要素とする遅延評価セグメント木を作ります。各ノードには担当範囲の 0 の個数と 1 の個数を持たせます。はじめは 0 の個数が小区間の長さ vj−vj−1v_j - v_{j-1} で、1 の個数は 00 です。反転はこの 2 つを入れ替える作用で、2 回反転すると元に戻るので、作用の合成は XOR です。

全体の計算量は O(Qlog⁡Q)O(Q \log Q) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/utility/compress.hpp"
void solve() {
LL(Q);
VAL(qlr, Q, 3);
Compress<ll> cp;
for (auto &[q, l, r] : qlr) {
l--;
cp.add(l);
cp.add(r);
}
cp.build();
using A = acted_monoid::Rearrange<monoid::Sum<ll>, 2>;
vec<A::S> init;
init.reserve(cp.size() - 1);
rep(i, 1, cp.size()) {
init.push_back({cp[i] - cp[i - 1], 0});
}
LazySegTree<A> seg(init);
for (auto [q, l, r] : qlr) {
if (q == 1) {
seg.apply(cp.id(l), cp.id(r), A::swap(0, 1));
} else {
print(seg.prod(cp.id(l), cp.id(r))[1]);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

VAL(qlr, Q, 3) で、クエリを std::array<ll, 3> の配列として読み込んでいます。座標圧縮には Compress を使い、端点を add で登録して build した後、cp[i] で viv_i、cp.id(x) で値 xx の番号を得ます。セグメント木の jj 番目の要素は小区間 [vj,vj+1)[v_j, v_{j+1}) なので、半開区間 [l−1,r)[l - 1, r) は要素の番号の範囲 [id(l−1),id(r))[\mathrm{id}(l - 1), \mathrm{id}(r)) に対応します。

acted_monoid::Rearrange<monoid::Sum<ll>, 2> は、和のモノイドを 2 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドです。成分 0 が 0 の個数、成分 1 が 1 の個数で、A::swap(0, 1) が反転の作用です。これを LazySegTree に渡しています。

使用ライブラリ:cpp_include@397a51d

AALC001 I - Subarray

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

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) から、互いに重ならない空でない連続部分列を 00 個以上 22 個以下選ぶ。選んだ部分列の要素の総和の最大値を出力する。

連続部分列を 1 個選ぶ場合(最大部分配列問題)は、セグメント木の各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「連続部分列の和の最大値」を持たせる方法が知られています。これを 2 個まで選べるように広げます。

ここで、長さ 00 の連続部分列(和は 00)も選べることにします。すると「00 個以上 22 個以下選ぶ」は「長さ 00 も含めてちょうど 22 個選ぶ」と同じになり、個数の場合分けが要らなくなります。

選ぶ連続部分列の個数 kk(k=1,2k = 1, 2)と、区間の端に接する部分列があるかどうかで、次の 8 つの値を持たせます。いずれも和の最大値です。

値左端から始まる部分列右端で終わる部分列
lrk\mathrm{lr}_kありあり
lk\mathrm{l}_kありなくてもよい
rk\mathrm{r}_kなくてもよいあり
zk\mathrm{z}_kなくてもよいなくてもよい

「左端から始まる部分列」は長さ 00 でもよいので、たとえば l1\mathrm{l}_1 は空の接頭辞も含めた接頭辞の和の最大値です。k=1k = 1 で左端から始まり右端で終わるのは区間全体なので、lr1\mathrm{lr}_1 は区間全体の和です。

隣り合う区間 XX(左)と YY(右)をつなげるときは、境目をまたぐ部分列があるかどうかで場合分けします。またぐ部分列は、XX の右端で終わる部分列と YY の左端から始まる部分列がつながったものです。そのため、個数は XX 側と YY 側の合計より 1 少なくなります。たとえば z2\mathrm{z}_2 は次の候補の最大値です。

  • 境目をまたがない:z2X\mathrm{z}_2^X、z2Y\mathrm{z}_2^Y、z1X+z1Y\mathrm{z}_1^X + \mathrm{z}_1^Y
  • 境目をまたぐ:r2X+l1Y\mathrm{r}_2^X + \mathrm{l}_1^Y、r1X+l2Y\mathrm{r}_1^X + \mathrm{l}_2^Y

ほかの値も同じように、「XX 側で左端の条件を満たし、YY 側で右端の条件を満たす」組み合わせを列挙すれば求まります。すべての部分列を長さ 00 にすれば和は 00 なので、lr1\mathrm{lr}_1 以外の値は 00 以上です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001I {
struct S {
ll lr1, l1, r1, z1, lr2, l2, r2, z2;
S() {
lr1 = l1 = r1 = z1 = lr2 = l2 = r2 = z2 = 0;
}
S(ll a) {
lr1 = a;
l1 = r1 = z1 = lr2 = l2 = r2 = z2 = max(a, 0LL);
}
ll ans() const {
ll res = 0;
chmax(res, lr1);
chmax(res, l1);
chmax(res, r1);
chmax(res, z1);
chmax(res, lr2);
chmax(res, l2);
chmax(res, r2);
chmax(res, z2);
return res;
}
};
static S op(const S &a, const S &b) {
S res{};
res.lr1 = a.lr1 + b.lr1;
chmax(res.l1, a.l1);
chmax(res.l1, a.lr1 + b.l1);
chmax(res.r1, b.r1);
chmax(res.r1, a.r1 + b.lr1);
chmax(res.z1, a.z1);
chmax(res.z1, b.z1);
chmax(res.z1, a.r1 + b.l1);
chmax(res.lr2, a.l1 + b.r1);
chmax(res.lr2, a.lr1 + b.lr2);
chmax(res.lr2, a.lr2 + b.lr1);
chmax(res.l2, a.l2);
chmax(res.l2, a.lr1 + b.l2);
chmax(res.l2, a.lr2 + b.l1);
chmax(res.l2, a.l1 + b.z1);
chmax(res.r2, b.r2);
chmax(res.r2, a.r2 + b.lr1);
chmax(res.r2, a.r1 + b.lr2);
chmax(res.r2, a.z1 + b.r1);
chmax(res.z2, a.z2);
chmax(res.z2, b.z2);
chmax(res.z2, a.z1 + b.z1);
chmax(res.z2, a.r2 + b.l1);
chmax(res.z2, a.r1 + b.l2);
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001I::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(A[i]);
SegTree<AALC0001I> 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 をまとめた構造体を渡します。op では結果を 00(すべて長さ 00 を選んだ場合)で初期化してから、chmax で候補を入れています。長さ 11 のノードでは、区間全体である lr1\mathrm{lr}_1 だけが AiA_i で、ほかの値は長さ 00 も選べるので max⁡(Ai,0)\max(A_i, 0) です。

使用ライブラリ:cpp_include@402f0cf

AALC001 H - Add and Mod

長さ 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 x:i=l,…,ri = l, \dots, r の順に、Ai=0A_i = 0 なら x←x mod 998244353x \leftarrow x \bmod 998244353、Ai>0A_i > 0 なら x←x+Aix \leftarrow x + A_i とする。最終的な xx を出力する。

p=998244353p = 998244353 とします。区間 [l,r][l, r] に 00 が含まれないなら、答えは x+∑i=lrAix + \sum_{i=l}^{r} A_i です。

00 が含まれる場合、最後の 00 の位置を mm とします。途中で pp で割った余りをとっても、その後の値を pp で割った余りは変わりません。位置 mm では余りをとるので、その時点の値は (x+∑i=lm−1Ai) mod p\left(x + \sum_{i=l}^{m-1} A_i\right) \bmod p になります。その後は ∑i=m+1rAi\sum_{i=m+1}^{r} A_i を足すだけです。

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

  • XX:00 を含むかどうかと、含む場合は最後の 00 より前の要素の和を pp で割った余り
  • YY:最後の 00 より後の要素の和(00 を含まなければ区間全体の和)

隣り合う区間 LL(左)と RR(右)をつなげるとき、RR が 00 を含むなら、最後の 00 は RR の中にあります。その前の要素は LL 全体と RR の最後の 00 より前の部分なので、X=(L の総和+XR) mod pX = (L \text{ の総和} + X^R) \bmod p、Y=YRY = Y^R です。LL の総和を pp で割った余りは、LL が 00 を含むかどうかによらず XL+YLX^L + Y^L で求まります(00 を含まないなら XLX^L を 00 とみなします)。RR が 00 を含まないなら、X=XLX = X^L、Y=YL+YRY = Y^L + Y^R です。

答えは、区間が 00 を含むなら (x+X) mod p+Y(x + X) \bmod p + Y、含まなければ x+Yx + Y です。YY は最大で 2×105×109=2×10142 \times 10^5 \times 10^9 = 2 \times 10^{14} 程度なので、64 ビット整数に収まります。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
struct AALC0001H {
struct S {
std::optional<mint> x;
ll y;
S() : x{}, y{} {}
S(ll f) : x{}, y{} {
if (f == 0)
x = 0;
else
y = f;
}
};
static S op(const S &a, const S &b) {
S res = S{};
if (b.x.has_value()) {
res.x = a.x.value_or(0) + a.y + b.x.value();
res.y = b.y;
} else {
res.x = a.x;
res.y = a.y + b.y;
}
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001H::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(A[i]);
SegTree<AALC0001H> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, {x});
} else if (q == 2) {
LL(l, r, x);
auto p = seg.prod(l - 1, r);
ll ans = x;
if (p.x.has_value()) {
ans = (ans + p.x.value()).value();
}
ans += p.y;
print(ans);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。上の XX を std::optional<mint> の x で表し、00 を含まないことを値がないことで表しています。YY は ll の y です。

使用ライブラリ:cpp_include@402f0cf

AALC001 G - Sum of k-th Powers

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

  • 1 l r x:Al,…,ArA_l, \dots, A_r のそれぞれに xx を足す。
  • 2 l r k:∑i=lrAik\sum_{i=l}^{r} A_i^k を 998244353998244353 で割った余りを出力する(1≤k≤41 \le k \le 4)。

遅延評価セグメント木の各ノードに、担当区間の p=0,1,…,4p = 0, 1, \dots, 4 乗和 sp=∑Aips_p = \sum A_i^p を持たせます(s0s_0 は区間の長さです)。2 つの区間の合成は、それぞれの和をとるだけです。

区間の全要素に xx を足したときは、二項定理より

∑(Ai+x)p=∑q=0p(pq)xp−q∑Aiq=∑q=0p(pq)xp−qsq\sum (A_i + x)^p = \sum_{q=0}^{p} \binom{p}{q} x^{p-q} \sum A_i^q = \sum_{q=0}^{p} \binom{p}{q} x^{p-q} s_q

となるので、新しい sps_p は古い s0,…,sps_0, \dots, s_p から計算できます。足す値の合成は和です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です(定数倍は kk の上限 44 に応じて大きくなります)。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() {
LL(N, Q);
VL(A, N);
vec<acted_monoid::AddPowerSum<mint, 4>::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(A[i]);
LazySegTree<acted_monoid::AddPowerSum<mint, 4>> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(l, r, x);
seg.apply(l - 1, r, x);
} else if (q == 2) {
LL(l, r, k);
print(seg.prod(l - 1, r)[k]);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

acted_monoid::AddPowerSum<mint, 4> は、区間加算と 00 乗から 44 乗までの和を扱う作用付きモノイドで、mapping で上の二項展開を行います。これを LazySegTree に渡しています。prod の結果に [k] を付けると kk 乗和が得られます。

使用ライブラリ:cpp_include@397a51d

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

AALC001 E - RGB

長さ NN の非負整数列 AA と、R, G, B からなる長さ NN の文字列 SS が与えられます。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:l≤i<j<k≤rl \le i < j < k \le r かつ Si,Sj,SkS_i, S_j, S_k がこの順に R, G, B である組 (i,j,k)(i, j, k) すべてについての AiAjAkA_i A_j A_k の総和を、998244353998244353 で割った余りを出力する。

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

  • R\mathrm{R}:SiS_i が R である ii についての AiA_i の総和(G, B についても同様に G\mathrm{G}, B\mathrm{B})
  • RG\mathrm{RG}:i<ji < j かつ Si,SjS_i, S_j がこの順に R, G である組についての AiAjA_i A_j の総和(GB\mathrm{GB} も同様)
  • RGB\mathrm{RGB}:求めたい値

隣り合う区間 XX(左)と YY(右)をつなげるとき、たとえば RG\mathrm{RG} になる組は「両方 XX の中」「両方 YY の中」「R が XX、G が YY」のどれかです。最後の場合の総和は RXGY\mathrm{R}^X \mathrm{G}^Y なので、次のように合成できます。

RGXY=RGX+RGY+RXGYGBXY=GBX+GBY+GXBYRGBXY=RGBX+RGBY+RGXBY+RXGBY\begin{aligned} \mathrm{RG}^{XY} &= \mathrm{RG}^X + \mathrm{RG}^Y + \mathrm{R}^X \mathrm{G}^Y \\ \mathrm{GB}^{XY} &= \mathrm{GB}^X + \mathrm{GB}^Y + \mathrm{G}^X \mathrm{B}^Y \\ \mathrm{RGB}^{XY} &= \mathrm{RGB}^X + \mathrm{RGB}^Y + \mathrm{RG}^X \mathrm{B}^Y + \mathrm{R}^X \mathrm{GB}^Y \end{aligned}

R\mathrm{R}, G\mathrm{G}, B\mathrm{B} はそれぞれの和です。これをセグメント木に載せれば、全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
enum E {
R,
G,
B,
RG,
GB,
RGB,
};
void solve() {
LL(N, Q);
VL(A, N);
STR(S);
struct AALC0001E {
struct S {
ary<mint, 6> cnt;
S() : cnt{} {}
S(char x, mint a) : cnt{} {
if (x == 'R') {
cnt[E::R] += a;
} else if (x == 'G') {
cnt[E::G] += a;
} else if (x == 'B') {
cnt[E::B] += a;
} else {
assert(false);
}
}
};
static S op(const S &a, const S &b) {
S res = S();
res.cnt[E::R] = a.cnt[E::R] + b.cnt[E::R];
res.cnt[E::G] = a.cnt[E::G] + b.cnt[E::G];
res.cnt[E::B] = a.cnt[E::B] + b.cnt[E::B];
res.cnt[E::RG] = a.cnt[E::RG] + b.cnt[E::RG] + a.cnt[E::R] * b.cnt[E::G];
res.cnt[E::GB] = a.cnt[E::GB] + b.cnt[E::GB] + a.cnt[E::G] * b.cnt[E::B];
res.cnt[E::RGB] = a.cnt[E::RGB] + b.cnt[E::RGB] + a.cnt[E::RG] * b.cnt[E::B] + a.cnt[E::R] * b.cnt[E::GB];
return res;
}
static S e() { return S(); }
};
vec<AALC0001E::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(S[i], A[i]);
SegTree<AALC0001E> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, {S[i - 1], x});
} else if (q == 2) {
LL(l, r);
print(seg.prod(l - 1, r).cnt[E::RGB]);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。6 つの値は enum E の名前で配列 cnt に入れています。

使用ライブラリ:cpp_include@402f0cf

AALC001 D - Inversion Count

0,1,20, 1, 2 からなる長さ 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) の転倒数を出力する。

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

  • cntv\mathrm{cnt}_v:値 vv(v=0,1,2v = 0, 1, 2)の個数
  • inv\mathrm{inv}:区間内の転倒数

隣り合う区間 XX(左)と YY(右)をつなげたときの転倒数は、「XX の中の転倒数」「YY の中の転倒数」「XX と YY にまたがる転倒数」の和です。またがる転倒は、XX の値 ii と YY の値 jj で i>ji > j となる組なので、その個数は ∑i>jcntiX cntjY\sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j です。

invXY=invX+invY+∑i>jcntiX cntjY\mathrm{inv}^{XY} = \mathrm{inv}^X + \mathrm{inv}^Y + \sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j

これで 2 つの区間の情報を O(1)O(1) で合成できるので、セグメント木に載せられます。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001D {
struct S {
al<3> cnt;
ll inv;
S() : cnt{}, inv{} {}
S(ll x) : cnt{}, inv{} {
assert(0 <= x && x < 3);
cnt[x] = 1;
}
};
static S op(const S &a, const S &b) {
S res;
res.inv = a.inv + b.inv;
rep(i, 3) {
res.cnt[i] = a.cnt[i] + b.cnt[i];
rep(j, i) {
res.inv += a.cnt[i] * b.cnt[j];
}
}
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001D::S> init;
init.reserve(N);
for (ll a : A)
init.push_back(a);
SegTree<AALC0001D> 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).inv);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。al<3> は std::array<ll, 3> です。

使用ライブラリ:cpp_include@402f0cf

AALC001 C - Binary Search on a Segment Tree

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

  • 1 i x:AiA_i を xx に変更する。
  • 2 l t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる rr(l≤r≤Nl \le r \le N)の最小値を出力する。なければ N+1N + 1 を出力する。
  • 3 r t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる ll(1≤l≤r1 \le l \le r)の最大値を出力する。なければ 00 を出力する。

和のセグメント木を使います。Ai≥0A_i \ge 0 なので、ll を固定すると ∑i=lrAi\sum_{i=l}^{r} A_i は rr について単調に増えます。そのため、クエリ 2 は「和が tt 未満である間、右に伸ばせるだけ伸ばす」という二分探索で求まります。これはセグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で行えます。クエリ 3 も同様に、左に伸ばす二分探索(min_left)で求まります。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
RSumQ<ll> seg(A);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, x);
} else if (q == 2) {
LL(l, t);
print(1 + seg.max_right(l - 1, [t](ll a) { return a < t; }));
} else {
LL(r, t);
print(seg.min_left(r, [t](ll a) { return a < t; }));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RSumQ<ll> は区間和のセグメント木で、max_right と min_left は ACL と同じ仕様です。

  • max_right(l - 1, f) は、0 始まりの半開区間 [l−1,r′)[l - 1, r') の和が tt 未満となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素を加えたときに初めて tt 以上になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。
  • min_left(r, f) は、半開区間 [l′,r)[l', r) の和が tt 未満となる最小の l′l' を返します。0 始まりで l′−1l' - 1 番目(1 始まりで l′l' 番目)の要素を加えたときに初めて tt 以上になるので、答えは l′l' です。l′=0l' = 0 のときも、そのまま「存在しない」場合の出力 00 になります。

使用ライブラリ:cpp_include@402f0cf

AALC001 B - Lazy Segment Tree

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

  • 1 l r x:Al,…,ArA_l, \dots, A_r のそれぞれに xx を足す。
  • 2 l r:min⁡(Al,…,Ar)\min(A_l, \dots, A_r) を出力する。

区間への加算と区間の最小値の取得なので、遅延評価セグメント木を使います。区間 [l,r][l, r] の全要素に xx を足すと、その区間の最小値もちょうど xx 増えます。そのため、各ノードには「担当区間の最小値」だけを持たせ、作用は「xx を足す」、作用の合成は「足す値の和」とすればよいです。

どちらの操作も O(log⁡N)O(\log N) なので、全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
RAddMinQ<ll> seg(A);
rep(Q) {
LL(q);
if (q == 1) {
LL(l, r, x);
seg.apply(l - 1, r, x);
} else {
LL(l, r);
print(seg.prod(l - 1, r));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RAddMinQ<ll> は区間加算・区間最小値の遅延評価セグメント木です。apply(l, r, x) と prod(l, r) は 0 始まりの半開区間 [l,r)[l, r) を対象にします。

使用ライブラリ:cpp_include@402f0cf

AALC001 A - Segment Tree

長さ 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:min⁡(Al,…,Ar)\min(A_l, \dots, A_r) を出力する。

1 点の更新と区間の最小値の取得なので、最小値を演算とするセグメント木をそのまま使えます。どちらの操作も O(log⁡N)O(\log N) なので、全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
RMinQ<ll> seg(A);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, x);
} else {
LL(l, r);
print(seg.prod(l - 1, r));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RMinQ<ll> は区間の最小値を求めるセグメント木です。prod(l, r) は 0 始まりの半開区間 [l,r)[l, r) を対象にするので、prod(l - 1, r) としています。

使用ライブラリ:cpp_include@402f0cf

ABC479 D - Back and Forth Distance

NN 個のマスが一列に並んでいます。マス ii からは、左側の好きなマスへコスト LiL_i で、右側の好きなマスへコスト RiR_i で移動できます。QQ 個のクエリ (s,t)(s, t) について、マス ss からマス tt へ移動するときのコストの合計の最小値を求める問題です(2≤N≤3×1052 \le N \le 3 \times 10^5、1≤Q≤3×1051 \le Q \le 3 \times 10^5、1≤Li,Ri≤1091 \le L_i, R_i \le 10^9、s≠ts \ne t)。

s<ts < t の場合を考えます(s>ts > t の場合は左右を入れ替えるだけです)。

最初の移動で場合分けします。

  • 最初に右へ移動する場合:コストは少なくとも RsR_s かかります。一方、マス ss からマス tt へ直接移動すればコスト RsR_s で着くので、この場合の最小値は RsR_s です。
  • 最初に左へ移動する場合:まずコスト LsL_s がかかります。その後マス tt に行くには、どこかで右へ移動する必要があります。最初に右へ移動するまでは左にしか動いていないので、そのときにいるマス jj は j<sj < s を満たし、コスト RjR_j がかかります。逆に、マス ss からマス jj へ移動し、マス jj からマス tt へ移動すれば、コスト Ls+RjL_s + R_j で着きます。したがって、この場合の最小値は Ls+min⁡j<sRjL_s + \min_{j < s} R_j です。

まとめると、答えは

min⁡(Rs, Ls+min⁡1≤j<sRj)\min\left(R_s,\ L_s + \min_{1 \le j < s} R_j\right)

です(s=1s = 1 のときは RsR_s)。s>ts > t のときは同様に min⁡(Ls, Rs+min⁡s<j≤NLj)\min\left(L_s,\ R_s + \min_{s < j \le N} L_j\right) です。

min⁡j<sRj\min_{j < s} R_j は RR の先頭からの最小値(累積 min)、min⁡j>sLj\min_{j > s} L_j は LL の末尾からの最小値なので、前計算しておけば各クエリに O(1)O(1) で答えられます。計算量は O(N+Q)O(N + Q) です。セグメント木で区間の最小値を求めても、O((N+Q)log⁡N)O((N + Q) \log N) で間に合います。

Python
N, Q = map(int, input().split())
L = [0, 0] + list(map(int, input().split()))
R = [0] + list(map(int, input().split())) + [0]
INF = 1 << 60
pre = [INF] * N
for i in range(1, N):
pre[i] = min(pre[i - 1], R[i])
suf = [INF] * (N + 2)
for i in range(N, 1, -1):
suf[i] = min(suf[i + 1], L[i])
for _ in range(Q):
s, t = map(int, input().split())
if s < t:
print(min(R[s], L[s] + pre[s - 1]))
else:
print(min(L[s], R[s] + suf[s + 1]))

L[i] が LiL_i、R[i] が RiR_i になるように、先頭と末尾に 00 を詰めています。pre[i] は min⁡(R1,…,Ri)\min(R_1, \dots, R_i)、suf[i] は min⁡(Li,…,LN)\min(L_i, \dots, L_N) で、範囲が空のときは INF です。s=1s = 1 のときは pre[0] が INF なので、自動的に RsR_s が答えになります(s=Ns = N のときも同様です)。

C++
#include "shogo-library/algebra/monoid.hpp"
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(L, N - 1);
VL(R, N - 1);
RMinQ<ll> segl(L), segr(R);
rep(Q) {
LL(s, t);
s--, t--;
ll ans = 1e18;
if (s < t) {
chmin(ans, R[s]);
if (s > 0) {
chmin(ans, segr.prod(0, s) + L[s - 1]);
}
} else {
chmin(ans, L[s - 1]);
if (s < N - 1) {
chmin(ans, segl.prod(s, N - 1) + R[s]);
}
}
print(ans);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RMinQ は区間の最小値を求めるセグメント木で、prod(l, r) は半開区間 [l,r)[l, r) の最小値を返します。コードでは s を 0 始まりに直しているので、問題文のマス ss に対して L[s - 1] が LsL_s、R[s] が RsR_s です。segr.prod(0, s) が min⁡j<sRj\min_{j < s} R_j、segl.prod(s, N - 1) が min⁡j>sLj\min_{j > s} L_j にあたります。

使用ライブラリ:cpp_include@402f0cf

セグメント木のリンク集

セグメント木について、参考になる記事や資料をまとめました。

セグメント木は、列に対して「1 点の更新」と「区間の積(和・最小値・最大値など)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。演算が結合法則を満たし、単位元を持つ(モノイドである)ことが条件です。区間に対する更新も行えるように拡張したものを、遅延評価セグメント木(遅延セグ木)と呼びます。区間 chmin のように遅延セグ木にそのままでは載らない作用を扱うための拡張に、Segment Tree Beats があります。

セグメント木そのものを解説する講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 区間の情報をどう持ち、どう結合するかを、区間和・区間最小値から関数合成・行列まで例を挙げて解説しています。セグメント木を使ったことがある人向けです。
  • 代数構造用語集
    • モノイドなどの用語の定義です。
  • 永続セグメント木
    • 過去の状態を残したまま更新できるようにしたセグメント木です。
  • セグメント木(Wikipedia)
    • 前半は Bentley による元々の segment tree(線分の集合を格納し、ある点を含む線分を列挙する木)の説明で、競プロで使うものとは別物です。モノイドへの一般化と配列による実装は後半にありますが、細かい誤りがあるので、ほかの資料と合わせて読むのがおすすめです。
  • Segment Tree(cp-algorithms)
    • 英語の定番の解説です。応用例が多く載っています。

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。

ABC478 F - Min-First Search

頂点 1,…,N1, \ldots, N の木 TT について、頂点 11 から始めて「訪問候補の集合 SS から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を SS に加える」ことを繰り返したときの訪問順を f(T)f(T) とします。順列 QQ (Q1=1Q_1 = 1) が与えられるので、f(T)=Qf(T) = Q となる木 TT の個数を 998244353998244353 で割った余りを求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、添字を 00 始まりにして Q0=1Q_0 = 1 とします。

i≥1i \ge 1 について、QiQ_i を SS に加えたのは、QiQ_i より先に訪問された隣接頂点です。木なので、QiQ_i に隣接する頂点のうち QiQ_i より先に訪問されるものはちょうど 1 つで、これを QiQ_i の親 QkQ_k (k<ik < i) と呼ぶことにします。木は「各 i≥1i \ge 1 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。

QkQ_k を訪問した時点で QiQ_i が SS に入り、QiQ_i は ii 番目に取り出されるまで SS に残ります。その間に取り出される Qk+1,…,Qi−1Q_{k+1}, \ldots, Q_{i-1} はそのときの SS の最小値なので、すべて QiQ_i より小さくなければなりません。

そこで、QiQ_i より前にある QiQ_i より大きい要素のうち最も後ろのものの位置を pip_i とします(なければ pi=0p_i = 0)。すると親の位置 kk の条件は

pi≤k≤i−1p_i \le k \le i - 1

で、選び方は i−pii - p_i 通りです(QpiQ_{p_i} 自身は大きくても、親として先に訪問されるので構いません)。

逆に、すべての ii についてこの範囲で親を選べば、ii 番目の時点で SS に残っている他の頂点 QmQ_m (m>im > i) は、親が ii より前にあるので条件から Qi<QmQ_i < Q_m となり、QiQ_i が最小として正しく取り出されます。したがって各 ii の選び方は独立で、答えは

∏i=1N−1(i−pi)\prod_{i=1}^{N-1} (i - p_i)

です。

pip_i は「直前にある自分より大きい要素の位置」なので、

  • 区間最大値のセグメント木で min_left を使って二分探索する(O(Nlog⁡N)O(N \log N))
  • 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で O(N)O(N))

のどちらでも求められます。

C++(セグメント木)
#include "ou-library/modint.hpp"
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
using mint = modint998244353;
void solve() {
LL(N);
VL(Q, N);
Q--;
mint ans = 1;
RMaxQ<ll> seg(Q);
rep(i, 1, N) {
ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; });
if (j)
j--;
ans *= i - j;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

min_left(i, x <= Q[i]) で「Ql,…,Qi−1Q_l, \ldots, Q_{i-1} がすべて QiQ_i 以下になる最小の ll」を求め、その 1 つ前が pip_i です。RMaxQ は区間最大値のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

cLay(ポインタをたどる)
#define MD 998244353
ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);

g[i] に pip_i を記録しておき、Qi−1Q_{i-1} から始めて自分より小さい間は g をたどることで pip_i を求めています。Q0=1Q_0 = 1 は最小なので、より大きい要素がなければ p=0p = 0 で止まります。