题解 P3488 【[POI2009]LYZ-Ice Skates】

大菜鸡fks · 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;
}