No.2988 Min-Plus Convolution Query
タグ : / 解いたユーザー数 16
作問者 :
tatyam
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もしくは右上の雲マークをクリックしてアカウントを作成してください。