コンテンツにスキップ

ブログ

ABC480 B - Invalid Vote

NN 人の候補者がいて、候補者 ii の名前は SiS_i です(名前はすべて異なります)。MM 枚の投票用紙があり、投票用紙 jj には文字列 TjT_j が書かれています。各投票用紙は次のように扱われます。

  • TjT_j と名前が完全に一致する候補者がいれば、その候補者に 1 票入る。
  • そうでなく、TjT_j を 1 文字書き換えると名前が一致する候補者がちょうど 1 人いれば、その候補者に 1 票入る。
  • どちらでもなければ無効票になる。

各候補者の得票数を求める問題です(1≤N,M≤1001 \le N, M \le 100、1≤∣Si∣,∣Tj∣≤101 \le |S_i|, |T_j| \le 10)。

書かれているとおりに調べます。

「TjT_j を 1 文字書き換えると SiS_i に一致する」は、TjT_j と SiS_i の長さが等しく、異なる文字の位置がちょうど 1 か所であること(ハミング距離が 11 であること)と同じです。完全に一致する候補者がいないときは、この条件を満たす候補者を数え、ちょうど 1 人ならその人に 1 票を入れます。

計算量は、名前の長さの最大値を LL として O(NML)O(NML) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/string.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VS(S, N);
VS(T, M);
vl ans(N);
for (str t : T) {
if (contains(S, t)) {
ans[index(S, t)]++;
continue;
}
vl cand = indices_if(S, [&](str s) { return len(t) == len(s) && hamming_distance(t, s) == 1; });
if (len(cand) == 1) {
ans[cand[0]]++;
}
}
for (ll a : ans)
print(a);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

contains(S, t) は S に t が含まれるか、index(S, t) はその位置を返します。indices_if は条件を満たす要素の位置をすべて集めた列を返し、hamming_distance は長さの等しい 2 つの文字列で異なる文字の個数を返します。hamming_distance は長さが等しいことを前提にしているので、先に len(t) == len(s) を確かめています。

使用ライブラリ:cpp_include@9c33ee7

ABC480 A - ADjacent

2×22 \times 2 のグリッドの各マスに A, B, C, D が 1 つずつ書かれています。A のマスと D のマスが辺を共有しているかどうかを判定する問題です。

A か D が書かれたマスに印をつけます。印のついた 2 マスが同じ行か同じ列にあれば辺を共有していて、対角の位置にあれば辺を共有していません。

2×22 \times 2 のグリッドで辺を共有するマスの組は、上の行、下の行、左の列、右の列の 4 通りです。このどれかで 2 マスとも印がついていれば Yes です。

C++
#include "shogo-library/base/all"
void solve() {
STR(S, T);
aal<2, 2> tmp;
tmp[0][0] = S[0] == 'A' || S[0] == 'D';
tmp[0][1] = S[1] == 'A' || S[1] == 'D';
tmp[1][0] = T[0] == 'A' || T[0] == 'D';
tmp[1][1] = T[1] == 'A' || T[1] == 'D';
if (tmp[0][0] * tmp[0][1] + tmp[1][0] * tmp[1][1] + tmp[0][0] * tmp[1][0] + tmp[0][1] * tmp[1][1]) {
print("Yes");
} else {
print("No");
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tmp[i][j] は、そのマスに A か D が書かれていれば 11、そうでなければ 00 です。if の中の 4 つの積は、順に上の行、下の行、左の列、右の列の 2 マスがどちらも印つきかどうかを表しています。どれかが 11 なら和が正になり、Yes を出力します。

使用ライブラリ:cpp_include@9c33ee7

Uiua
&p⨬"No""Yes"/+⊂≡/×⟜/×∊"AD"[∩&sc]

[∩&sc] で 2 行を読んで 2×22 \times 2 の文字の配列にし、∊"AD" で A か D のマスが 11、それ以外が 00 の配列にします。

⟜/× で、この配列を残したまま、行の方向に掛け合わせた列ごとの積を作ります。続く ≡/× で行ごとの積を作り、⊂ で 2 つをつなぎます。この 4 つの値は、上の行、下の行、左の列、右の列の 2 マスがどちらも印つきかどうかです。/+ で足すと、隣接していれば 11、していなければ 00 になるので、⨬"No""Yes" でそれに応じた文字列を選んで &p で出力しています。

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

ShareOJ Programming Contest vol.1 E - Solicitation of Murder

NN 頂点 MM 辺の有向グラフが与えられます。辺 a→ba \to b は「囚人 aa は囚人 bb に殺意を持っている」ことを表します。「生存している a,ba, b で辺 a→ba \to b があるものを選び、bb を殺す」という操作を好きな回数行ったあと、生存している囚人の集合としてありうるものの個数を 998244353998244353 で割った余りを求める問題です。

テストケースは TT 個あり、NN の総和と MM の総和はそれぞれ 2×1052 \times 10^5 以下です。

グラフを強連結成分分解します。外から入ってくる辺がない強連結成分(入次数 00 の成分)を、ここでは始点成分と呼びます。

生存者の集合 SS がありうるのは、すべての始点成分に SS の頂点が 1 つ以上あるときで、そのときに限ります。

必要性. 始点成分 CC の頂点を殺せるのは、CC の頂点だけです。CC の頂点が全員殺されたとすると、CC の中で最後に殺された頂点を殺した頂点は CC の中にいて、そのあとに殺されています。これは最後であることに反します。よって、CC には生存者が残ります。

十分性. どの頂点も、どこかの始点成分から到達できます。強連結成分の中では互いに到達できるので、すべての始点成分に SS の頂点があれば、すべての頂点が SS のどれかの頂点から到達できます。そこで、SS からの距離 d(v)d(v) を考え、SS にない頂点を d(v)d(v) が大きい順に殺します。d(v)=t≥1d(v) = t \ge 1 の頂点 vv には、d(u)=t−1d(u) = t - 1 で辺 u→vu \to v がある頂点 uu があります。uu は SS の頂点か、vv よりあとに殺す頂点なので、vv を殺すときにはまだ生きています。したがって、vv を殺せます。

条件は成分ごとに独立です。

  • 始点成分 CC では、空でない部分集合ならどれでもよいので 2∣C∣−12^{|C|} - 1 通りです。
  • それ以外の成分 CC では、制限がないので 2∣C∣2^{|C|} 通りです。

これらの積が答えです。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph.hpp"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
rep(M) {
LL(a, b);
a--, b--;
g.add_directed_edge(a, b);
}
vl dp(N);
auto tmp = strongly_connected_components(g);
mint ans = 1;
for (const auto &f : tmp) {
ll x = 0;
for (ll u : f) {
x |= dp[u];
}
ans *= mint(2).pow(f.size()) - !x;
for (ll u : f) {
for (ll v : g[u])
dp[v] = 1;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

strongly_connected_components は強連結成分をトポロジカル順に返します。dp[v] は「すでに処理した成分から vv に入る辺がある」ことを表すフラグです。成分 f を見る時点で、f に外から入る辺はすべて前の成分から来ているので、x が 00 なら f は始点成分です。成分の中の辺で立つフラグは、x を求めたあとに立てています。

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

ShareOJ Programming Contest vol.1 D - Integers and Operators

整数のカード A1,…,ANA_1, \dots, A_N と、+ か ^(XOR)が書かれた演算子のカード NN 枚があります。x=0x = 0 から始めて、整数と演算子のカードを 1 枚ずつ選んで xx を更新することを NN 回繰り返します。最後の xx としてありうる最大値と最小値を求める問題です。N≤8N \le 8 です。

N≤8N \le 8 と小さいので、カードの使い方をすべて試します。

ii 回目に使う整数のカードと演算子のカードを決めれば、手続きが 1 通りに決まります。つまり、整数のカードの並べ方と演算子のカードの並べ方の組をすべて試せばよいです。

ただし、そのままでは 8!×8!≈1.6×1098! \times 8! \approx 1.6 \times 10^9 通りになり、間に合いません。演算子のカードには + と ^ の 2 種類しかないので、並べ方を記号の列として見ると重複がたくさんあります。重複を除くと、+ が cc 枚なら (Nc)≤(84)=70\binom{N}{c} \le \binom{8}{4} = 70 通りです。全体では 8!×70≈2.8×1068! \times 70 \approx 2.8 \times 10^6 通りになり、1 通りあたり NN 回の計算で済みます。

Python
from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
op = input().split()
l = []
for p in permutations(op):
l.append(p)
l = list(set(l))
ans0 = 10**18
ans1 = -(10**18)
for t in l:
for p in permutations(A):
x = 0
for i, c in zip(t, p):
if i == "+":
x += c
else:
x ^= c
ans0 = min(ans0, x)
ans1 = max(ans1, x)
print(ans1, ans0)

演算子の並べ方を set に入れて重複を除き、l にしています。ans1 が最大値、ans0 が最小値です。

ShareOJ Programming Contest vol.1 C - Add to Multiples

はじめすべて 00 の長さ NN の数列 AA があります。「kk と整数 xx を選び、kk の倍数番目の要素すべてに xx を足す」という操作を NN 回以下行って、A=(X1,…,XN)A = (X_1, \dots, X_N) にする操作列を 1 つ答える問題です。ただし ∣x∣≤1018|x| \le 10^{18} でなければなりません。

テストケースは TT 個あり、NN の総和は 3×1053 \times 10^5 以下、∣Xi∣≤109|X_i| \le 10^9 です。

kk を選ぶ操作で変わるのは Ak,A2k,…A_k, A_{2k}, \dots なので、kk より小さい番号の要素は変わりません。そこで、i=1,2,…,Ni = 1, 2, \dots, N の順に AiA_i を合わせていきます。

ii を見る時点で、AiA_i を変える操作は ii の約数 k<ik < i を選んだものだけで、それらはすでに済んでいます。したがって、今の AiA_i と XiX_i の差 x=Xi−Aix = X_i - A_i を求めて、k=ik = i で xx を足せば Ai=XiA_i = X_i になります。このあとの操作では AiA_i は変わりません。

各 ii について操作は高々 1 回なので、操作は NN 回以下です。

ii のときに足す値を xix_i とすると、Xi=∑d∣ixdX_i = \sum_{d \mid i} x_d が成り立ちます。これをメビウスの反転公式で解くと、xi=∑d∣iμ(i/d)Xdx_i = \sum_{d \mid i} \mu(i / d) X_d となります。μ\mu の値は −1,0,1-1, 0, 1 のどれかなので、∣xi∣|x_i| は (ii の約数の個数)×109\times 10^9 以下です。3×1053 \times 10^5 以下の整数の約数は多くても 180180 個なので、∣xi∣≤1018|x_i| \le 10^{18} を十分に満たします。

k=ik = i で足すときに書き換える要素は ⌊N/i⌋\lfloor N / i \rfloor 個です。合計は ∑i=1NN/i=O(Nlog⁡N)\sum_{i=1}^{N} N / i = O(N \log N) になります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(1, N + 1):
k = A[i - 1]
if k == 0:
continue
ans.append((i, k))
for j in range(1, N // i + 1):
A[i * j - 1] -= k
print(len(ans))
for i, j in ans:
print(i, j)

A を「あと足す必要がある量」として持ち、操作のたびにそこから引いています。k は足す値 xx で、00 のときは操作を省いています。

ShareOJ Programming Contest vol.1 B - One Digit Factorization

正整数 NN が、11 桁の正整数だけの積で表せるかを判定する問題です。テストケースは TT 個あり、1≤T≤1001 \le T \le 100、1≤N≤10181 \le N \le 10^{18} です。

NN が 11 桁の正整数だけの積で表せることは、NN の素因数が 2,3,5,72, 3, 5, 7 だけであることと同じです。

  • 11 桁の正整数 1,2,…,91, 2, \dots, 9 は、どれも素因数が 2,3,5,72, 3, 5, 7 だけです。そのため、これらの積の素因数も 2,3,5,72, 3, 5, 7 だけです。
  • 逆に、素因数が 2,3,5,72, 3, 5, 7 だけなら、NN を素因数分解した式がそのまま 11 桁の正整数の積になっています。N=1N = 1 のときも、11 自体が 11 桁なので表せます。

NN を 2,3,5,72, 3, 5, 7 でそれぞれ割り切れなくなるまで割り、最後に 11 が残れば Yes、そうでなければ No です。

1 回割るたびに NN は半分以下になるので、割る回数は log⁡21018<60\log_2 10^{18} < 60 回ほどで済みます。

Python
for _ in range(int(input())):
N = int(input())
for p in [2, 3, 5, 7]:
while N % p == 0:
N //= p
if N == 1:
print("Yes")
else:
print("No")

ShareOJ Programming Contest vol.1 A - Welcome to ShareOJ!

英小文字からなる文字列 SS が与えられるので、末尾が oj かどうかを判定する問題です。テストケースは TT 個あり、1≤T≤1001 \le T \le 100、1≤∣S∣≤1001 \le |S| \le 100 です。

各テストケースについて、SS の末尾が oj かどうかをそのまま調べます。

Python なら str.endswith が使えます。∣S∣=1|S| = 1 のときも、"x".endswith("oj") は False になるので、長さを別に気にする必要はありません。

Python
for _ in range(int(input())):
if input().endswith("oj"):
print("Yes")
else:
print("No")

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

ダイクストラ法のリンク集

ダイクストラ法について、参考になる記事や資料をまとめました。

ダイクストラ法は、辺の重みがすべて非負のグラフで、1 つの始点から各頂点への最短距離を求めるアルゴリズムです。「まだ確定していない頂点のうち、暫定の距離が最小のもの」を確定させ、そこから出る辺で隣の頂点の距離を更新する、という操作を繰り返します。優先度付きキュー(二分ヒープ)を使うと O((V+E)log⁡V)O((V + E) \log V)、ヒープを使わずに毎回最小の頂点を探すと O(V2)O(V^2) です。負の重みの辺があると正しく動かないので、そのときはベルマン-フォード法などを使います。

競プロでよく書く実装では、距離を更新するたびに (距離, 頂点) をキューに追加し、古い要素は消さずに残します。そのため、取り出した距離が記録している距離より大きいときは読み飛ばす処理(if d > dist[v]: continue)が必要です。これがないと計算量が悪化します。また、距離は 64 bit 整数で持つ必要があることが多いです。

AtCoder Library(ACL)にはダイクストラ法がなく、AtCoder Algorithm Lectures にも今のところ最短経路の講座はありません。

  • 最短経路問題総特集!!!BFSから拡張ダイクストラまで(ageprocpp、Qiita)
    • BFS、ベルマン-フォード法、ダイクストラ法、ワーシャル-フロイド法、経路復元、拡張ダイクストラ(頂点を増やしたグラフ上のダイクストラ法)までを、文章で順に説明しています。ダイクストラ法の手順には、古い要素を読み飛ばす処理も書かれています。コードはほとんどありません。
    • ワーシャル-フロイド法の節の「途中で辺の長さが変わるクエリがあっても O(V2)O(V^2) で対応できる」は、辺が短くなる場合に限った話です。
  • ダイクストラ法による単一始点最短経路を求めるアルゴリズム(アルゴリズムロジック)
    • 手順、計算量、C++ の実装、経路復元、正当性の考え方を、図を使って説明しています。
    • キューに入れる距離の型が pair<long, int> の long です。AtCoder では 64 bit ですが、Windows などでは 32 bit なので、書き写すときは long long にしてください。
  • ダイクストラ法・ダイクストラ法の高速化(アルゴ式)
    • 問題を解きながら手順を学ぶ形式です。まずヒープを使わない O(N2+M)O(N^2 + M) の方法を実装し、次の問題でヒープを使って高速化します。
  • ダイクストラ法のよくあるミスと落し方(snuke)
    • 古い要素を読み飛ばす処理を忘れる、最大ヒープのまま使う、負の辺のあるグラフに使う、といったよくあるミスで、実際にどれだけ遅くなるかを撃墜ケースつきで説明しています。自分の実装を確かめるのに役立ちます。
  • Dijkstra 法(Kyopro Encyclopedia of Algorithms)
    • 定義、計算量、高速化の要点(キューに入れる前の枝刈り、0-1 BFS、拡張したグラフでの利用など)を短くまとめた辞典の項目です。
  • 色々なダイクストラ高速化(yosupo、スライド)
    • キューに入れる前の枝刈り、辺の重みが 0/10/1 のときの 0-1 BFS、重みが小さい整数のときの方法、Radix Heap などの高速化を紹介しています。C++ です。
  • 01-BFSのちょっと丁寧な解説(ARMERIA)
    • ダイクストラ法、BFS、01-BFS を「暫定の距離が最小の頂点を取り出す」という共通点から説明しています。C++ と Python のコードがあります。
  • heapq --- ヒープキューアルゴリズム(Python 公式ドキュメント)
    • heapq は最小ヒープで、(距離, 頂点) のタプルをそのまま入れられます。「優先度キュー実装の注釈」の節では、優先度が変わった要素に無効の印をつけて残し、新しい要素を追加し直す方法を紹介しています。ダイクストラ法で古い要素を読み飛ばすのと同じ考え方です。
  • Dijkstra (単一始点最短路)(Luzhiled’s Library)
    • C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、long long を指定してください。
  • Yosupo Library Checker - Shortest Path(けんちょんの競プロ精進記録)
    • 下の Library Checker の問題の解説で、ダイクストラ法での経路復元の方法を説明しています。C++ のテンプレートつきです。
  • ダイクストラ法(日本語版 Wikipedia)
    • 擬似コード、ヒープの種類ごとの計算量、ビー玉と紐のたとえによる説明があります。擬似コードはキューの中の値を書き換える(decrease-key)形で、競プロでよく書く「追加して読み飛ばす」形とは違います。
  • Dijkstra’s algorithm(英語版 Wikipedia)
    • 歴史、擬似コード、正当性の証明、計算量、双方向ダイクストラ法などの変種まで載っています。キューに追加して読み飛ばす形の実装にも触れています。
  • Dijkstra - finding shortest paths from given vertex・Dijkstra on sparse graphs(cp-algorithms)
    • 前者はヒープを使わない O(n2+m)O(n^2 + m) の方法を正当性の証明と経路復元つきで、後者は set と priority_queue を使う O(mlog⁡n)O(m \log n) の方法を説明しています。後者には、読み飛ばす処理がないと O(nm)O(nm) まで悪化しうることも書かれています。
    • コードは距離を int で持っています。また、後者でフィボナッチヒープを使った O(nlog⁡n+m)O(n \log n + m) を「理論上の下限」としているのは、比較に基づく方法に限った話です。
  • Shortest Paths with Non-Negative Edge Weights(USACO Guide)
    • 後半がダイクストラ法の節で、C++・Java・Python の実装と問題の一覧があります。読み飛ばす処理を外すと TLE する例も説明しています。前半はベルマン-フォード法とワーシャル-フロイド法です。
  • ABC477 E - Wheel Distance
    • 中心の頂点から各頂点への最短距離をダイクストラ法で前計算し、各クエリに場合分けで答えています。

累積和・いもす法のリンク集

累積和といもす法について、参考になる記事や資料をまとめました。

累積和は、数列 a0,…,aN−1a_0, \dots, a_{N-1} に対して S0=0S_0 = 0、Si+1=Si+aiS_{i+1} = S_i + a_i を前計算しておき、区間 [l,r)[l, r) の和を Sr−SlS_r - S_l で O(1)O(1) で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。

いもす法は、その逆の操作です。「区間 [l,r)[l, r) に xx を足す」を ll に +x+x、rr に −x-x と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。

資料によって、区間を半開区間 [l,r)[l, r) で書くものと閉区間 [l,r][l, r] で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。

  • 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
    • 半開区間と S0=0S_0 = 0 の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
    • 2-1 節の検算で「s13=a1+⋯+a12s_{13} = a_1 + \dots + a_{12}」のように添字が 1 ずれています(定義どおりなら a0a_0 からの和です)。差をとった結果は正しいです。
  • 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
  • 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
    • 最後の「更新がある場合」で 2 次元 BIT の計算量を O(log⁡HW)O(\log HW) としていますが、正しくは O(log⁡Hlog⁡W)O(\log H \log W) です。

コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。

  • いもす法(いもす研)
    • 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
    • 区間の右端 EiE_i が TT になり得るのに、配列を大きさ TT で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
    • 2 次元の説明で、(Ai,Di)(A_i, D_i) を「右上」、(Bi,Ci)(B_i, C_i) を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも −1-1 を足す点なので、結果は変わりません。
  • Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
    • itertools.accumulate の使い方の解説です。initial=0 を指定すると先頭に 00 がついた長さ N+1N + 1 の累積和になること、max や operator.mul を渡して累積 max や累積積を作れることが分かります。

木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。

  • AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
    • 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで O(N+Q)O(N + Q) にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
  • AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
    • 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
  • いもす法のカテゴリ(けんちょんの競プロ精進記録)
    • いもす法を使う問題の解説がまとまっていて、問題集としても使えます。

累積和・いもす法そのものを解説した講座はありません。

  • 転置原理入門
    • 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
  • 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
    • 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
  • Summed-area table(英語版 Wikipedia)
    • 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。dd 次元への一般化の式も載っています。dd 次元の段落では、2 次元の段落と点の名前の付け方が入れ替わっています。
  • Introduction to Prefix Sums(USACO Guide)
    • 1 次元の累積和の入門で、C++・Java・Python のコードと練習問題の一覧があります。
    • 最初の Python のコードは psums[-1] を psum[-1] と書き間違えていて、そのままでは動きません。
  • More on Prefix Sums(USACO Guide)
    • 最大部分配列和、2 次元の累積和(構築の様子が見られる図つき)、差分配列(いもす法)を扱っています。区間は閉区間で書かれています。
  • An Introduction To Difference Arrays(arujbansal、Codeforces)
    • 1 次元の差分配列の短い入門です。閉区間 [L,R][L, R] で書いていて、配列を N+2N + 2 の大きさで取る理由も説明しています。

ABC479 E - Larger Component

NN 頂点の木があり、辺 ii は頂点 AiA_i と BiB_i を結びます(NN は奇数)。各 i=1,…,N−1i = 1, \dots, N - 1 について、辺 ii を取り除いてできる 2 つの連結成分のうち、頂点数が多い方のすべての頂点 vv の xvx_v に ii を足します。最終的な x1,…,xNx_1, \dots, x_N を求める問題です(3≤N≤2×105−13 \le N \le 2 \times 10^5 - 1)。

頂点 11 を根とする根付き木で考えます。辺 ii が親 uu と子 vv を結ぶとき、辺 ii を取り除いてできる連結成分は「vv の部分木」と「それ以外」です。vv の部分木の頂点数 szv\mathrm{sz}_v は、葉の側から足し合わせれば全頂点について O(N)O(N) で求められます。

  • 2 szv>N2 \, \mathrm{sz}_v > N なら、vv の部分木の全頂点に ii を足します。
  • そうでなければ、vv の部分木以外の全頂点に ii を足します。これは「全頂点に ii を足し、vv の部分木の全頂点から ii を引く」と言い換えられます。

どちらも「ある頂点の部分木全体に値を足す」操作になります(全頂点は根の部分木です)。これは木の上のいもす法で処理できます。頂点 ww の部分木全体に cc を足すときは、配列の ww の位置にだけ cc を足しておきます。すべて記録したら、根から葉に向かって親の値を子に足していきます。すると、各頂点の値は根からその頂点までの経路上の記録の合計になります。これは、その頂点を部分木に含む頂点への加算の合計なので、求める xvx_v です。

計算量は O(N)O(N) です。

Python
N = int(input())
G = [[] for _ in range(N)]
for i in range(1, N):
a, b = map(int, input().split())
G[a - 1].append((b - 1, i))
G[b - 1].append((a - 1, i))
par = [-1] * N
pid = [0] * N
order = [0]
for u in order:
for v, i in G[u]:
if v != par[u]:
par[v] = u
pid[v] = i
order.append(v)
sz = [1] * N
for v in reversed(order[1:]):
sz[par[v]] += sz[v]
x = [0] * N
for v in order[1:]:
i = pid[v]
if sz[v] * 2 > N:
x[v] += i
else:
x[0] += i
x[v] -= i
for v in order[1:]:
x[v] += x[par[v]]
print(*x)

頂点 11(コード上は 0)から BFS して、order に訪問順、par[v] に親、pid[v] に親と結ぶ辺の番号を記録しています。order を逆順に見ると子が親より先に来るので、部分木のサイズ sz が求まります。最後に order の順に親の値を子に足すことで、いもす法の記録を伝えています。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
void solve() {
LL(N);
Tree<> tree(N);
tree.read();
RootedTree<> rooted(tree, 0);
vl sz(N, 1);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
sz[u] += sz[v];
}
}
vl ans(N, 0);
for (auto e : rooted.edges()) {
ll u = e.src;
ll v = e.dst;
if (rooted.depth[u] > rooted.depth[v]) {
std::swap(u, v);
}
if (sz[v] * 2 > N) {
ans[v] += e.id + 1;
} else {
ans[0] += e.id + 1;
ans[v] -= e.id + 1;
}
}
for (ll u : rooted.preorder) {
for (ll v : rooted.child[u]) {
ans[v] += ans[u];
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RootedTree は頂点 0 を根とする根付き木で、postorder(帰りがけ順)、preorder(行きがけ順)、child、depth を持っています。各辺について深い方の端点を v とし、v が子になるようにしています。辺の番号 e.id は 0 始まりなので、11 を足しています。

使用ライブラリ: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

ABC479 C - Bento Packing

NN 個のおかずがあり、ii 個目のおいしさは AiA_i、体積は BiB_i です。体積の合計が WW 以下になるようにおかずを選ぶとき、おいしさの合計の最大値を求める問題です。1 つも選ばなくてもかまいません(1≤N≤201 \le N \le 20、1≤W,Ai,Bi≤1091 \le W, A_i, B_i \le 10^9)。

N≤20N \le 20 と小さいので、おかずの選び方 2N2^N 通りをすべて調べられます。それぞれについて体積の合計とおいしさの合計を求め、体積の合計が WW 以下のもののうち、おいしさの合計の最大値が答えです。

選び方は、00 以上 2N2^N 未満の整数 ii で表します。ii を 2 進数で書いたとき下から jj 桁目が 11 なら jj 個目のおかずを選ぶ、と決めれば、ii を 00 から 2N−12^N - 1 まで動かすことですべての選び方を 1 回ずつ調べられます。計算量は O(2NN)O(2^N N) です。

WW や BiB_i が大きいので、体積を添字にするナップサック DP は使えません。

Python
N, W = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(1 << N):
a = 0
b = 0
for j in range(N):
if (i >> j) & 1:
a += AB[j][0]
b += AB[j][1]
if b <= W:
ans = max(ans, a)
print(ans)

(i >> j) & 1 で、ii の下から jj 桁目(0 始まり)が 11 かどうか、つまり jj 個目のおかずを選ぶかどうかを調べています。a がおいしさの合計、b が体積の合計です。i = 0 は何も選ばない場合にあたり、このとき a = 0 なので、ans の初期値 00 と同じです。

ABC479 B - Longest Rainy Streak

S(晴れ)と R(雨)からなる長さ NN の文字列 SS が与えられます。雨が連続した日数の最大値を求める問題です。雨の日が 1 日もなければ答えは 00 です(1≤N≤1001 \le N \le 100)。

SS を S の位置で区切ると、R だけが続く部分に分かれます。それぞれの長さが雨の連続した日数なので、その最大値が答えです。

Python
input()
print(max(map(len, input().split("S"))))

split("S") で S の位置で区切ると、R だけからなる文字列のリストになります。S が並んでいる所や両端では空文字列もできますが、長さ 00 なので最大値には影響しません。雨の日がないときは空文字列だけになり、答えは 00 になります。

Uiua
⬚0/↥⊜/+.=@R&sc◌&sc

&sc◌&sc で NN を読み捨ててから SS を読み、=@R で雨の日が 11、晴れの日が 00 の列にします。

. でこの列を複製し、⊜/+ で 11 が続く部分ごとに区切って和をとると、雨が連続した日数の列になります。/↥ でその最大値を求めます。雨の日がないときは列が空になるので、⬚0 で 00 を出すようにしています。

ABC479 A - Odd Index Sum

長さ NN の整数列 AA が与えられます。添字が奇数の要素 A1,A3,A5,…A_1, A_3, A_5, \dots の和を求める問題です(1≤N≤1001 \le N \le 100、1≤Ai≤1001 \le A_i \le 100)。

A1,A3,A5,…A_1, A_3, A_5, \dots は、先頭から 1 つおきにとった要素です。これを取り出して足せば答えになります。

Python
input()
print(sum(map(int, input().split()[::2])))

1 行目の NN は使わないので読み捨てています。0 始まりで偶数番目の要素が、問題文の 1 始まりで奇数番目の要素にあたるので、[::2] で先頭から 1 つおきに取り出しています。

Uiua
/+×◿2+1°⊏⊜⋕⊸≠@ &sc◌&sc

&sc◌&sc で NN を読み捨ててから 2 行目を読み、⊜⋕⊸≠@ で空白区切りの整数列 AA にします。

°⊏ で AA の添字の列 [0,1,…,N−1][0, 1, \dots, N - 1] を作り、+1 で 1 始まりにします。◿2 で 2 で割った余りをとると、添字が奇数の位置が 11、偶数の位置が 00 になります。これを × で AA に掛けて、/+ で足し合わせています。

DOJ Beginner Contest 11 G - Déjà vu

正の整数列 a=(a1,a2,…,aN)a = (a_1, a_2, \dots, a_N) が与えられます。空でない部分列 bb に対して、次の操作を何回でも行えます。

  • 素数 pp を 1 つ選び、bb の要素のうち pp で割り切れるものをすべて同時に pp で割る。

bb の要素をすべて同じ値にするとき、その値の最大値を f(b)f(b) とします。すべての空でない部分列 bb についての f(b)f(b) の和を 998244353998244353 で割った余りを求める問題です。

ai≤2×105a_i \le 2 \times 10^5 で、NN の総和は 5×1055 \times 10^5 以下、max⁡a\max a の総和は 2×1052 \times 10^5 以下です。

素数 pp ごとに考えます。bb の各要素を素因数分解したときの pp の指数を見ると、pp を選ぶ操作は、正の指数をすべて 11 ずつ減らし、00 の指数はそのままにします。

最後にすべての指数を e>0e > 0 でそろえるには、正の指数どうしの差は変わらず、00 の指数は増えないので、はじめからすべての指数が ee でなければなりません。そうでなければ、すべて 00 にそろえるしかありません。

よって、f(b)f(b) は「bb のすべての要素で指数が等しい素数」について pep^e を掛けたものです。ここから次のことがいえます。

  • bb のすべての要素が c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形で書ける   ⟺  \iff cc を割り切るどの素数についても、bb のすべての要素の指数が cc の指数と等しい   ⟺  \iff f(b)=c⋅df(b) = c \cdot d(gcd⁡(c,d)=1\gcd(c, d) = 1)と書ける

f(b)=cf(b) = c となる部分列の個数

Section titled “f(b)=cf(b) = cf(b)=c となる部分列の個数”

aa の要素のうち、c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形のものの個数を tct_c とします。これらだけからなる空でない部分列は 2tc−12^{t_c} - 1 個あり、上の性質から、これはちょうど f(b)=c⋅jf(b) = c \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)となる部分列全体です。f(b)=cf(b) = c となる部分列の個数を gcg_c とすると、

gc=2tc−1−∑j≥2, gcd⁡(c,j)=1gcjg_c = 2^{t_c} - 1 - \sum_{j \ge 2,\ \gcd(c, j) = 1} g_{cj}

です。cc の大きい順に計算すれば、右辺の gcjg_{cj} はすでに求まっています。答えは ∑cc⋅gc\sum_c c \cdot g_c です。

M=max⁡aM = \max a とすると、cc ごとに M/cM / c 個の倍数を見るので、全体で O(Mlog⁡M)O(M \log M) 回の gcd⁡\gcd 計算です。

Python
from math import gcd
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = max(A)
tmp0 = [0] * (M + 1)
tmp1 = [0] * (M + 1)
for a in A:
tmp0[a] += 1
ans = 0
for i in reversed(range(1, M + 1)):
t = tmp0[i]
u = 0
for j in range(2, M // i + 1):
if gcd(i, j) != 1:
continue
t += tmp0[i * j]
u += tmp1[i * j]
v = (pow(2, t, MOD) - u - 1) % MOD
tmp1[i] = v
ans += i * v
ans %= MOD
print(ans)

tmp0[x] は値 xx の要素の個数、tmp1[c] は gcg_c です。t が tct_c、u が ∑gcj\sum g_{cj} にあたります。

DOJ Beginner Contest 11 F - Laboratory

NN 種類の微生物があり、ii 番の微生物の xx 日目の個体数は Ai+BixA_i + B_i x です。BiB_i を成長係数とよびます。

xx 日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。

  • 成長係数の小さい順
  • xx 日目の個体数の少ない順

どちらも、値が同じなら番号の小さい順に並べます。KK 種類以上選べる最も早い日 x≥0x \ge 0 を求める問題です。存在しなければ -1 を出力します。

1≤K≤N≤1051 \le K \le N \le 10^5、1≤Ai,Bi≤1091 \le A_i, B_i \le 10^9 です。

固定した日に選べる最大の種類数

Section titled “固定した日に選べる最大の種類数”

微生物を (Bi,i)(B_i, i) の昇順に並べておきます。選んだ微生物の並びがこの順で、(Ai+Bix,i)(A_i + B_i x, i) も昇順になっていれば条件を満たします。

つまり、(Bi,i)(B_i, i) の順に並べた列で、(Ai+Bix,i)(A_i + B_i x, i) の最長狭義増加部分列(LIS)の長さが、xx 日目に選べる最大の種類数です。LIS の長さは O(Nlog⁡N)O(N \log N) で求まります。

xx 日目に選べる組は、x+1x + 1 日目にも選べます。

(Bp,p)<(Bq,q)(B_p, p) < (B_q, q) の 2 つが xx 日目に条件を満たしているとします。1 日たつと、個体数の差 (Aq+Bqx)−(Ap+Bpx)(A_q + B_q x) - (A_p + B_p x) は Bq−Bp≥0B_q - B_p \ge 0 だけ増えます。Bp<BqB_p < B_q なら差が増えるので順序は保たれ、Bp=BqB_p = B_q なら差が変わらないので順序も変わりません。

よって、選べる最大の種類数は xx について広義単調増加です。KK 種類以上選べる最小の xx を二分探索で求めます。

問題文にあるとおり、答えが存在すれば 10910^9 以下です。x=109+1x = 10^9 + 1 で KK 種類選べなければ -1 を出力し、選べれば [0,109+1][0, 10^9 + 1] で二分探索します。

全体で O(Nlog⁡Nlog⁡max⁡)O(N \log N \log \max) です。

Python
from operator import itemgetter
from bisect import bisect_left
for _ in range(int(input())):
N, K = map(int, input().split())
ABi = [tuple(map(int, input().split())) + (i,) for i in range(N)]
ABi.sort(key=itemgetter(1))
def q(x):
dp = [(2 * 10**18, 10**18)] * (N + 1)
for a, b, i in ABi:
dp[bisect_left(dp, (a + b * x, i))] = (a + b * x, i)
for i in range(N + 1):
if dp[i][0] >= 2 * 10**18:
return i
assert False
ok = 10**9 + 1
ng = -1
if q(ok) < K:
print(-1)
continue
while ok > ng + 1:
mid = (ok + ng) // 2
if q(mid) >= K:
ok = mid
else:
ng = mid
print(ok)

sort は安定なので、BiB_i だけをキーにしても、BiB_i が等しいものは番号順に並びます。q(x) は (Ai+Bix,i)(A_i + B_i x, i) の LIS の長さを返します。dp[k] は長さ k+1k + 1 の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。

DOJ Beginner Contest 11 D - Cipher Guess

英大文字だけからなる NN 個の暗号文の単語 C1,C2,…,CNC_1, C_2, \dots, C_N と、平文の単語 SS が与えられます。

単一換字式暗号(同じ文字は同じ文字に、異なる文字は異なる文字に置き換える)で SS を変換した結果になりうる単語を、候補とよびます。候補のうち暗号文に最も多く現れる単語を求める問題です。同数なら辞書順で最小のものを答え、候補がなければ -1 を出力します。

∣Ci∣,∣S∣≤20|C_i|, |S| \le 20 で、NN の総和は 10510^5 以下です。

単語 CC が候補であるための条件は、「SS で同じ文字が現れる位置の組」と「CC で同じ文字が現れる位置の組」が一致することです。

たとえば ABBA なら、A の位置が {0,3}\{0, 3\}、B の位置が {1,2}\{1, 2\} です。XYYX も {0,3},{1,2}\{0, 3\}, \{1, 2\} に分かれるので候補です。XYYY は {0},{1,2,3}\{0\}, \{1, 2, 3\} になるので候補ではありません。

そこで、各単語について文字ごとの出現位置のリストを作り、それをソートしたものを比べます。長さが違う単語は、位置の範囲が違うので自然に一致しません。

候補を Counter で数えます。あらかじめ CC を辞書順にソートしておくと、Counter には辞書順に単語が入ります。most_common は同数の要素を入れた順に返すので、most_common(1) で「最多で、同数なら辞書順最小」の単語が得られます。

単語の長さを LL とすると、全体で O(NL+Nlog⁡N)O(NL + N \log N) です。

Python
from collections import defaultdict, Counter
for _ in range(int(input())):
N = int(input())
C = input().split()
C.sort()
S = input()
d = defaultdict(list)
for i, a in enumerate(S):
d[a].append(i)
ans = Counter()
X = sorted(d.values())
for f in C:
d = defaultdict(list)
for i, a in enumerate(f):
d[a].append(i)
Y = sorted(d.values())
if X == Y:
ans[f] += 1
if ans:
print(ans.most_common(1)[0][0])
else:
print(-1)