「JLOI2015」城池攻占

发表于
字数统计: 1,509字 | 阅读时长 ≈ 7min

「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$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

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

输入格式

第一行包含两个正整数 $n, m$，表示城池的数量和骑士的数量。
第二行包含 $n$ 个整数，其中第 $i$ 个数为 $h_i$，表示城池 $i$ 的防御值。
第三到第 $n+1$ 行，每行包含三个整数。其中第 $i +1$ 行的三个数为 $f_i, a_i, v_i$，分别表示管辖这座城池的城池编号和两个战斗力变化参数。
第 $n +2$ 到 $n + m +1$ 行，每行包含两个整数。其中第 $n + i$ 行的两个数为 $s_i,c_i$，分别表示初始战斗力和第一个攻击的城池。

输出格式

输出 $n + m$ 行，每行包含一个非负整数。其中前 $n$ 行分别表示在城池 $1$ 到 $n$ 牺牲的骑士数量，后 $m$ 行分别表示骑士 $1$ 到 $m$ 攻占的城池数量。

数据范围与提示

对于 $100 \%$ 的数据，$1 \leq n,m \leq 300000, \ 1 \leq f_i 0$；保证任何时候骑士战斗力值的绝对值不超过 $10^{18}$。

自然的想法是模拟每一个骑士的行走路径，遇到防御值比战斗力更高的就停下。下面考虑如何优化。

由于$a=1$时乘上的数为正，那么从同一个节点向上走的骑士的战斗力大小关系是不会发生改变的，这就很容易想到了用可并堆处理。对于每一个节点开一个小根堆，在DFS处理i到它时就把儿子节点的堆和自己的合并，在处理弹出堆顶时同时统计答案。之后就是可并堆上带lazy的修改操作。

对于两种操作分别开两个标记$mul$和$add$，使得对儿子节点的修改成为$val=val\times mul+add$的形式。那么对于一次区间整体加，只需要修改$add$。而对于区间整体乘，则需要把$mul$和$add$都乘上$v$：$v(val\times mul+add)=val\times(mul\times v)+add\times v$。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 600005
#define ll long long
using namespace std;

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(){
	char s=GC;bool sign=0;ll v=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=true,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

struct node{
	ll val;int id;
}T[MAXN];
bool operator<(node a,node b){
	return a.val<b.val;
}

int N,M,ansc[MAXN],ansk[MAXN],f[MAXN],a[MAXN];
ll h[MAXN],v[MAXN];
int ls[MAXN],rs[MAXN];
ll mul[MAXN],add[MAXN];
vector<int>G[MAXN];
int dep[MAXN],st[MAXN];

int tot,rt[MAXN];

void putdown(int p){
	if(mul[p]!=1){
		if(ls[p]){
			mul[ls[p]]*=mul[p];
			T[ls[p]].val*=mul[p];
			add[ls[p]]*=mul[p];
		}
		if(rs[p]){
			mul[rs[p]]*=mul[p];
			T[rs[p]].val*=mul[p];
			add[rs[p]]*=mul[p];
		}
		mul[p]=1;
	}
	if(add[p]){
		if(ls[p]){
			add[ls[p]]+=add[p];
			T[ls[p]].val+=add[p];
		}
		if(rs[p]){
			add[rs[p]]+=add[p];
			T[rs[p]].val+=add[p];
		}
		add[p]=0;
	}
}

int Merge(int x,int y){
	if(!x||!y)return x|y;
	putdown(x);putdown(y);
	if(T[y]<T[x])swap(x,y);
	rs[x]=Merge(rs[x],y);
	swap(ls[x],rs[x]);
	return x;
}

int Del(int x){
	putdown(x);
	return Merge(ls[x],rs[x]);
}

void dfs(int x){
	int i,y;
	dep[x]=dep[f[x]]+1;
	for(i=0;i<G[x].size();i++){
		y=G[x][i];dfs(y);
		rt[x]=Merge(rt[x],rt[y]);
	}
	
	while(rt[x]&&T[rt[x]].val<h[x]){
		ansc[x]++;
		ansk[T[rt[x]].id]=x;
		rt[x]=Del(rt[x]);
	}

	if(x==1){
		while(rt[x]){
			ansk[T[rt[x]].id]=0;
			rt[x]=Del(rt[x]);
		}
	}
	else if(rt[x]){
		if(a[x]==0)add[rt[x]]+=v[x],T[rt[x]].val+=v[x];
		else mul[rt[x]]*=v[x],T[rt[x]].val*=v[x],add[rt[x]]*=v[x];
	}
}

int main(){
	int i,c;
	ll s;
	N=_R();M=_R();
	for(i=1;i<=N;i++)h[i]=_R();
	for(i=2;i<=N;i++){
		f[i]=_R();a[i]=_R();v[i]=_R();
		G[f[i]].push_back(i);
	}
	for(i=1;i<=M;i++){
		s=_R();c=_R();st[i]=c;
		tot++;
		T[tot].val=s;T[tot].id=i;
		mul[tot]=1;
		rt[c]=Merge(rt[c],tot);
	}
	dfs(1);
	for(i=1;i<=M;i++)ansk[i]=dep[st[i]]-dep[ansk[i]];
	for(i=1;i<=N;i++)printf("%d\n",ansc[i]);
	for(i=1;i<=M;i++)printf("%d\n",ansk[i]);
}