显然是一个二分图匹配问题，所以我们可以想到用霍尔定理来做。
但是我们不能暴力枚举左边点的所有情况，但是我们其实只需要找到左边所有情况的最小值即可。我们显然可以发现最小值一定是一个连续的区间。因为这样重叠是最多的。
所以我们等价于找一个区间：(r-l+1+d)*k>=sum(l,r)在极端情况都是满足的，所以我们维护区间最大子段和即可。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+10; int n,m,k,d; struct node{int ls,rs,s,sum;}t[N<<2],c; #define mid (l+r>>1) inline node merge(node a,node b){ c.sum=a.sum+b.sum; c.ls=max(a.ls,a.sum+b.ls),c.rs=max(b.rs,b.sum+a.rs); c.s=max(max(a.s,b.s),a.rs+b.ls); return c; } void change(int p,int l,int r,int x,int v){ if(l==r){t[p].ls+=v,t[p].rs+=v,t[p].s+=v,t[p].sum+=v; return ;} if(x<=mid) change(p<<1,l,mid,x,v); else change(p<<1|1,mid+1,r,x,v); t[p]=merge(t[p<<1],t[p<<1|1]); } signed main(){ cin>>n>>m>>k>>d; for(int i=1;i<=n;i++) change(1,1,n,i,-k); for(int i=1,r,x;i<=m;i++){ scanf("%lld %lld",&r,&x); change(1,1,n,r,x); if(t[1].s>d*k) puts("NIE"); else puts("TAK"); } return 0; }