No.2988 Min-Plus Convolution Query
tatyam問題文最終更新日: 2024-12-13 00:25:27
問題文
長さ $N$ の整数列 $A = (A_1, A_2, \dots, A_N)$ と $B = (B_1, B_2, \dots, B_N)$ が与えられます。 ここで、$B$ は下に凸です。すなわち、$2 \le i \le N - 1$ を満たす各 $i$ について、$B_i \le \dfrac{B_{i-1} + B_{i+1}}2$ が成り立ちます。
$Q$ 個のクエリが与えられるので、順に処理してください。
各クエリでは、整数 $p, x, k$ が与えられるので、$A_p$ に $x$ を代入したのち、$\displaystyle\min_{i+j=k} (A_i + B_j)$ を出力してください。
入力
$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
ここで、$\text{query}_i$ ($1 \le i \le Q$) は $i$ 番目のクエリを表す。各クエリは以下の形式で与えられる。
$p$ $x$ $k$
- $1 \le N, Q \le 2 \times 10^5$
- $|A_i| \le 10^9$ ($1 \le i \le N$)
- $|B_i| \le 10^9$ ($1 \le i \le N$)
- $B_i \le \dfrac{B_{i-1} + B_{i+1}}2$ ($2 \le i \le N - 1$)
- 各クエリについて:
- $1 \le p \le N$
- $|x| \le 10^9$
- $2 \le k \le 2N$
- 入力される値はすべて整数である
出力
$Q$ 行出力せよ。$i$ 行目 ($1 \le i \le Q$) には、$i$ 番目のクエリの答えを出力せよ。
サンプル
サンプル1
入力
4 4 5 7 5 1 8 2 2 6 4 8 4 1 5 2 4 5 5 1 4 7
出力
7 13 7 7
はじめ、$A = (5, 7, 5, 1), B = (8, 2, 2, 6)$ です。
- $1$ 番目のクエリでは、$A_4$ に $8$ を代入し、$A = (5, 7, 5, 8)$ とします。このとき、$\displaystyle\min_{i+j=4}(A_i + B_j) = \min(A_1 + B_3, A_2 + B_2, A_3 + B_1) = \min(7, 9, 13) = 7$ です。
- $2$ 番目のクエリでは、$A_1$ に $5$ を代入し、$A = (5, 7, 5, 8)$ とします。このとき、$\displaystyle\min_{i+j=2}(A_i + B_j) = \min(A_1 + B_1) = \min(13) = 13$ です。
- $3$ 番目のクエリでは、$A_4$ に $5$ を代入し、$A = (5, 7, 5, 5)$ とします。このとき、$\displaystyle\min_{i+j=5}(A_i + B_j) = \min(A_1 + B_4, A_2 + B_3, A_3 + B_2, A_4 + B_1) = \min(11, 9, 7, 13) = 7$ です。
- $4$ 番目のクエリでは、$A_1$ に $4$ を代入し、$A = (4, 7, 5, 5)$ とします。このとき、$\displaystyle\min_{i+j=7}(A_i + B_j) = \min(A_3 + B_4, A_4 + B_3) = \min(11, 7) = 7$ です。
サンプル2
入力
6 10 952307430 620871373 -571153654 -685400002 32071513 -657229960 528406116 -173528425 -593861850 -758113254 -449683182 -68171691 6 605052734 6 4 783115046 2 6 -793132706 12 2 871488395 4 2 679092740 8 4 360513340 9 6 427897700 3 4 567483968 2 2 634051142 4 4 -623295761 11
出力
-1165015504 1480713546 -861304397 -42747538 -1020836836 -1386994556 778779005 1480713546 -42747538 -36100178
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。