题目链接
考虑每个节点建一个以骑士攻击力为关键字的小根堆,从叶子节点向上扫描,每次弹堆至堆顶骑士攻击力大于当前城池防御力,可以采用左偏树维护,
对于城池的攻击力改变值,可以借用线段树区间修改的懒标记思想,打上乘法及加法标记,每次涉及到改变堆结构的操作前下放标记即可。
稍微卡常之后可过
代码
# include <iostream>
# include <cstdio>
# define MAXN 300005
struct edge{
int v, next;
}e[MAXN];
int hd[MAXN], cntE;
struct heap{
int ls, rs, dis, rt;
long long tagA, tagM; // 乘标记,加标记
}hp[MAXN];
struct knight{
long long pow;
int fir;
}kn[MAXN];
struct city{
int dep; // 深度
long long def; // 防御力
long long ai, vi; // 改变值
}ct[MAXN];
int death[MAXN], destory[MAXN];
template<typename T>
void rd(T & x);
void AddE(int u, int v);
void DFS(int now, int fa);
int Merge(int x, int y);
void PushDown(int now);
void Calc(int now, long long mul, long long pls);
// int Find(int x);
int main(){
int n, m;
rd<int>(n), rd<int>(m);
hp[0].dis = -1;
for(int i = 1; i <= n; i++){
rd<long long>(ct[i].def);
}
for(int i = 2, tmp; i <= n; i++){
rd<int>(tmp), rd<long long>(ct[i].ai), rd<long long>(ct[i].vi);
AddE(tmp, i);
}
for(int i = 1; i <= m; i++){
rd<long long>(kn[i].pow), rd<int>(kn[i].fir);
hp[kn[i].fir].rt = Merge(hp[kn[i].fir].rt, i); // 注意每个位置可能不止一个士兵,所以不能直接将 rt 设为 i 而应该合并
hp[i].tagM = 1;
}
DFS(1, 0);
while(hp[1].rt){
PushDown(hp[1].rt);
destory[hp[1].rt] = ct[kn[hp[1].rt].fir].dep;
hp[1].rt = Merge(hp[hp[1].rt].ls, hp[hp[1].rt].rs);
}
for(int i = 1; i <= n; i++){
printf("%d\n", death[i]);
}
for(int i = 1; i <= m; i++){
printf("%d\n", destory[i]);
}
return 0;
}
// int Find(int x){
// return hp[x].rt == x ? x : hp[x].rt = Find(hp[x].rt);
// }
void Calc(int now, long long mul, long long pls){
if(now){
(kn[now].pow *= mul) += pls;
hp[now].tagM *= mul;
(hp[now].tagA *= mul) += pls;
}
}
void PushDown(int now){
Calc(hp[now].ls, hp[now].tagM, hp[now].tagA);
Calc(hp[now].rs, hp[now].tagM, hp[now].tagA);
hp[now].tagM = 1, hp[now].tagA = 0;
}
int Merge(int x, int y){
if(!x || !y){
return x + y;
}
PushDown(x); PushDown(y);
if(kn[x].pow > kn[y].pow){
std::swap(x, y);
}
hp[x].rs = Merge(hp[x].rs, y);
if(hp[hp[x].ls].dis < hp[hp[x].rs].dis){
std::swap(hp[x].ls, hp[x].rs);
}
hp[x].dis = hp[hp[x].rs].dis + 1;
return x;
}
void DFS(int now, int fa){
ct[now].dep = ct[fa].dep + 1;
for(int i = hd[now]; i; i = e[i].next){
DFS(e[i].v, now);
hp[now].rt = Merge(hp[now].rt, hp[e[i].v].rt);
}
while(hp[now].rt && kn[hp[now].rt].pow < ct[now].def){
PushDown(hp[now].rt);
death[now] += 1, destory[hp[now].rt] = ct[kn[hp[now].rt].fir].dep - ct[now].dep;
hp[now].rt = Merge(hp[hp[now].rt].ls, hp[hp[now].rt].rs);
}
if(ct[now].ai){
Calc(hp[now].rt, ct[now].vi, 0);
}
else{
Calc(hp[now].rt, 1, ct[now].vi);
}
}
void AddE(int u, int v){
e[++cntE].v = v, e[cntE].next = hd[u], hd[u] = cntE;
}
template<typename T>
void rd(T & x){
x = 0; T fl = 1;
int ch = getchar();
for( ;!isdigit(ch); ch = getchar()){
if(ch == '-'){
fl = -1;
}
}
for( ; isdigit(ch); ch = getchar()){
x = x * 10 + ch - '0';
}
x *= fl;
}