BZOJ 1135 - [POI2009]Lyz | Sengxian's Blog

BZOJ 1135 - [POI2009]Lyz

#图论 #线段树 #二分图 #Hall定理 #最大子段和

Published on 2016-09-28

描述

初始时滑冰俱乐部有 $1$ 到 $n(n\le 200000)$ 号的溜冰鞋各 $k$ 双。已知 $x$ 号脚的人可以穿 $x$ 到 $x+d$ 的溜冰鞋。有 $m(m\le 500000)$ 次操作，每次包含两个数 $r_i, x_i$ 代表来了 $x_i$ 个 $r_i$ 号脚的人。 $x_i$ 为负，则代表走了这么多人。对于每次操作，输出溜冰鞋是否足够。

分析

如果不考虑范围，这题显然是个二分图完美匹配，将每个人和每个鞋子看作 $X$ 集和 $Y$ 集的点，每个人向能够穿的鞋子连边，溜冰鞋足够当且仅当这个图存在一个匹配能完全覆盖 $X$ 集。

然而数据范围比较大，这样是没法做的，我们使用 Hall's marriage theorem，定理的内容是：

霍尔定理（Hall's marriage theorem）：对于一个二分图 $G:(X + Y, E)$ ，存在一个匹配覆盖 $X$ 的充分必要条件是：对于任意一个 $W\subseteq X$ ，都有 $\vert W\vert \le \vert N_G(W)\vert$ ，其中 $N_G(W)$ 是在 $Y$ 中与 $W$ 联通的点的集合。本定理中的条件称为“相异性条件”。
说人话版本：一个二分图的 $X$ 集存在完美匹配的充要条件是对 $X$ 集中的任意 $k$ 个点在 $Y$ 集中都有至少 $k$ 个点与其相邻。
证明：必要性容易证明，下面证明充分性：
假设不存在一个匹配覆盖 $X$ ，那么考虑其最大匹配 $M$ ，一定存在一个未盖点 $u$ 在 $X$ 集中。考虑从 $u$ 出发的所有交替路，设这些交替路经过 $X$ 集合中的点集 $T$ （包括 $u$ ），经过 $Y$ 集合中的点集 $W$ 。不可能存在一条交替路，使得终点是 $Y$ 集中的未盖点（否则存在一条增广路，可以增广从而扩大匹配）。根据交替路的定义（经过匹配边，非匹配边.....），集合 $T \backslash \{u\}$ 与 $W$ 集合构成完美匹配（因为 $T \backslash \{u\}$ 中的点一定是通过一条匹配边到达 $W$ 中的点），这就可以推出 $\vert T\vert = \vert W\vert + 1$ 。

而又有 $N_G(T) = W$ （ $T$ 出发绝对到不了一个未盖点，否则有增广路），根据霍尔定理 $\vert T\vert \le \vert N_G(T) \vert = \vert W\vert$ ，这与之前 $\vert T\vert + 1 = \vert W\vert$ 矛盾。所以一定存在一个匹配覆盖 $X$ 。

设 $s_x$ 为 $x$ 鞋码的人的集合， $a_x$ 为 $x$ 鞋码的人的数量， $K$ 为每个尺码的鞋子数量。

我们现在就来证明某神奇的结论：

在 $X$ 中任选 $k$ 个我们用任选一段区间代替。

引理一：如果鞋码 $x$ 的所有人满足相异性条件，那么鞋码 $x$ 的人的子集也满足相异性条件。
证明：由于一个鞋码 $x$ 的人和 $a_x$ 个鞋码为 $x$ 的人的相邻点是一样的，设他们与 $A$ 个点相邻，那么有：

\vert s\vert\le a_x\le A, s\subseteq s_x

这就意味着我们可以将鞋码为 $x$ 的人看做一个整体考虑，只要整体满足，那么任意子集都满足。

定理一：如果对于任意 $[l, r]$ ，都有 $s_l \cup s_{l + 1}\cup\cdots\cup s_{r}$ 组成的集合满足相异性条件，那么对于所有人的任意子集也满足相异性条件。
证明：引理一告诉我们可以将一个鞋码的人一起考虑。我们使用反证法，假设有 $b_0<b_1<\cdots<b_k$ ，使得 $s_{b_0} \cup s_{b_1}\cup\cdots\cup s_{b_k}$ 不满足霍尔定理。根据我们的建图，有：

\vert s_{b_0} \cup s_{b_1}\cup\cdots\cup s_{b_k}\vert >\vert N_G(s_{b_0} \cup s_{b_1}\cup\cdots\cup s_{b_k})\vert = K\cdot(b_k + d - b_0 + 1)

而我们考虑区间 $[b_0, b_k]$ ，它满足相异性条件，而且它与刚刚的集合在 $Y$ 中的相邻点是一样多的：

\vert s_{b_0} \cup s_{b_0 + 1}\cup\cdots\cup s_{b_k}\vert \le \vert N_G(s_{b_0} \cup s_{b_0 + 1}\cup\cdots\cup s_{b_k})\vert = K\cdot(b_k + d - b_0 + 1)

而必然有不等式：

\vert s_{b_0} \cup s_{b_1}\cup\cdots\cup s_{b_k}\vert \le \vert s_{b_0} \cup s_{b_0 + 1}\cup\cdots\cup s_{b_k} \vert

这就推出了矛盾。

定理一告诉我们，只需要对于每个区间 $[l, r]$ ，满足

\sum_{k = l}^ra_k\le K \cdot(r + d - l + 1)

转换一下可变为：

\sum_{k = l}^r(a_k - K)\le K \cdot d

这样就变成了求最大子段和的问题了，如果最大子段和不超过 $K\cdot d$ ，那么有解，否则无解。可以使用线段树维护。

复杂度： $O(m\log n)$ 。

代码

//  Created by Sengxian on 2016/09/28.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1135 Hall 定理 + 线段树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int MAX_N = 200000 + 3;
int n, m, k, d;

#define ls (((o) << 1) + 1)
#define rs (((o) << 1) + 2)
#define mid (((l) + (r)) >> 1)
const int MAX_NODE = (1 << 18) * 2;
struct segNode {
    ll sum, maxL, maxR, mx;
    segNode(ll val = 0): sum(val), maxL(max(val, 0LL)), maxR(max(val, 0LL)), mx(max(val, 0LL)) {}
}nodes[MAX_NODE];

inline segNode merge(const segNode &lhs, const segNode &rhs) {
    segNode res;
    res.sum = lhs.sum + rhs.sum;
    res.maxL = max(lhs.maxL, lhs.sum + rhs.maxL);
    res.maxR = max(rhs.maxR, rhs.sum + lhs.maxR);
    res.mx = max(lhs.maxR + rhs.maxL, max(lhs.mx, rhs.mx));
    return res;
}

inline void build(int o, int l, int r) {
    if (r - l == 1) nodes[o] = segNode(-k);
    else {
        build(ls, l, mid), build(rs, mid, r);
        nodes[o] = merge(nodes[ls], nodes[rs]);
    }
}

inline void modify(int o, int l, int r, int p, int v) {
    if (r - l == 1) nodes[o] = segNode(nodes[o].sum + v);
    else {
        if (p < mid) modify(ls, l, mid, p, v);
        else modify(rs, mid, r, p, v);
        nodes[o] = merge(nodes[ls], nodes[rs]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt(), k = ReadInt(), d = ReadInt();
    build(0, 0, n);
    while (m--) {
        static int r, x;
        r = ReadInt() - 1, x = ReadInt();
        modify(0, 0, n, r, x);
        if (nodes[0].mx <= (ll)d * k) puts("TAK");
        else puts("NIE");
    }
    return 0;
}

Codeforces 724D - Dense Subsequence BZOJ 1127 - [POI2008]KUP