题意

初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。 有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。 对于每次操作，输出溜冰鞋是否足够。

题解

考虑Hall定理
如果我们任意选择一个l，r
因为题目有条件$1≤ri≤n-d$
一个区间$[l,r]$他们所连向的点是$(r-l+1+d)*d$
他们满足

$$\sum_{i=l}^{r}c[i]-(r-l+1+d)*k≤0$$
那么这个区间就是合法的
把式子化简可得 $$\sum_{i=l}^{r}(c[i]-k)≤d*k$$
这样的话，就相当于问一个最大的区间和
线段树维护就可以了

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=200005;
LL n,m,k,d;
struct qq {LL l,r;LL s1,s2;LL c,c1;//最大值LL L,R; }tr[N*2];LL num;//找最大值
void update (LL now)
{LL s1=tr[now].s1,s2=tr[now].s2;tr[now].c1=tr[s1].c1+tr[s2].c1;tr[now].c=max(tr[s1].c,tr[s2].c);tr[now].c=max(tr[now].c,tr[s1].R+tr[s2].L);tr[now].L=max(tr[s1].L,tr[s1].c1+tr[s2].L);tr[now].R=max(tr[s2].R,tr[s2].c1+tr[s1].R);
}
void bt (LL l,LL r)
{LL a=++num;tr[a].l=l;tr[a].r=r;tr[a].R=tr[a].L=tr[a].c=-k;tr[a].c1=-(r-l+1)*k;if (l==r) return ;LL mid=(l+r)>>1;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);
}
void change (LL now,LL x,LL z)
{if (tr[now].l==tr[now].r){tr[now].c+=z;tr[now].c1+=z;tr[now].L+=z;tr[now].R+=z;return ;}LL s1=tr[now].s1,s2=tr[now].s2;LL mid=(tr[now].l+tr[now].r)>>1;if (x<=mid) change(s1,x,z);else change(s2,x,z);update(now);
}
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&k,&d);bt(1,n);for (LL u=1;u<=m;u++){LL r,x;scanf("%lld%lld",&r,&x);change(1,r,x);LL t=tr[1].c;if (t<=d*k) printf("TAK\n");else printf("NIE\n");}return 0;
}