G - Many Sweets Problem 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) があります。次のクエリを Q 回処理してください。

  • c x l r k : A_c の値を x に更新する。その後、次の小問題を解いて答えを出力する。

r-l+1 個のお菓子があります。i 個目のお菓子の美味しさは A_{l+i-1} です。
あなたは食べたお菓子の美味しさの総和が k 以上になるまでお菓子を食べることにしました。
上手く食べるお菓子を選んだ時、食べるお菓子の個数を最小で何個にすることができますか？答えを出力してください。
ただし、どのようにお菓子を食べても美味しさの総和が k 以上にならない時は -1 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq c \leq N
  • 1 \leq x \leq 10^9
  • 1 \leq l \leq r \leq N
  • 1 \leq k \leq 10^{15}
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_q は以下の形式で与えられる。

c x l r k

出力

Q 行出力せよ。q 行目には q 番目のクエリの答えを出力せよ。

入力例 1

7 5
8 2 4 1 7 3 6
1 1 4 7 9
5 2 1 3 8
6 4 1 5 9
6 5 3 5 1
7 9 4 6 4

出力例 1

2
-1
4
1
1

1 番目のクエリについて説明します。
まず、A_1 を 1 に更新します。A=(1,2,4,1,7,3,6) になります。そして小問題を解きます。
小問題ではお菓子は 4 個あり、美味しさは順に 1,7,3,6 です。
食べたお菓子の美味しさの総和が k=9 以上になるように食べるお菓子の個数を最小化するには、2 番目のお菓子と 4 番目のお菓子を食べるのが最適です。よって小問題の答えは 2 になります。

入力例 2

15 10
993115119 576136368 21553212 219853538 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085 14767613
6 13801767 1 3 667406485
7 672229269 5 7 855399219
11 2367096 1 10 4016308479
6 5951398 8 8 413598120
6 196639646 5 11 2483790193
14 105322777 6 7 610670157
7 416730828 2 14 1236755516
9 838827476 5 14 4350335977
1 894919681 3 7 1132967029
6 932707551 6 15 1694677398

出力例 2

1
2
6
1
4
1
2
-1
2
2

Score : 625 points

Problem Statement

There is a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N). Process the following query Q times.

  • c x l r k : Update the value of A_c to x. Then, solve the following sub-problem and output the answer.

There are r-l+1 sweets. The deliciousness of the i-th sweet is A_{l+i-1}.
You decide to eat sweets until the total deliciousness of the sweets eaten becomes k or more.
What is the minimum possible number of sweets you eat, if you optimally choose which sweets to eat? Output the answer.
If the total deliciousness cannot become k or more no matter how you choose the sweets to eat, output -1 instead.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq c \leq N
  • 1 \leq x \leq 10^9
  • 1 \leq l \leq r \leq N
  • 1 \leq k \leq 10^{15}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_q is given in the following format:

c x l r k

Output

Output Q lines. The q-th line should contain the answer to the q-th query.

Sample Input 1

7 5
8 2 4 1 7 3 6
1 1 4 7 9
5 2 1 3 8
6 4 1 5 9
6 5 3 5 1
7 9 4 6 4

Sample Output 1

2
-1
4
1
1

We explain the first query.
First, update A_1 to 1. Then, A=(1,2,4,1,7,3,6). Now, solve the sub-problem.
In the sub-problem, there are four sweets, with deliciousness 1,7,3,6 in order.
To minimize the number of sweets eaten so that the total deliciousness becomes k=9 or more, it is optimal to eat the second and fourth sweets. Thus, the answer to the sub-problem is 2.

Sample Input 2

15 10
993115119 576136368 21553212 219853538 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085 14767613
6 13801767 1 3 667406485
7 672229269 5 7 855399219
11 2367096 1 10 4016308479
6 5951398 8 8 413598120
6 196639646 5 11 2483790193
14 105322777 6 7 610670157
7 416730828 2 14 1236755516
9 838827476 5 14 4350335977
1 894919681 3 7 1132967029
6 932707551 6 15 1694677398

Sample Output 2

1
2
6
1
4
1
2
-1
2
2