目次
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 上の二分探索などで調べていけばよい。
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$ は最大値

