【BZOJ1135】LYZ（POI2009）-线段树+Hall定理

测试地址：LYZ
题目大意：溜冰俱乐部配备有 $1$ ~ $n$ 号的溜冰鞋各 $k$ 双，脚为 $x$ 号的人可以穿 $x$ ~ $x + d$ 号的溜冰鞋，有 $m$ 次操作，每次操作给出两个数 $r_{i}, x_{i}$ ，表示有 $x_{i}$ 个脚为 $r_{i}$ 号的人来到了俱乐部（ $x_{i}$ 可能为负，表示走了 $| x_{i} |$ 个人），问每次操作之后，有没有足够的鞋子分配给当前在俱乐部的所有人。
做法：本题需要用到线段树+Hall定理。
首先，不难想出一个非常暴力的想法：将每个号的溜冰鞋拆成 $k$ 个点，每个人向能穿的鞋子连边，然后做二分图最大匹配来判定有没有完备匹配（就是每个人都匹配了一双鞋子）。然而这个复杂度大到不用写出来都知道肯定会爆炸了，我们需要加速这个判断的过程。
我们想到判定二分图有没有完备匹配的Hall定理（实际上我也是今天学的……），这个定理简单来说如下：
一个二分图被分成两个点集 $X, Y$ ，存在一个匹配使得 $X$ 中的每个点都被匹配的充要条件是，对于任意一个 $X$ 的子集 $S$ ，都直接连接 $Y$ 中的大于等于 $| S |$ 个点。
简单证明一下这个定理，首先必要性显然（要不然你是怎么匹配上的？），至于充分性，采用反证法，如果存在一个二分图满足Hall定理的条件，但是没有完备匹配，那么我们可以找到 $X$ 中的一个未被匹配到的点，因为二分图满足Hall定理的条件，所以这个点一定连接至少一个 $Y$ 中的点，如果这个 $Y$ 中的点没有被匹配到，那么和假设矛盾，反之则可以找到这个点在 $X$ 中的匹配点，现在 $X$ 中我们选定了两个点，根据Hall定理的条件，它们一定连接至少两个 $Y$ 中的点，这个多出来的点可能连接这两个点中的某一个，但是都不重要，如果连接到的点没有被匹配到，那么找到增广路，和假设矛盾，否则又找到这个点在 $X$ 中的匹配点……如此这般，我们最后一定能推翻我们的假设，所以充分性证毕。
那么回到这一题，我们怎么样应用这个定理来判断这样的二分图存不存在完备匹配呢？
我们把人的集合看做 $X$ ，那么对于任意两个人，如果他们能穿的鞋子没有交集，那么他们肯定只需要各自满足各自的要求即可，如果有交集的话，可以证明脚号码在这两个人的脚号码之间的那些人穿的鞋子肯定也是这些鞋子，那么只有当所有这些人组成的集合都满足Hall定理的条件时，整个鞋子的分配才有可能是合法的。
这样我们就把子集的条件变成了连续区间的条件，具体来说，如果穿 $i$ 号鞋的人有 $x_{i}$ 个，那么存在一个鞋子分配方案的充要条件是：
对于任意 $1 \leq l \leq r \leq n - d$ ，有 $\sum_{i = l}^{r} x_{i} \leq (r + d - l + 1) k$ 。
也就是说：
不存在 $1 \leq l \leq r \leq n - d$ ，使得 $\sum_{i = l}^{r} x_{i} > (r + d - l + 1) k$ 。
上面那个不等式等价于：
$\sum_{i = l}^{r} (x_{i} - k) > d k$
那么我们只需对序列 $(x_{i} - k)$ 求出最大子段和，如果最大子段和大于 $d k$ ，就表示不存在合法分配方案，否则就存在一个合法分配方案。而单点修改和求最大子段和是线段树的基本操作，直接上线段树即可，时间复杂度为 $O ((n + m) \log n)$ 。
总的来说，这题的思想非常巧妙，从二分图匹配的暴力，再到想到用Hall定理判定，再到将子集条件转化为区间条件，并用线段树解决，每一步都是非常巧妙的，但又有迹可循，学习了。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll k,d,sum[800010],lftsum[800010],rhtsum[800010],mxsum[800010];

void buildtree(int no,int l,int r)
{
    lftsum[no]=rhtsum[no]=mxsum[no]=0;
    if (l==r) {sum[no]=-k;return;}
    int mid=(l+r)>>1;
    buildtree(no<<1,l,mid);
    buildtree(no<<1|1,mid+1,r);
    sum[no]=sum[no<<1]+sum[no<<1|1];
}

void pushup(int no)
{
    sum[no]=sum[no<<1]+sum[no<<1|1];
    mxsum[no]=max(max(mxsum[no<<1],mxsum[no<<1|1]),rhtsum[no<<1]+lftsum[no<<1|1]);
    lftsum[no]=max(lftsum[no<<1],lftsum[no<<1|1]+sum[no<<1]);
    rhtsum[no]=max(rhtsum[no<<1|1],rhtsum[no<<1]+sum[no<<1|1]);
}

void modify(int no,int l,int r,int pos,ll x)
{
    if (l==r)
    {
        sum[no]+=x;
        lftsum[no]=rhtsum[no]=mxsum[no]=max(sum[no],(ll)0);
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) modify(no<<1,l,mid,pos,x);
    else modify(no<<1|1,mid+1,r,pos,x);
    pushup(no);
}

int main()
{
    scanf("%d%d%lld%lld",&n,&m,&k,&d);

    buildtree(1,1,n-d);
    for(int i=1;i<=m;i++)
    {
        int r;
        ll x;
        scanf("%d%lld",&r,&x);
        modify(1,1,n-d,r,x);
        if (mxsum[1]>d*k) printf("NIE
");
        else printf("TAK
");
    }

    return 0;
}