mydcwfy's Blog

UOJ710 【北大集训2021】魔塔 OL

Posted on
Symbols count in article: 3.5k Reading time ≈ 8 mins.

按序给出 $m$ 次操作或询问：

  1. 新增元素 $(x, y, z)$，新给一个编号，获得他需要消耗 $a$ 点血量，获得他后可以获得 $b$ 点血量。
  2. 编号为 $k$ 的元素被删除了。保证不会重复利用或重复删除编号。
  3. 给定三元组 $(x, y, z)$，问要获得所有严格小于等于 $(x, y, z)$ 的元素需要开始时有多少血量才不会出现血量 $< 0$ 的情况。

元素和询问次数都不超过 $50000$，$x, y, z\leq 10000$，$a, b\leq 10 ^ 9$，2s。

首先我们需要考虑的问题是如果已经给出了所有严格小于等于的元素，如何排布使得开始的血量最少。

直接对这些元素排序，考虑微调来判断谁在前面，因为微调不会影响其他元素。假设当前 $(a_1, b_1)$ 和 $(a_2, b_2)$ 需要比较，那么假设 $a_1$ 在前，最少血量就是 $\max(a_1, a_1 + a_2 - b_1)$，$a_2$ 在前也是一样。比较这两个就可以了。

注意到这个判断先后顺序的是满足 std::sort 的要求（严格弱序）。我们可以观察到如果 $a_1 < b_1$ 和 $a_2 < b_2$ 不相同的话，是可以严格排序的（显然 $a < b$ 的在前面）。而如果都是 $a < b$ 的话，那么就是比较 $a_1$ 和 $a_2$。如果都是 $a \geq b$ 的话，就是比 $a_1 + a_2 - b_1$ 和 $a_1 + a_2 - b_2$ 也就是 $b_1$ 和 $b_2$。容易发现都是严格弱序的。

这样我们就解决了第一个问题，如何找到最小的方案。那么现在我们将所有元素按照该排序方式排序，离线询问，现在需要解决的问题就是如何找到所有满足严格小于等于的存在的元素。注意到存在其实也是时间轴上的偏序，于是就是解决偏序问题。

高维偏序问题，显然的 std::bitset 解法，复杂度 $O(\dfrac {n ^ 2}w)$ 也很对，但是注意到我们还是需要把每个元素取出来然后选择他，这样复杂度可能退化。考虑分块，我们每 $B$ 个一块，然后对一块所有可能的选择情况都预处理出来。然后再对于所有询问，这样就可以直接使用了。

假设 $n, m$ 同阶，复杂度显然是 $O(\dfrac {n2 ^ B}B + \dfrac{n ^ 2}B)$，取 $B = O(\log n)$ 即可得到复杂度为 $O(\dfrac{n ^ 2}{\log n})$。复杂度虽然比较奇怪，但事实是这算法能过。

所有偏序需要一个一个加入统计答案的可以使用分块做到 $O(\dfrac{n ^ 2}{\log n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define high(x) (31 - __builtin_clz(x))

struct Node {
	LL nd, sum;
	Node operator +(Node t) const {
		LL ret = std::max(nd, nd - sum + t.nd);
		return {ret, ret + t.sum + sum - nd - t.nd};
	}
};
struct Monster {
	int st, ed, x, y, z;
	Node add;
	bool operator <(Monster t) const {
		return std::min(-add.nd, -add.nd + add.sum - t.add.nd)
			> std::min(-t.add.nd, -t.add.nd + t.add.sum - add.nd);
	}
} mon[N];
struct Query {
	int x, y, z, at;
	Node res;
} q[N];
int m, n, Q, havx[S], havy[S], havz[S];
Node ans[1 << B | 10];

void solve(int l, int r)
{
	int len = r - l + 1;
	for (int i = 1; i < (1 << len); ++ i)
		ans[i] = ans[i ^ (1 << high(i))] + mon[high(i) + l].add;
	for (int i = 0; i < S; ++ i) havx[i] = havy[i] = havz[i] = 0;
	for (int i = l, id; i <= r; ++ i)
	{
		havx[mon[i].x] |= 1 << (id = i - l);
		havy[mon[i].y] |= 1 << id, havz[mon[i].z] |= 1 << id;
	}
	for (int i = 1; i < S; ++ i)
		havx[i] |= havx[i - 1], havy[i] |= havy[i - 1], havz[i] |= havz[i - 1];
	std::vector<int> id1(r - l + 1);
	for (int i = l; i <= r; ++ i) id1[i - l] = i;
	std::vector<int> id2(id1);
	std::sort(id1.begin(), id1.end(), [&](int x, int y) { return mon[x].st < mon[y].st; });
	std::sort(id2.begin(), id2.end(), [&](int x, int y) { return mon[x].ed < mon[y].ed; });
	auto iter1 = id1.begin(), iter2 = id2.begin();
	for (int i = 1, hav = 0; i <= Q; ++ i)
	{
		while (iter1 != id1.end() && mon[*iter1].st <= q[i].at) hav ^= 1 << (*(iter1 ++) - l);
		while (iter2 != id2.end() && mon[*iter2].ed <= q[i].at) hav ^= 1 << (*(iter2 ++) - l);
		// std::cout << i << ' ' << (hav & havx[q[i].x] & havy[q[i].y] & havz[q[i].z]) << ' ' << hav << '\n';
		q[i].res = q[i].res + ans[hav & havx[q[i].x] & havy[q[i].y] & havz[q[i].z]];
	}
}

int main()
{
	std::cin >> m;
	char op[3];
	for (int i = 1, id, t = 0; i <= m; ++ i)
	{
		scanf("%s", op);
		if (*op == '+')
			++ n, scanf("%d %d %d %lld %lld", &mon[n].x, &mon[n].y, &mon[n].z, &mon[n].add.nd, &mon[n].add.sum), mon[n].st = ++ t;
		else if (*op == '-') scanf("%d", &id), mon[id].ed = ++ t;
		else if (*op == '?') ++ Q, scanf("%d %d %d", &q[Q].x, &q[Q].y, &q[Q].z), q[Q].at = t;
		else assert(false);
	}
	for (int i = 1; i <= n; ++ i) ;
	for (int i = 1; i <= n; ++ i)
		if (!mon[i].ed) mon[i].ed = m + 1;
	std::sort(mon + 1, mon + n + 1);
	for (int l = 1, r; l <= n; l = r + 1) solve(l, r = std::min(n, l + B - 1));
	for (int i = 1; i <= Q; ++ i) printf("%lld\n", q[i].res.nd);
	return 0;
}