这个题首先考虑什么时候是NIE

显然是存在一段\([l,r]\)的人的总数>\(k*(r-l+1+d)\)

此时显然并不好维护，毕竟不等式两边都与长度有关，长度这个因素不能忽略

拆括号之后移下项：\(\sum_{i=l}^{r}v_i-k>k*d\)

现在可以忽略长度了，左边显然就是最大连续子段和，线段树搞就是了

代码：

#include
    
     #include
     
      #include
      
       using namespace std;void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=5e5+10;int n,m,k,d;struct oo{int l,r;long long sum,lmx,rmx,mx;}s[maxn*4];inline void update(int x){    s[x].sum=s[x<<1].sum+s[x<<1|1].sum;    s[x].mx=max(s[x<<1].rmx+s[x<<1|1].lmx,max(s[x<<1].mx,s[x<<1|1].mx));    s[x].lmx=max(s[x<<1].lmx,s[x<<1].sum+s[x<<1|1].lmx);    s[x].rmx=max(s[x<<1|1].rmx,s[x<<1|1].sum+s[x<<1].rmx);}inline void build(int x,int l,int r){    s[x].l=l,s[x].r=r;int mid=(l+r)>>1;    if(l==r){s[x].sum=s[x].lmx=s[x].rmx=s[x].mx=-k;return ;}    build(x<<1,l,mid),build(x<<1|1,mid+1,r);    update(x);}inline void change(int x,int l,int v){    if(s[x].l==s[x].r){s[x].sum=s[x].lmx=s[x].rmx=s[x].mx=s[x].sum+v;return ;}    int mid=(s[x].l+s[x].r)>>1;    if(l<=mid)change(x<<1,l,v);    else change(x<<1|1,l,v);    update(x);}int main(){    read(n),read(m),read(k),read(d);    build(1,1,n);    for(rg int i=1,x,y;i<=m;i++)    {        read(x),read(y),change(1,x,y);        if(s[1].mx>1ll*k*d)printf("NIE\n");        else printf("TAK\n");    }}