QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[0]
Statistics

小 P 喜欢研究生活中各种各样的问题,最近他对洗澡这个问题颇有研究。小 P 所在的宿舍一层楼的澡堂有 m 个洗澡的位置(即可以 m 个人同时洗澡),每天有 n 个人要洗澡,每个人前去洗澡的时间为 ti,每个人洗澡的时间固定为 T

i 个人会在 ti 时刻去洗澡时,如果没有位置,他就只有等到有一个人洗完,他会在有一个人洗完后立刻去洗澡。

假设第 i 个人最终开始洗澡的时间为 si,那么他会产生 siti 的不满度。

在接下来的 q 天,在第 j 天的时候,xj 会改变一下计划,洗澡的时间会修改为 tj。注意第 j 天的修改不会持续到第 j+1 天。

小 P 对不满度的和很有兴趣,所以他想请你对每一天求出所有人不满度的和。

输入格式

第一行四个正整数分别为 n,m,q,T,表示洗澡人数,澡堂个数,询问次数,以及洗澡的固定时间。

接下来的一行有 n 个正整数,第 i 个正整数 ti 表示第 i 个人前去洗澡的时间,保证 i[1,n),titi+1

接下来的 q 行,每行两个整数 xj,tj,表示第 xj 个人的洗澡时间在这一天(且仅在这一天)变成了 tj

输出格式

q 行,第 j 行一个整数表示第 j 天的不满度之和。

样例输入 1

10 3 5 7
1 1 1 2 6 9 12 13 15 17 
8 6
2 14
7 10
9 17
6 16

样例输出 1

24
15
21
18
18

样例输入 2

12 2 10 8
4 4 5 9 10 11 14 14 15 19 23 23 
10 1
9 14
7 6
10 9
1 10
4 1
11 15
3 20
9 8
10 20

样例输出 2

137
138
145
147
137
127
145
122
144
136

数据范围

对于全部数据,1m5,1n106,1q105,1ti,T108

测试包编号 n m q 特殊性质 分值 子任务依赖
1 103 5 103 10
2 106 1 105 20
3 106 2 105 10 2
4 2×105 5 5×104 20 1
5 106 5 105 ti[1,108] 中随机 20
6 106 5 105 20 3, 4, 5

时空限制:512 MB,3s