QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 8951. 澡堂

Statistics

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

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

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

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

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

输入格式

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

接下来的一行有 $n$ 个正整数,第 $i$ 个正整数 $t_i$ 表示第 $i$ 个人前去洗澡的时间,保证 $\forall i\in [1,n),t_i\le t_{i+1}$。

接下来的 $q$ 行,每行两个整数 $x_j,t'_j$,表示第 $x_j$ 个人的洗澡时间在这一天(且仅在这一天)变成了 $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\le m\le 5,1\le n\le 10^6,1\le q\le 10^5,1\le t_i,T\le 10^8$。

测试包编号 $n\le$ $m\le$ $q\le$ 特殊性质 分值 子任务依赖
1 $10^3$ $5$ $10^3$ 10
2 $10^6$ $1$ $10^5$ 20
3 $10^6$ $2$ $10^5$ 10 2
4 $2\times 10^5$ $5$ $5\times 10^4$ 20 1
5 $10^6$ $5$ $10^5$ $t_i$ 在 $[1,10^8]$ 中随机 20
6 $10^6$ $5$ $10^5$ 20 3, 4, 5

时空限制:512 MB,3s