洛谷P3488 [POI2009] LYZ-Ice Skates 题解

题目链接：P3488 [POI2009] LYZ-Ice Skates

题意：

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

现在有 $m$ 次操作，每次两个数 $r,x$，表示来了 $x$ 个 $r$ 号脚的人，$x$ 为负则表示离开。

在每次操作之后，你需要判断溜冰鞋是否足够。

输入格式：

第一行 $4$ 个整数 $n,m,k,d$。

接下来 $m$ 行，每行两个整数 $r_i,x_i$，代表一次操作。

输出格式：

$m$ 行，每行一个字符串，若此次操作后满足题意则输出 TAK，否则输出 NIE。

数据范围：

$n\le 2\times 10^5,m\le 5\times 10^5,k\le 10^9,1\le r_i\le n-d,-10^9\le x_i\le 10^9,0\le d<n$

考虑将 $x$ 鞋码的人和 $[x,x+d]$ 的鞋子连边

那么溜冰鞋足够当且仅当这个二分图左部存在一个匹配（即左部的每个点均有匹配）

Hall定理

对于一个二分图 $G\sim (X,Y)$ ，$X$ 存在一个匹配的充分必要条件为：

对于 $X$ 的任意子集 $S$ ，$S$ 的邻居的个数 $|N(S)|$ 满足 $|N(S)| \ge |S|$ 。

换句话说，左侧任选 $i$ 个点，右侧都至少有 $i$ 个点跟它对应。

记鞋码为 $x$ 的人有 $a_x$ 个，若本题存在匹配，则对于任意 $1 \le l \le r \le n-d$ 均有

$\sum_{i=l}^r a_i \le (r - l + 1 + d) \cdot k$

如果记 $S(l,r) = \sum_{i=l}^r\,(a_i-k)$ ，那么

$S(l,r) \le kd$

这相当于单点修改，区间查询最大子段和，考虑线段树即可。

时间复杂度 $\mathcal{O}(q\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, k, d;
struct node { int pre, suf, sum, res; } tr[N * 4];
void push_up(int at)
{
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
    tr[at].pre = max(tr[ls(at)].pre, tr[ls(at)].sum + tr[rs(at)].pre);
    tr[at].suf = max(tr[rs(at)].suf, tr[rs(at)].sum + tr[ls(at)].suf);
    tr[at].res = max({tr[ls(at)].res, tr[rs(at)].res, tr[ls(at)].suf + tr[rs(at)].pre});
}
void build(int at = 1, int l = 1, int r = n)
{
    if(l == r) { return tr[at] = {0, 0, -k, -k}, void(0); }
    int mid = (l + r) >> 1;
    build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void modify(int x, int v, int at = 1, int l = 1, int r = n)
{
    if(l == r)
    {
        tr[at].res += v; tr[at].sum += v;
        tr[at].pre = tr[at].suf = max(tr[at].sum, 0ll); return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(x, v, ls(at), l, mid);
    else { modify(x, v, rs(at), mid + 1, r); }  push_up(at);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q >> k >> d; build();
    rep(i, 1, q)
    {
        static int x, y; cin >> x >> y;
        modify(x, y); cout << (tr[1].res <= k * d ? "TAK" : "NIE") << '\n';
    }
    return 0;
}