「JLOI2015」城池攻占

发表于

题目描述

小铭铭最近获得了一副新的桌游，游戏中需要用 $m$ 个骑士攻占 $n$ 个城池。

这 $n$ 个城池用 $1$ 到 $n$ 的整数表示。除 $1$ 号城池外，城池 $i$ 会受到另一座城池 $f_i$ 的管辖，其中 $f_i <i$。也就是说，所有城池构成了一棵有根树。这 $m$ 个骑士用 $1$ 到 $m$ 的整数表示，其中第 $i$ 个骑士的初始战斗力为 $s_i$，第一个攻击的城池为 $c_i$。

每个城池有一个防御值 $h_i$，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 $1$ 号城池，或牺牲为止。

除 $1$ 号城池外，每个城池 $i$ 会给出两个战斗力变化参数 $a_i, v_i$。若 $a_i = 0$，攻占城池 $i$ 以后骑士战斗力会增加 $v_i$；若 $a_i =1$，攻占城池 $i$ 以后，战斗力会乘以 $v_i$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

算法讨论

好像不是很优秀的倍增算法。。

对于每个点，存一下往上走$2^i$步所需要最小的战斗力，再记一下途中的buff就好了

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
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 300005;
typedef long long ll;
const ll Inf = 6e18;

char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline ll _R() {
	ll d = 0; bool ty = 1; char t;
	while (t = GC, (t < '0' || t > '9') && t != '-') ;
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}

int n, m, ans1[N], ans2[N];

struct tr_matrix {
	ll ml, ad;
} tr[N][20];
tr_matrix operator * (const tr_matrix& lhs, const tr_matrix& rhs) {
	return (tr_matrix) {lhs.ml * rhs.ml, lhs.ad * rhs.ml + rhs.ad};
}
ll operator * (const tr_matrix& lhs, ll x) {
	return x * lhs.ml + lhs.ad;
}
ll operator * (ll x, const tr_matrix& rhs) {
	return x * rhs.ml + rhs.ad;
}

ll rc[N][20];

int Fa[N][20], Dep[N];
int Tote, Last[N], Next[N << 1], End[N << 1];
#define ADDE(ST, END) (End[++ Tote] = END, Next[Tote] = Last[ST], Last[ST] = Tote)

void dfs(int x, int fa) {
	for (int i = 1; i <= 19; i ++) rc[x][i] = Inf;
	Dep[x] = Dep[fa] + 1;
	Fa[x][0] = fa;
	for (int i = 1, v = Fa[x][i - 1]; i < 20 && (1 << i) <= Dep[x]; v = Fa[x][i], i ++) {
		Fa[x][i] = Fa[v][i - 1];
		tr[x][i] = tr[x][i - 1] * tr[v][i - 1];

		if (tr[x][i - 1].ml < 0) continue;
		rc[x][i] = max(rc[x][i - 1], (rc[v][i - 1] - tr[x][i - 1].ad - 1) / tr[x][i - 1].ml + 1);
	}

	for (int u, i = Last[x]; i; i = Next[i])
		if (u = End[i], u != fa) dfs(u, x);
}
int main() {
	freopen("fall.in", "r", stdin);
	freopen("fall.out", "w", stdout);
	int i, j, k, x, y;
	ll d;
	n = _R(), m = _R();
	for (i = 1; i <= n; i ++) rc[i][0] = _R();
	for (i = 2; i <= n; i ++) {
		x = _R(), k = _R();
		if (k == 0) tr[i][0].ad = _R(), tr[i][0].ml = 1;
		else tr[i][0].ml = _R();
		ADDE(x, i);
		ADDE(i, x);
	}
	dfs(1, 0);
	for (i = 1; i <= m; i ++) {
		d = _R(), x = _R();
		for (j = 19; j >= 0 && x; j --)
			if (rc[x][j] <= d) d = d * tr[x][j], x = Fa[x][j], ans2[i] += 1 << j;
		if (x == 1 && d >= rc[1][0]) ans2[i] ++, x = 0;
		ans1[x] ++;
	}
	for (i = 1; i <= n; i ++) printf("%d\n", ans1[i]);
	for (i = 1; i <= m; i ++) printf("%d\n", ans2[i]);
}