[BZOJ4378][POI2015]Logistyka（树状数组）

Address

洛谷P3586

BZOJ4378

Solution

显然我们的重点在询问。（废话）

先说结论：

设数集中 ≥ s \ge s ≥s 的数有 c n t cnt cnt 个。

每次选 c c c 个正数减一这种操作能进行 s s s 次，当且仅当

（1） c n t ≥ c cnt\ge c cnt≥c ，

或者（2）数集中 &lt; s &lt;s <s 的数之和 ≥ ( c − c n t ) × s \ge(c-cnt)\times s ≥(c−cnt)×s 。

证明：

（1）当 c n t ≥ c cnt\ge c cnt≥c 时显然。只需要每次操作都对这 c n t cnt cnt 个数执行即可。

（2）

必要性：相当于在 &lt; s &lt;s <s 的数中每次选 c − c n t c-cnt c−cnt 个数减一，进行 s s s 次操作。如果 &lt; s &lt;s <s 的数之和小于 ( c − c n t ) × s (c-cnt)\times s (c−cnt)×s ，则显然是不行的。

充分性：可以使用数学归纳法证明：一个数集，里面的数和为 ( c − c n t ) × s (c-cnt)\times s (c−cnt)×s ，每次选 c − c n t c-cnt c−cnt 个数减一，可以使所有数变成 0 0 0 的充分必要条件是数集里每个数都不超过 s s s 。使用这个结论就能推出数集中 &lt; s &lt;s <s 的数之和 ≥ ( c − c n t ) × s \ge(c-cnt)\times s ≥(c−cnt)×s 时一定能做到。

于是我们可以将操作数离散化，使用树状数组维护每个数值的出现次数和出现的数之和。

这样我们就能方便地在支持修改的情况下求 c n t cnt cnt 以及数集中 &lt; s &lt;s <s 的数之和了。

时间复杂度 O ( m log ⁡ n ) O(m\log n) O(mlogn) 。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Bitr(x, n) for (; x <= n; x += x & -x)
#define Bitl(x) for (; x; x -= x & -x)

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

inline char get()
{
	char c;
	while ((c = getchar()) != 'U' && c != 'Z');
	return c;
}

typedef long long ll;

const int N = 1e6 + 5;

int n, m, a[N], X[N], Y[N], tm, ttm, b[N], A[N];
char op[N];
ll sum, Asum[N];

void change(int x, int v)
{
	Bitr(x, ttm) A[x] += v;
}

void changes(int x, int v)
{
	Bitr(x, ttm) Asum[x] += v;
}

int ask(int x)
{
	int res = 0;
	Bitl(x) res += A[x];
	return res;
}

ll asks(int x)
{
	ll res = 0;
	Bitl(x) res += Asum[x];
	return res;
}

int main()
{
	int i;
	n = read(); m = read();
	b[tm = 1] = 0;
	For (i, 1, m)
	{
		op[i] = get();
		X[i] = read(); Y[i] = read();
		b[++tm] = Y[i];
	}
	std::sort(b + 1, b + tm + 1);
	ttm = std::unique(b + 1, b + tm + 1) - b - 1;
	For (i, 1, m) Y[i] = std::lower_bound(b + 1, b + ttm + 1, Y[i]) - b;
	For (i, 1, n) change(a[i] = 1, 1);
	For (i, 1, m)
		if (op[i] == 'U')
		{
			sum += b[Y[i]] - b[a[X[i]]];
			change(a[X[i]], -1); change(Y[i], 1);
			changes(a[X[i]], -b[a[X[i]]]);
			changes(Y[i], b[Y[i]]);
			a[X[i]] = Y[i];
		}
		else
		{
			int xcnt = n - ask(Y[i] - 1);
			ll xsum = asks(Y[i] - 1);
			puts(xcnt >= X[i] || xsum >= 1ll * (X[i] - xcnt) * b[Y[i]]
				? "TAK" : "NIE");
		}
	return 0;
}