POI #Year2009 #线段树 #Hall定理
考虑实际上是一个二分图匹配问题,那么这个二分图存在匹配当且仅对于 \(L\) 的任何子集右侧的度数和 \(\geq\) 左侧的
然后线段树维护左侧的区间最大和
// Author: xiaruize
const int N = 2e5 + 10;
int n, m, k, d;
struct segment_tree
{
#define ls p << 1
#define rs p << 1 | 1
struct node
{
int mx, lmx, rmx, sum;
} tr[N << 2];
void pushup(int p)
{
tr[p].lmx = max(tr[ls].lmx, tr[ls].sum + tr[rs].lmx);
tr[p].rmx = max(tr[rs].rmx, tr[rs].sum + tr[ls].rmx);
tr[p].mx = max({tr[ls].mx, tr[rs].mx, tr[ls].rmx + tr[rs].lmx});
tr[p].sum = tr[ls].sum + tr[rs].sum;
}
void build(int p, int l, int r)
{
if (l == r)
{
tr[p] = {-k, -k, -k, -k};
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void update(int p, int l, int r, int x, int val)
{
if (l == r)
{
tr[p].sum += val;
tr[p].mx += val;
tr[p].lmx += val;
tr[p].rmx += val;
return;
}
int mid = l + r >> 1;
if (x <= mid)
update(ls, l, mid, x, val);
else
update(rs, mid + 1, r, x, val);
pushup(p);
}
} seg;
void solve()
{
cin >> n >> m >> k >> d;
seg.build(1, 1, n);
rep(i, 1, m)
{
int r, x;
cin >> r >> x;
seg.update(1, 1, n, r, x);
debug(seg.tr[1].mx);
if (seg.tr[1].mx <= k * d)
cout << "TAK" << endl;
else
cout << "NIE" << endl;
}
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:val,int,tr,mid,Ice,seg,POI2009LYZ,build,Skates
From: https://www.cnblogs.com/xiaruize/p/18142217