#P17251. [2025年南开中学集训]圣诞派派翁

[2025年南开中学集训]圣诞派派翁

题目描述

有一个正整数集合 SS。

有 mm 个操作,每个操作表示把 SS 内前 kk 大的数减 11,若集合大小小于 kk 则全局减 11。

当一个数变为 00 时它会消失,即从集合中删除。

设操作完成后 SS 内数的总和为 f(S)f(S)。

一开始 SS 为空集,有 nn 次添加,每次输入 a,ba,b,表示加入 aa 个 bb,求每次加入后的 f(S)f(S),注意每次不会真的进行 mm 次操作。

输入格式

第一行两个正整数 n,mn,m,表示添加的个数和操作的个数。

接下来 mm 行,一行一个正整数 kk。

接下来 nn 行,一行两个正整数 a,ba,b。

输出格式

nn 行,每行一个正整数,表示此时的 f(S)f(S)。

输入输出样例 #1

输入 #1

2 3
1
2
3
2 3
3 1

输出 #1

1
3

输入输出样例 #2

输入 #2

5 4
40
50
40
30
10 7
10 6
10 5
10 4
10 3

输出 #2

30
50
60
70
90

说明/提示

对于所有数据,1lea,b,n,mle2times1061\\le a,b,n,m\\le 2\\times 10^6,0lekle2times1060\\le k\\le 2\\times 10^6。

本题采用捆绑测试 + 子任务依赖,你需要通过一个子任务的所有测试点才能得到该子任务的分数。

子任务编号 nn mm aa 分值
1 le100\\le 100 5
2 le2times103\\le 2\\times 10^3 le105\\le 10^5 15
3 le104\\le 10^4 30
4 le105\\le 10^5 20
5 le106\\le 10^6
6 le2times106\\le 2\\times 10^6 10