#P1135. [POI2009]Lyz

[POI2009]Lyz

题目描述

初始时滑冰俱乐部有 11 到 nn 号的溜冰鞋各 kk 双。已知 xx 号脚的人可以穿 xx 到 x+dx+d 的溜冰鞋。 有 mm 次操作,每次包含两个数 ri,xir_i,x_i 代表来了 xix_i 个 rir_i 号脚的人。xix_i 为负,则代表走了这么多人。 对于每次操作,输出溜冰鞋是否足够。

输入格式

第一行四个整数 n,m,k,dn,m,k,d。

接下来 mm 行,每行两个数 ri,xir_i,x_i。

输出格式

对于每个操作,输出一行,TAK 表示够,NIE 表示不够。

4 4 2 1
1 3
2 3
3 3
2 -1
TAK
TAK
NIE
TAK

数据规模与约定

$1 \le n \le 2 \times 10^5 , 1 \le m \le 5 \times 10^5 , 1 \le k \le 10^9, 0 \le d \le n$

1≤i≤m,1≤ri≤n−d,∣xi∣≤1091 \le i \le m, 1 \le r_i \le n-d , |x_i| \le 10^9

提示

考虑我们什么时候是无解?

设 [l,r][l,r] 为脚号码的范围,sumisum_i 表示型号为 ii 的人数,则当且仅当 sum(l,r)−k×(r−l+1+d)>0sum(l,r)-k\times (r-l+1+d)>0,就是人比鞋子多的意思;

移项,可得∑lrsumi−k>k×d\sum_l^r sum_i-k > k\times d,我们只要用线段树维护区间最大子段和,然后和 k×dk\times d 比较即可