洛谷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;
}