题解 P3488 [POI2009]LYZ-Ice Skates

· · 题解

滑冰俱乐部初始有 1 到 n 号码溜冰鞋各 k 双，已知 x 号脚的人可以穿 x 到 x + d 号码的鞋子。

现在有 m 次操作，每次两个数 r、x，表示 r 号脚的人来了 x 个，x 为负表示离开。对于每次操作，输出溜冰鞋是否足够。

很容易想到将人和溜冰鞋一起建二分图，傻瓜式连边，并对于每次操作都跑一遍最大流，但这时间复杂度显然爆炸！

由于题目只询问是否存在完美匹配，所以考虑使用 Hall 定理。

设 s_x 为当前脚码为 x 的人数。由 Hall 定理可知，若该二分图存在完美匹配，则有：

\forall l,r\in[1,n-d],l\le r,\sum_{i=l}^rs_{i}\le k\times (r-l+1+d)

不妨将右侧常变量分离，则有：

\sum_{i=l}^r(s_i-k)\le k\times d

于是我们动态维护所有区间 \sum s_i-k 的最大值，每次询问时判断是否大于 k\times d 即可。

用线段树可以做到 O(m\log n).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll n,m,k,d;
struct node1{
    ll maxn,sum,qz,hz;
    node1 (ll maxn=0,ll sum=0,ll qz=0,ll hz=0)
        :maxn(maxn),sum(sum),qz(qz),hz(hz){}
}S;
struct node{
    ll sum[N<<2],qz[N<<2],hz[N<<2],maxn[N<<2];
    void pushup(int i){
        sum[i]=sum[i<<1]+sum[i<<1|1];
        qz[i]=max(qz[i<<1],qz[i<<1|1]+sum[i<<1]);
        hz[i]=max(hz[i<<1|1],hz[i<<1]+sum[i<<1|1]);
        maxn[i]=max(maxn[i<<1],max(maxn[i<<1|1],hz[i<<1]+qz[i<<1|1]));
    }
    void build(int i,int l,int r){
        if (l==r){
            sum[i]=qz[i]=hz[i]=maxn[i]=-k;
            return;
        }
        int mid=l+r>>1;
        build(i<<1,l,mid);
        build(i<<1|1,mid+1,r);
        pushup(i);
    }
    void add(int i,int l,int r,int pos,ll s){
        if (l==r){
            sum[i]+=s;
            qz[i]+=s;
            hz[i]+=s;
            maxn[i]+=s;
            return;
        }
        int mid=l+r>>1;
        if (pos<=mid) add(i<<1,l,mid,pos,s);
        else add(i<<1|1,mid+1,r,pos,s);
        pushup(i);
    }
    // node1 query(int i,int l,int r,int ql,int qr){
    //     if (ql<=l&&r<=qr) return node1(maxn[i],sum[i],qz[i],hz[i]);
    //     int mid=l+r>>1;
    //     if (qr<=mid) return query(i<<1,l,mid,ql,qr);
    //     if (mid<ql) return query(i<<1|1,mid+1,r,ql,qr);
    //     node1 x=query(i<<1,l,mid,ql,qr),y=query(i<<1|1,mid,r,ql,qr),z;
    //     z.qz=max(x.qz,x.sum+y.qz);
    //     z.hz=max(y.hz,y.sum+x.hz);
    //     z.sum=x.sum+y.sum;
    //     z.maxn=max(max(x.maxn,y.maxn),x.hz+y.qz);
    //     return z;
    // }
}T;
int read(){
    int w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*f;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
#endif  
    n=read(),m=read(),k=read(),d=read();
    T.build(1,1,n);
    for (int i=1;i<=m;i++){
        int x=read(),g=read();
        T.add(1,1,n,x,g);
        ll num=T.maxn[1];
        //cout<<num<<"\n";
        if (num>k*d) puts("NIE");
        else puts("TAK");
    }
    return 0;
}