原文链接：https://blog.csdn.net/qq_36797743/java/article/details/79400401
题意
初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。 有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。 对于每次操作，输出溜冰鞋是否足够。
考虑Hall定理
如果我们任意选择一个Ｌ，Ｒ
因为题目有条件1≤Ｒi≤n−d
一个区间[Ｌ,Ｒ]他们所连向的点是(Ｒ−Ｌ+1+d)∗ｋ
他们满足
sigma(c[i]) - (R-L+1+d)*K<=0
其中L<=i<=R
c[i]代表选择i尺码的鞋子的人有多少个
上式表示鞋子的数量多于人的数目
由于右式中的(R-L+1)*k是一个区间，左式也是一个这样的区间，所以可以将把式子化简得
sigma(c[i]−k)≤d∗k
其中L<=i<=R
如果我们希望这个式子始终成立，那么如果最大的子段和C[i]
都满足上式，则所有区间就都满足了。
#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;
}
https://blog.csdn.net/WerKeyTom_FTD/article/details/65660346?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-5&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-5
原文：https://www.cnblogs.com/cutemush/p/12740692.html