[文章目录]
Description
初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。 有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。 对于每次操作，输出溜冰鞋是否足够。n<=200000 m<=500000 r<=n-d xi<=10^9 注意，如果来了一拨人不够，这波人是一直等着的。
考虑对于一些人我们的策略：从小号脚的枚举，显然每个号都优先用小号的鞋。那么不合法状态一定是存在一段脚号区间使得该区间人数和>len*k+d*k。 =>sum-len*k>d*k 对于每一个鞋号个数-k，之后这就是最大连续子段和问题了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 201000
using namespace std;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char f=1,ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=nc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
x= f ? x:-x;
}
int n,M,m,d;
ll k,sum[N<<2],mxl[N<<2],mx[N<<2],mxr[N<<2];
inline ll Min(ll x,ll y){return x<y?x:y;}
inline ll Max(ll x,ll y){return x>y?x:y;}
void pushup(int pos)
{
mx[pos]=Max(mx[pos<<1],Max(mx[pos<<1|1],mxr[pos<<1]+mxl[pos<<1|1]));
mxl[pos]=Max(mxl[pos<<1],sum[pos<<1]+mxl[pos<<1|1]);
mxr[pos]=Max(mxr[pos<<1|1],sum[pos<<1|1]+mxr[pos<<1]);
sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}
void build(int pos,int l,int r)
{
if(l==r)
{
sum[pos]=mxl[pos]=mxr[pos]=mx[pos]=-k;
return ;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix(int pos,int l,int r,int x,int y)
{
if(l==r)
{
mx[pos]+=y; mxl[pos]+=y; mxr[pos]+=y;
sum[pos]+=y; return ;
}
int mid=(l+r)>>1;
if(x<=mid) fix(pos<<1,l,mid,x,y);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
int main()
{
scanf("%d%d%lld%d",&n,&m,&k,&d);
M=n-d; build(1,1,M);
int x,y; ll lim=k*d;
while(m--)
{
read(x); read(y); fix(1,1,M,x,y);
if(mx[1]>lim) puts("NIE");
else puts("TAK");
}
return 0;
}