BZOJ4003 [JLOI2015]城池攻占(左偏树)

题目链接

洛谷

darkbzoj

题意简述

给你一棵树,每个节点有 $h$ 值,一个勇士来到一个节点时如果他的战斗力大于等于 $h$ 就能占领城池并前往这个节点的父亲(除非已经到了根节点),否则阵亡;攻占一个节点后,勇士的战斗力会加/减/乘一个正整数(根据节点而定);每个勇士有初始战斗力和想占领的第一个节点。问,每个节点各有多少个勇士阵亡,每个勇士各占领了几个节点。

简要做法

每个节点搞个小根可并堆维护该节点所有勇士(包括一开始就在这的和爬上来的),当堆顶小于 $h$ 时弹出并更新答案,直到堆为空或者堆顶大于等于 $h$,然后再加/减/乘,合并到父亲。

加/减/乘:更新堆顶并打标记,在所有需要访问儿子的地方(弹出堆顶时/合并时)下传标记。

合并复杂度:每个勇士初始位置需要合并一次,每个节点合并到父亲要一次,$O((n+m)\log m)$;弹出复杂度:每个勇士最多被弹出一次,$O(m\log m)$;修改复杂度:除了下传标记外每次修改都是 $O(1)$ 的,所以是 $O(n)$;总复杂度:$O((n+m)\log m)$。

参考代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

typedef long long ll;

ll read()
{
ll out=0;
int f=1;
char c;
for (c=getchar();!isdigit(c)&&c!='-';c=getchar());
if (c=='-') f=-1,c=getchar();
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out*f;
}

const int N=300010;

struct Node
{
int ls,rs,d;
ll val,add,mul;
Node(){ls=rs=add=0;d=mul=1;}
} t[N];

int merge(int x,int y);
int pop(int x);
void madd(int u,ll x);
void mmul(int u,ll x);
void pushdown(int x);

void add(int u,int v);
void dfs(int u);

int head[N],nxt[N],to[N],cnt;
int n,m,p[N],f[N],a[N],dep[N],c[N],ans1[N],ans2[N];
ll h[N],b[N];

int main()
{
int i;

n=read();
m=read();

for (i=1;i<=n;++i) h[i]=read();

for (i=2;i<=n;++i)
{
f[i]=read();
add(f[i],i);
a[i]=read();
b[i]=read();
}

for (i=1;i<=m;++i)
{
t[i].val=read();
c[i]=read();
p[c[i]]=merge(i,p[c[i]]);
}

dfs(1);

for (i=1;i<=n;++i) printf("%d\n",ans1[i]);
for (i=1;i<=m;++i) printf("%d\n",ans2[i]);

return 0;
}

void dfs(int u)
{
int i,v;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
dep[v]=dep[u]+1;
dfs(v);
}
while (p[u]&&t[p[u]].val<h[u])
{
++ans1[u];
ans2[p[u]]=dep[c[p[u]]]-dep[u];
p[u]=pop(p[u]);
}
if (a[u]) mmul(p[u],b[u]);
else madd(p[u],b[u]);
if (u>1) p[f[u]]=merge(p[u],p[f[u]]);
else while (p[u])
{
ans2[p[u]]=dep[c[p[u]]]+1;
p[u]=pop(p[u]);
}
}

void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}

int merge(int x,int y)
{
if (!x||!y) return x|y;
if (t[x].val>t[y].val) swap(x,y);
pushdown(x);
t[x].rs=merge(t[x].rs,y);
if (t[t[x].rs].d>t[t[x].ls].d) swap(t[x].ls,t[x].rs);
t[x].d=t[t[x].rs].d+1;
return x;
}

int pop(int x)
{
pushdown(x);
return merge(t[x].ls,t[x].rs);
}

void madd(int u,ll x)
{
t[u].val+=x;
t[u].add+=x;
}

void mmul(int u,ll x)
{
t[u].val*=x;
t[u].add*=x;
t[u].mul*=x;
}

void pushdown(int x)
{
mmul(t[x].ls,t[x].mul);
madd(t[x].ls,t[x].add);
mmul(t[x].rs,t[x].mul);
madd(t[x].rs,t[x].add);
t[x].add=0;
t[x].mul=1;
}