小 P 喜欢研究生活中各种各样的问题,最近他对洗澡这个问题颇有研究。小 P 所在的宿舍一层楼的澡堂有 m 个洗澡的位置(即可以 m 个人同时洗澡),每天有 n 个人要洗澡,每个人前去洗澡的时间为 ti,每个人洗澡的时间固定为 T。
第 i 个人会在 ti 时刻去洗澡时,如果没有位置,他就只有等到有一个人洗完,他会在有一个人洗完后立刻去洗澡。
假设第 i 个人最终开始洗澡的时间为 si,那么他会产生 si−ti 的不满度。
在接下来的 q 天,在第 j 天的时候,xj 会改变一下计划,洗澡的时间会修改为 t′j。注意第 j 天的修改不会持续到第 j+1 天。
小 P 对不满度的和很有兴趣,所以他想请你对每一天求出所有人不满度的和。
输入格式
第一行四个正整数分别为 n,m,q,T,表示洗澡人数,澡堂个数,询问次数,以及洗澡的固定时间。
接下来的一行有 n 个正整数,第 i 个正整数 ti 表示第 i 个人前去洗澡的时间,保证 ∀i∈[1,n),ti≤ti+1。
接下来的 q 行,每行两个整数 xj,t′j,表示第 xj 个人的洗澡时间在这一天(且仅在这一天)变成了 t′j。
输出格式
共 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
数据范围
对于全部数据,1≤m≤5,1≤n≤106,1≤q≤105,1≤ti,T≤108。
测试包编号 | 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