这一题基础是二分图匹配，并且要知道一个 $Hall$ 定理：对于二分图能完全匹配的充要条件是，设点数少的那边为左边，点数为 $n$，对于 $k in [1,n]$ ，左边任意 $k$ 个点，右边都要有至少有 $k$ 的点与左边这些点相连
证明好像也不难，首先必要性是显然的
然后考虑对于左边 $n$ 个点的集合，如果他满足 $Hall$ 定理并且存在一个点 $X_a$ 没法匹配，那么这个点 $X_a$ 连向的 $Y_{b,c,d..}$ 一定已经都有匹配，设此时是 $X_{b,c,d...}$ 匹配 $Y_{b,c,d...}$ ，
那么由 $Hall$ 定理得到 $X_a,X_{b,c,d...}$ 这些点构成的集合一定还有一条出边连向 $Y_{b,c,d}$ 之外的点（不然 $Y$ 的点数小于 $X$ 的点数），
所以可以这样一直增广下去最终一定能找到一条增广路
然后考虑如何保证题目中一定存在完全匹配，显然我们只要考虑连续的一段型号的人，这样会让右边空闲的位置尽量少
如果不合法那么一定存在连续的一段 $[l,r]$ ，使得 $sum_{i=l}^{r}X_i>(r-l+1+d)*k$ ，其中 $X_i$ 为 $i$ 号脚的人的数量，式子表示人比鞋多
变一下式子即为 $sum_{i=l}^{r}(X_i-k)>d*k$ ，所以我们只要能判断是否有连续的一段 $X-k$ 的和大于 $d*k$
直接用线段树维护一下最大子段和即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; int n,m,K,D; struct Segtree { ll sum[N<<2],mx[N<<2],lmx[N<<2],rmx[N<<2]; inline void pushup(int o) { int lc=o<<1,rc=o<<1|1; mx[o]=max( max(mx[lc],mx[rc]) , max(0ll,rmx[lc]+lmx[rc]) ); lmx[o]=max( max(0ll,lmx[lc]) , sum[lc]+lmx[rc] ); rmx[o]=max( max(0ll,rmx[rc]) , sum[rc]+rmx[lc] ); sum[o]=sum[lc]+sum[rc]; } void build(int o,int l,int r) { if(l==r) { sum[o]=-K; return; } int mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); pushup(o); } void change(int o,int l,int r,int pos,int v) { if(l==r) { sum[o]+=v; lmx[o]=rmx[o]=mx[o]=max(0ll,sum[o]); return; } int mid=l+r>>1; pos<=mid ? change(o<<1,l,mid,pos,v) : change(o<<1|1,mid+1,r,pos,v); pushup(o); } ll query() { return mx[1]; } }T; int main() { n=read(),m=read(),K=read(),D=read(); T.build(1,1,n); int a,b; for(int i=1;i<=m;i++) { a=read(),b=read(); T.change(1,1,n,a,b); if(T.query()>1ll*K*D) printf("NIE "); else printf("TAK "); } return 0; }