rockdu
题意翻译
滑冰俱乐部初始有 1..n 号码溜冰鞋各 k 双,已知 x 号脚的人可以穿 x..x + d 号码的鞋子。现
在有 m 次操作,每次两个数 r、x,表示 r 号脚的人来了 x 个,x 为负表示离开。对于每次操作,
输出溜冰鞋是否足够。
数据范围: n,k,m\leq5*10^5, k\leq10^9n,k,m≤5∗105,k≤109
题目背景
题目描述
Byteasar runs a skate club. Its members meet on a regular basis and train together, and they always use the club's ice-skates. The skate sizes are (by convention) numbered from to
. Naturally, each club member has some foot size, but that is not all to it! Skaters have skate size tolerance factor
: a skater with foot size
can wear skates with sizes from
up to
. It should be noted, though, that no skater ever wears two skates of different size simultaneously.
To supply the club, Byteasar bought pairs of ice-skates of each size, i.e. from
to
. As time passes, some people join the club, just as some established members leave it. Byteasar worries if he will have enough skates of appropriate size for every member at each training.
We assume that initially the club has no members at all. Byteasar will give you a sequence of events of the following form:
(new) members with foot size
have joined/left the club. Right after each such event Byteasar wants to know whether he has enough skates of appropriate size for every club member. He asks you to write a programme that will check it for him.
输入输出格式
输入格式：
The first line of the standard input contains four integers ,
,
and
(
,
,
,
), separated by single spaces, that denote, respectively: maximum skate size, number of events, number of skate pairs of each size Byteasar initially bought, and the skate size tolerance factor. The following
lines contain the sequence of
events, one per line. The
-th line (for  should either contain the word TAK (Polish for yes), or the word NIE (Polish for no), depending on whether Byteasar has the skates of appropriate size for every club member right after the
-th event.
输入输出样例
本题是二分图Hall定理的一个巧妙运用。
朴素的算法对于每一次建立一个二分图匹配一下，肯定过不了。
考虑使用Hall定理。对于右边是每一种鞋有k个点，左边是人数。
那么我们把每种鞋的人数放进桶里，发现根据本题性质，我们只需要判断这个权值数组中每一个数减去k组成的新数组中，最大连续字段和是否满足Hall定理即可。所以建立权值线段树，每一次查询最大子段和，判断是否小于该区间内鞋的总数即可。
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 5e5 + 5;
int n, k, m, d, r, x;
namespace SGT {
struct node {
LL lmx, rmx, mx, sum; int ch[2];
}tree[maxn << 1];
int cnt, root;
void push_up(int rt) {
int lc = tree[rt].ch[0], rc = tree[rt].ch[1];
tree[rt].lmx = max(tree[lc].lmx, tree[lc].sum + tree[rc].lmx);
tree[rt].rmx = max(tree[rc].rmx, tree[rc].sum + tree[lc].rmx);
tree[rt].mx = max(tree[lc].mx, max(tree[rc].mx, tree[lc].rmx + tree[rc].lmx));
tree[rt].sum = tree[lc].sum + tree[rc].sum;
}
void build(int l, int r, int & rt) {
if(!rt) rt = ++cnt;
if(l == r) {
tree[rt] = (node) {-k, -k, -k, -k, 0, 0};
return ;
}
int mid = l + r >> 1;
build(l, mid, tree[rt].ch[0]);
build(mid + 1, r, tree[rt].ch[1]);
push_up(rt);
}
void edt(int p, int tl, int tr, int dt, int rt) {
if(tl == tr) {
tree[rt].lmx += dt;
tree[rt].rmx += dt;
tree[rt].mx += dt;
tree[rt].sum += dt;
return ;
}
int mid = tl + tr >> 1;
if(p <= mid) edt(p, tl, mid, dt, tree[rt].ch[0]);
else edt(p, mid + 1, tr, dt, tree[rt].ch[1]);
push_up(rt);
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &k, &d);
SGT::build(1, n, SGT::root);
for(register int i = 1; i <= m; ++i) {
scanf("%d%d", &r, &x);
SGT::edt(r, 1, n, x, SGT::root);
printf("%s\n", SGT::tree[1].mx <= 1ll * d * k ? "TAK" : "NIE");
}
return 0;
}
没有帐号? 立即注册