AtCoder Beginner Contest 484 E,F問題メモ

E - Subsegment Sum Finder

問題文

  • 長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられるので、(空でない)連続部分列であって総和が $L$ 以上 $R$ 以下であるものの個数を答えてください。
  • ただし、 $2$ つの連続部分列が列として一致していたとしても、それらを取り出した位置が異なるのであれば、それらは区別して数えるものとします。

制約

  • 入力は全て整数
  • $1 \le N \le 3 \times 10^5$
  • $-10^{18} \le L \le R \le 10^{18}$
  • $-10^{12} \le A_i \le 10^{12}$

解法

前からの累積和 $B$ を取り、それを Sorted List などに入れ昇順が保たれるように並べたものを $C$ とする。

L=-2  R=3
    A  3  -1  -4  -1   5
累積B  3   2  -2  -3   2  →  C: (-3, -2, 2, 2, 3)

$A_1$ が左端の区間については、$C$ の $L$ 以上 $R$ 以下の要素数の数があてはまる。

$A_2$ が左端の区間については、$B_i-B_1$ が $L$ 以上 $R$ 以下となる、$i \ge 2$ の要素数があてはまる。

つまり、

  • $B_1$ を対象から除くため、$B_1=3$ を $C$ から取り除く
  • $L'←L+B_1,R'←R+B_1$ とし、$B_i-B_1$ でなく $B_i$ を $C$ から直接検索できるようにする

としたうえで、$L'$ 以上 $R'$ 以下の要素数を求めれば良い。

$i$ を進めても同様に、$C$ から $B_{i-1}$ を取り除き、 $L',R'$ を更新し、その間の要素数を SortedList 上の二分探索などで調べていけばよい。

Python3

F - Make them monochrome

問題文

  • 長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ があります。各要素は $-1$ または正整数です。
  • 以下の $Q$ 個のクエリを処理してください。
  • タイプ $1$ : 1 i x
    • $A_i$ を $x$ に変更する。
  • タイプ $2$ : 2 l r
    • $A_l,A_{l+1},\dots,A_r$ に含まれる $-1$ をそれぞれ任意の正整数に置き換えることができるとき、 $A_l,A_{l+1},\dots,A_r$ を全て等しくできるなら Yes 、そうでないなら No と出力する。

制約

  • 入力は全て整数
  • $1 \le N,Q \le 3 \times 10^5$
  • $-1 \le A_i \le 10^6$
  • $A_i \neq 0$
  • タイプ $1$ のクエリは以下の制約を満たす
    • $1 \le i \le N$
    • $-1 \le x \le 10^6$
    • $x \neq 0$
  • タイプ $2$ のクエリは以下の制約を満たす
    • $1 \le l \le r \le N$

解法

セグ木の使い方さえ分かっていれば比較的簡単。

タイプ2において「区間内が全て $-1$」か、または「$-1$ 以外の全ての値が一緒」なら Yes である。
それが判別でき、区間同士のマージもできるような情報を載せておけばいい。

  • $(\min, \max)$
    • 区間内が全て $-1$ なら $\min=\max=-1$
    • そうでないなら、$\min$ は $-1$ を除いた最小値、$\max$ は最大値

Python3

programming_algorithm/contest_history/atcoder/2026/1114_abc484.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0