诸多甜点问题(Many Sweets Problem)

题目描述

给定长度为 N 的正整数列 A=(A₁,A₂,…,A_N)。处理以下查询 Q 次：

• c x l r k：先将 A_c 改为 x，随后求解以下子问题并输出答案。

有 r−l+1 个甜点，第 i 个甜点的美味度为 A_{l+i−1}。

你决定一直吃甜点直到所吃甜点美味度总和达到 k 以上。

若最优选择吃的甜点，最少需要吃几个？输出该数。

若无论如何选择所吃甜点，美味度总和都无法达到 k 以上，则输出 −1。

输入格式

N Q
A1 A2 … AN
query1
query2
⋮
queryQ

每个查询格式为 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 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹
• 1 ≤ c ≤ N
• 1 ≤ x ≤ 10⁹
• 1 ≤ l ≤ r ≤ N
• 1 ≤ k ≤ 10¹⁵
• 输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布