自动搬运

查看原文

来自洛谷，原作者为

	大菜鸡fks **

搬运于2025-08-24 21:49:29，当前版本为作者最后更新于2018-06-01 14:32:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题好妙啊。

首先不看数据范围是二分图匹配的裸题。但显然会爆炸。

从暴力的做法入手，进行思考。这里引用一个Hall定理：对于一个二分图，设左边有个n点，右边有个m点，则左边个点能完全匹配的充要条件是：对于1<=i<=n,左面任意i个点，都至少有i个右面的点与它相连。

要满足如上条件，从最劣情况入手，显然选择连续型号的人会使右边与他相连的人最少。设a[i]为选择i这个型号的人的数量,sum[l,r]为a[l..r]的总和。

那么对于任意的sum[l,r]<=(r-l+1+d)*k

可以换一下形式。

设s[l,r]为l<=i<=r, a[i]-k的和。

那么对于任意的l,r，s[l,r]<=d*k

于是这题就变成动态维护最大子段和了，线段树即可。

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
const int N=2e5+5;
struct node{
	int lmx,rmx,sum,ans;
}a[N<<2];
int n,m,K,d;
inline void pushup(int k){
	a[k].sum=a[k<<1].sum+a[k<<1|1].sum;
	a[k].lmx=max(a[k<<1].lmx,a[k<<1].sum+a[k<<1|1].lmx);
	a[k].rmx=max(a[k<<1|1].rmx,a[k<<1|1].sum+a[k<<1].rmx);
	a[k].ans=max(a[k<<1].ans,max(a[k<<1|1].ans,a[k<<1].rmx+a[k<<1|1].lmx));
}
void build(int k,int l,int r){
	if (l==r){
		a[k]=(node){0,0,-K,-K};
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid); build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k,int l,int r,int x,int y){
	if (l==r){
		a[k].ans+=y; a[k].sum+=y;
		a[k].lmx=a[k].rmx=max(a[k].sum,0ll);
		return;
	}
	int mid=(l+r)>>1;
	if (mid>=x) update(k<<1,l,mid,x,y);
	   else update(k<<1|1,mid+1,r,x,y);
	pushup(k);
}
inline void init(){
	n=read(); m=read(); K=read(); d=read();
	build(1,1,n);
}
inline void solve(){
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		update(1,1,n,x,y);
		if (a[1].ans<=K*d) puts("TAK"); else puts("NIE");
	}
}
signed main(){
	init();
	solve();
	return 0;
}