問題一覧 > 通常問題

No.2988 Min-Plus Convolution Query

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : tatyam
お気に入りにしたユーザー ProblemId : 11666 / 自分の提出
問題文最終更新日: 2024-12-13 00:25:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2024 (順位表) の他の問題:

Problem Statement

You are given integer sequences $A = (A_1, A_2, \dots, A_N)$ and $B = (B_1, B_2, \dots, B_N)$ of length $N$. Here, $B$ is convex. That is, for each $i$ satisfying $2 \le i \le N - 1$, $B_i \le \dfrac{B_{i-1} + B_{i+1}}2$ holds.

You are given $Q$ queries. Process them in order.

In each query, you are given integers $p, x, k$. Assign $x$ to $A_p$, and then output $\displaystyle\min_{i+j=k} (A_i + B_j)$.

Input

$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$

Here, $\text{query}_i$ ($1 \le i \le Q$) denotes the $i$-th query. Each query is given in the following format.

$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$)
  • For each query:
    • $1 \le p \le N$
    • $|x| \le 10^9$
    • $2 \le k \le 2N$
  • All input values are integers.

Output

Output $Q$ lines. On the $i$-th line ($1 \le i \le Q$), output the answer to the $i$-th query.

Sample

Sample 1
Input
4 4
5 7 5 1
8 2 2 6
4 8 4
1 5 2
4 5 5
1 4 7
Output
7
13
7
7

Initially, $A = (5, 7, 5, 1), B = (8, 2, 2, 6)$.

  • In the $1$st query, assign $8$ to $A_4$, making $A = (5, 7, 5, 8)$. Then, $\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$.
  • In the $2$nd query, assign $5$ to $A_1$, making $A = (5, 7, 5, 8)$. Then, $\displaystyle\min_{i+j=2}(A_i + B_j) = \min(A_1 + B_1) = \min(13) = 13$.
  • In the $3$rd query, assign $5$ to $A_4$, making $A = (5, 7, 5, 5)$. Then, $\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$.
  • In the $4$th query, assign $4$ to $A_1$, making $A = (4, 7, 5, 5)$. Then, $\displaystyle\min_{i+j=7}(A_i + B_j) = \min(A_3 + B_4, A_4 + B_3) = \min(11, 7) = 7$.

Sample 2
Input
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
Output
-1165015504
1480713546
-861304397
-42747538
-1020836836
-1386994556
778779005
1480713546
-42747538
-36100178

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。