#1828. 澡堂
澡堂
澡堂
题目描述
标题: 澡堂 - Problem - QOJ.ac
小 P 喜欢研究生活中各种各样的问题,最近他对洗澡这个问题颇有研究。小 P 所在的宿舍一层楼的澡堂有 m 个洗澡的位置(即可以 m 个人同时洗澡),每天有 n 个人要洗澡,每个人前去洗澡的时间为 ti,每个人洗澡的时间固定为 T。
第 i 个人会在 ti 时刻去洗澡时,如果没有位置,他就只有等到有一个人洗完,他会在有一个人洗完后立刻去洗澡。
假设第 i 个人最终开始洗澡的时间为 si,那么他会产生 si−ti 的不满度。
在接下来的 q 天,在第 j 天的时候,xj 会改变一下计划,洗澡的时间会修改为 tj′。注意第 j 天的修改不会持续到第 j+1 天。
小 P 对不满度的和很有兴趣,所以他想请你对每一天求出所有人不满度的和。
输入格式
第一行四个正整数分别为 n,m,q,T,表示洗澡人数,澡堂个数,询问次数,以及洗澡的固定时间。
接下来的一行有 n 个正整数,第 i 个正整数 ti 表示第 i 个人前去洗澡的时间,保证 ∀i∈[1,n),ti≤ti+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
数据范围
对于全部数据,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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 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
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
137
138
145
147
137
127
145
122
144
136