【codecomb2096】lyz

2014年10月16日1,2160

Description

滑冰俱乐部初始有1->n号码溜冰鞋各k双,已知x号脚的人可以穿x->x+d号码的鞋子。现在有m次操作,每次两个数r、x,表示r号脚的人来了x个,x为负表示离开。对于每次操作,输出溜冰鞋是否足够。

Input

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

以下m行,每行一个操作。

Output

对于每一个询问,输出是否可行。若可行,输出TAK,反之,输出NIE。

Sample Input

4 4 2 1

1 3

2 3

3 3

2 -1

Sample Output

TAK

TAK

NIE

TAK

Hint

数据范围:

n<=200000,m<=500000,1<=k<=10^9,0<=d<=n,ri<=n-d

题解

如果某一段的需求和为sum,长度为len

而(len+d)* k >= sum 即为合法

把这式子倒腾一下

d * k >= sum – len * k

那么把线段树初值赋为 -k

就变为 d * k >= sum

问题转换为找一个最大子串和看它是否小等于d*k,线段树维护