[武汉加油] bzoj 1135: [POI2009]Lyz

忽略数据范围，我们就可以用二分图搞一搞，但事实证明我们并不能忽略(滑稽)

Hall定理：对于一个二分图，设左边有个n点，右边有个m点，则左边个点能完全匹配的充要条件是：对于1<=i<=n,左面任意i个点，都至少有i个右面的点与它相连。

换成人话就是这样的：设\(a_i\)为\(i\)号脚的人数，如果对于任意的\(l,r\),都有\(\displaystyle \sum_{i=l}^{r}a_i \le (r+d-l+1) \times k\),那么鞋就是够的。

上面的式子等价于\(\displaystyle \sum_{i=l}^{r}(a_i - k) \le d \times k\)。

由于\(d \times k\)是定值，我们只需要找出来最大的\(\displaystyle \sum_{i=l}^{r}(a_i - k)\)即可。

这就转化成了最大子段和的问题了，我们可以用线段树来维护。

#include<iostream>
#include<cstdio>
#define LL long long
#define lson (k<<1)
#define rson ((k<<1)|1)
using namespace std;
const int N=200010;
int n,m,x,y;
LL K,d;
LL tr[N<<2],maxx[N<<2],maxl[N<<2],maxr[N<<2];
void upd(int k)
{
    tr[k]=tr[lson]+tr[rson];
    maxx[k]=max(maxr[lson]+maxl[rson],max(maxx[lson],maxx[rson]));
    maxl[k]=max(maxl[lson],tr[lson]+maxl[rson]);
    maxr[k]=max(maxr[rson],tr[rson]+maxr[lson]);
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        tr[k]=maxx[k]=maxl[k]=maxr[k]=-K;
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    upd(k);
}
void change(int k,int l,int r,int pos,LL val)
{
    if(l==r)
    {
        tr[k]+=val;maxx[k]+=val;maxl[k]+=val;maxr[k]+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)change(lson,l,mid,pos,val);
    else change(rson,mid+1,r,pos,val);
    upd(k);
}
int main()
{
    cin>>n>>m>>K>>d;
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        change(1,1,n,x,y);
        puts(maxx[1]<=K*d?"TAK":"NIE");
    }
    return 0;
}

原文：https://www.cnblogs.com/wljss/p/12315644.html