bzoj 4003 城池攻占

Posted on | Views:

可并堆.

如果对于每个骑士,我们都求出他在哪个城池牺牲,那么两个问题都可以解决.

对于树上的每个节点,开一个可并堆,维护当前这个点上所有骑士的战斗力.

对树进行 $dfs$ .

先将堆中的战斗力修改,然后弹出在当前节点牺牲的骑士,更新答案,再将剩余的骑士合并到父亲上去.

加或者乘一个正数是不会改变战斗力的大小关系的,所以修改时在根节点处打标记就可以了,堆的形态不会变化.

最后还要处理攻占根节点后仍未牺牲的骑士.

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
123
124
125
126
127
128
129
130
131
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10;
int n,m,ecnt=0,head[MAXN],to[MAXN],nx[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int dep[MAXN],st[MAXN],a[MAXN];
ll h[MAXN],v[MAXN];
struct node
{
	int ls,rs;
	ll addtag,multag,val;
	node(){addtag=0,multag=1;ls=rs=0;}
}Heap[MAXN];
int rt[MAXN];
void upd_mul(int x,ll c)
{
	Heap[x].val*=c;
	Heap[x].multag*=c;
	Heap[x].addtag*=c;
}
void upd_add(int x,ll c)
{
	Heap[x].val+=c;
	Heap[x].addtag+=c;
}
void pushdown(int x)
{
	if(Heap[x].multag!=1)
	{
		if(Heap[x].ls)
			upd_mul(Heap[x].ls,Heap[x].multag);
		if(Heap[x].rs)
			upd_mul(Heap[x].rs,Heap[x].multag);
		Heap[x].multag=1;
	}
	if(Heap[x].addtag)
	{
		if(Heap[x].ls)
			upd_add(Heap[x].ls,Heap[x].addtag);
		if(Heap[x].rs)
			upd_add(Heap[x].rs,Heap[x].addtag);
		Heap[x].addtag=0;
	}
}
int merge(int x,int y)
{
	if(!x || !y)
		return x+y;
	if(Heap[x].val>Heap[y].val)
		swap(x,y);
	pushdown(x);
	Heap[x].rs=merge(Heap[x].rs,y);
	swap(Heap[x].ls,Heap[x].rs);
	return x;
}
void pop(int &x)
{
	pushdown(x);
	x=merge(Heap[x].ls,Heap[x].rs);
}
int ans1[MAXN],ans2[MAXN];
void dfs(int u)
{
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		dep[v]=dep[u]+1;
		dfs(v);
		rt[u]=merge(rt[u],rt[v]);
	}
	while(rt[u] && Heap[rt[u]].val<h[u])
	{
		++ans1[u];
		ans2[rt[u]]=dep[st[rt[u]]]-dep[u];
		pop(rt[u]);
	}
	if(a[u]==0)
		upd_add(rt[u],v[u]);
	else
		upd_mul(rt[u],v[u]);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		h[i]=read();
	for(int i=2;i<=n;++i)
	{
		int f=read();
		addedge(f,i);
		a[i]=read();
		v[i]=read();
	}
	for(int i=1;i<=m;++i)
	{
		Heap[i].val=read();
		st[i]=read();
		rt[st[i]]=merge(rt[st[i]],i);
	}
	dfs(1);
	while(rt[1])
	{
		ans2[rt[1]]=dep[st[rt[1]]]+1;
		pop(rt[1]);
	}
	for(int i=1;i<=n;++i)
		printf("%d\n",ans1[i]);
	for(int i=1;i<=m;++i)
		printf("%d\n",ans2[i]);
	return 0;
}