問題一覧 > 通常問題

No.2988 Min-Plus Convolution Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : tatyam
7 ProblemId : 11666 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-12-13 00:25:27

問題文

長さ NN の整数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) と B=(B1,B2,…,BN)B = (B_1, B_2, \dots, B_N) が与えられます。 ここで、BB は下に凸です。すなわち、2≤i≤N−12 \le i \le N - 1 を満たす各 ii について、Bi≤Bi−1+Bi+12B_i \le \dfrac{B_{i-1} + B_{i+1}}2 が成り立ちます。

QQ 個のクエリが与えられるので、順に処理してください。

各クエリでは、整数 p,x,kp, x, k が与えられるので、ApA_p に xx を代入したのち、min⁡i+j=k(Ai+Bj)\displaystyle\min_{i+j=k} (A_i + B_j) を出力してください。

入力

NN QQ
A1A_1 A2A_2 …\ldots ANA_N
B1B_1 B2B_2 …\ldots BNB_N
query1\text{query}_1
query2\text{query}_2
⋮\vdots
queryQ\text{query}_Q

ここで、queryi\text{query}_i (1≤i≤Q1 \le i \le Q) は ii 番目のクエリを表す。各クエリは以下の形式で与えられる。 

pp xx kk

  • 1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5
  • ∣Ai∣≤109|A_i| \le 10^9 (1≤i≤N1 \le i \le N)
  • ∣Bi∣≤109|B_i| \le 10^9 (1≤i≤N1 \le i \le N)
  • Bi≤Bi−1+Bi+12B_i \le \dfrac{B_{i-1} + B_{i+1}}2 (2≤i≤N−12 \le i \le N - 1)
  • 各クエリについて:
    • 1≤p≤N1 \le p \le N
    • ∣x∣≤109|x| \le 10^9
    • 2≤k≤2N2 \le k \le 2N
  • 入力される値はすべて整数である

出力

QQ 行出力せよ。ii 行目 (1≤i≤Q1 \le i \le Q) には、ii 番目のクエリの答えを出力せよ。

サンプル

サンプル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)A = (5, 7, 5, 1), B = (8, 2, 2, 6) です。

  • 11 番目のクエリでは、A4A_4 に 88 を代入し、A=(5,7,5,8)A = (5, 7, 5, 8) とします。このとき、min⁡i+j=4(Ai+Bj)=min⁡(A1+B3,A2+B2,A3+B1)=min⁡(7,9,13)=7\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 です。
  • 22 番目のクエリでは、A1A_1 に 55 を代入し、A=(5,7,5,8)A = (5, 7, 5, 8) とします。このとき、min⁡i+j=2(Ai+Bj)=min⁡(A1+B1)=min⁡(13)=13\displaystyle\min_{i+j=2}(A_i + B_j) = \min(A_1 + B_1) = \min(13) = 13 です。
  • 33 番目のクエリでは、A4A_4 に 55 を代入し、A=(5,7,5,5)A = (5, 7, 5, 5) とします。このとき、min⁡i+j=5(Ai+Bj)=min⁡(A1+B4,A2+B3,A3+B2,A4+B1)=min⁡(11,9,7,13)=7\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 です。
  • 44 番目のクエリでは、A1A_1 に 44 を代入し、A=(4,7,5,5)A = (4, 7, 5, 5) とします。このとき、min⁡i+j=7(Ai+Bj)=min⁡(A3+B4,A4+B3)=min⁡(11,7)=7\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もしくは右上の雲マークをクリックしてアカウントを作成してください。