错解
每次跑二分图匹配，时间复杂度显然爆炸。
时间复杂度：我被杀手皇后摸过了
正解
引入
Hall 定理：设二分图中 \(G=<V_1,V_2,E>,|V_1| \le |V_2|\)，则 G 中 存在 \(V_1\) 到 \(V_2\) 的完美匹配当且仅当 \(\forall S \sub V_1\)，均有 \(|S| \le |N(S)|\)，其中 \(N(S)=\Cup_{V_i \in S}{N(V_i)}\)，是 \(S\) 的邻域。
通俗来说，对于一个二分图，它的左面有 \(n\) 个点，右面有 \(m\) 个点，则左边 \(n\) 个点能完全匹配的充要条件是对于任意在 \([1,n]\) 之间的 \(i\)，左面任意 \(i\) 个点，都至少有 \(i\) 个右面的点与它相连。
证明
充分性：假设一个二分图 \(G\) 不存在完美匹配，且满足 Hall 定理，那么如果有一种最大匹配的方案，既然不存在完美匹配，可以找到至少一个未被匹配的点 \(A\)。
因为这个二分图满足 Hall 定理，所以这个点一定连向了至少一个点 \(B\)（有可能存在多个点）。那么这个点 \(B\) 一定在最大匹配中，左边一定有一个点 \(C\) 和它匹配。
\(C\) 做为一个匹配点可能在右边找到 \(D\)，就这样一直找下去，由于左部点数是小于等于右部点数，于是最终点落在右部点结束，找到一个增广路，矛盾，假设不成立。
必要性：假设一个二分图 \(\text{G}\) 存在完美匹配，且不满足 Hall 定理。
那么对于某 \(k\) 个点，它们连向的都不足 \(k\) 个点，这些点无法匹配，矛盾，假设不成立。
转化
我们显然不能枚举所有情况，这样的时间复杂度是 \(O(2^p)\) 的，其中 \(p\) 为人数，所以我们只能考虑最劣的情况。
显然，选择连续号码的人会使右边与他相邻的人最少。
设 \([l,r]\) 为脚号码的范围，\(a_i\) 表示型号为 \(i\) 的人数，由 Hall 定理得：
\[\sum^r_{i=l}a_i \le k(r-l+1+d) \qquad (1) \]如果单纯这样做的话，修改是 \(O(n^2 \log n)\) 的，询问是 \(O(m^2)\) 的，时间复杂度依然接受不了。
考虑将 \((1)\) 式变形，得：
\[\sum^r_{i=l}(a_i-k)\le d \cdot k \qquad (2) \]\((2)\) 式中由于 \(d \cdot k\) 是个定值，那么问题变为单点修改+求最大连续子序列和，可以用线段树维护（最开始时令 \(a_i=-k\)）。
代码
//P3488 [POI2009]LYZ-Ice Skates
#include <iostream>
#include <cstdio>
using namespace std;
#define int long long
const int MAXN=2e5+5;
struct SegmentTree
{
int lmx,rmx,sum,res;
}tr[MAXN<<2];
int n,m,k,d;
void pushup(int p)
{
tr[p].lmx=max(tr[p<<1].lmx,tr[p<<1].sum+tr[p<<1|1].lmx);
tr[p].rmx=max(tr[p<<1|1].rmx,tr[p<<1|1].sum+tr[p<<1].rmx);
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
tr[p].res=max(tr[p<<1].res,max(tr[p<<1|1].res,tr[p<<1].rmx+tr[p<<1|1].lmx));
return;
}
void build(int p,int l,int r)
{
int mid;
if(l==r)
{
tr[p]={0,0,-k,-k};
return;
}
mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return;
}
void update(int p,int l,int r,int k,int c)
{
int mid;
if(l==r)
{
tr[p].sum+=c;
tr[p].res+=c;
tr[p].lmx=tr[p].rmx=max(0ll,tr[p].sum);
return;
}
mid=(l+r)>>1;
if(k<=mid)
{
update(p<<1,l,mid,k,c);
}
else
{
update(p<<1|1,mid+1,r,k,c);
}
pushup(p);
return;
}
signed main()
{
int x,y;
scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
update(1,1,n,x,y);
if(tr[1].res<=k*d)
{
printf("TAK\n");
}
else
{
printf("NIE\n");
}
}
return 0;
}
/*
* 洛谷
* https://www.luogu.com.cn/problem/P3488
* C++17 -O0
* 2022.10.10
*/