[文章目录]
Description
小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。
这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，其中 fi < i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。n,m<=300000
直觉倍增，存储通过的最低初始攻击了以及之后攻击了会怎么变化，然而开不下。
由于每次战斗力变化都不乘负值，也就是对于经过当前位置的骑士的相对攻击力大小不变，可以用可并堆来维护。
对于所有骑士按照攻击力值维护小根堆，dfs树的时候在起始位置加入，碰到骑士该挂掉的位置删除，修改的话在堆中维护标记即可。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 301000
#define pb push_back
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read()
{
ll x=0; char f=0,ch=nc();
while(!isdigit(ch)) {if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
return f ? -x : x;
}
struct heap
{
int nvl,ls,rs;
ll w,ad,mp;
heap(){ls=rs=ad=0; nvl=mp=1;}
}t[N];
void pushdown(int x)
{
if(t[x].mp!=1)
{
if(t[x].ls)
{
t[t[x].ls].mp*=t[x].mp;
t[t[x].ls].ad*=t[x].mp;
t[t[x].ls].w*=t[x].mp;
}
if(t[x].rs)
{
t[t[x].rs].mp*=t[x].mp;
t[t[x].rs].ad*=t[x].mp;
t[t[x].rs].w*=t[x].mp;
}
t[x].mp=1;
}
if(t[x].ad)
{
if(t[x].ls)
{
t[t[x].ls].ad+=t[x].ad;
t[t[x].ls].w+=t[x].ad;
}
if(t[x].rs)
{
t[t[x].rs].ad+=t[x].ad;
t[t[x].rs].w+=t[x].ad;
}
t[x].ad=0;
}
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].w>t[y].w) swap(x,y);
pushdown(x);
t[x].rs=merge(t[x].rs,y);
if(t[t[x].ls].nvl<t[t[x].rs].nvl) swap(t[x].ls,t[x].rs);
t[x].nvl=t[t[x].ls].nvl+1;
return x;
}
int n,m,a[N],head[N],to[N],nxt[N],cnt,c[N],deep[N],ans1[N],ans2[N];
ll v[N],h[N],rt[N];
vector<int> ve[N];
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
deep[to[i]]=deep[x]+1;
dfs(to[i]);
rt[x]=merge(rt[x],rt[to[i]]);
}
for(int i=0;i<(int)ve[x].size();++i) rt[x]=merge(rt[x],ve[x][i]);
while(rt[x]!=0&&t[rt[x]].w<h[x])
{
ans1[x]++;
ans2[rt[x]]=deep[c[rt[x]]]-deep[x];
pushdown(rt[x]);
rt[x]=merge(t[rt[x]].ls,t[rt[x]].rs);
}
if(rt[x])
{
if(!a[x]) t[rt[x]].w+=v[x],t[rt[x]].ad+=v[x];
else t[rt[x]].w*=v[x],t[rt[x]].ad*=v[x],t[rt[x]].mp*=v[x];
}
}
int main()
{
n=read(); m=read();
for(int i=1;i<=n;++i) h[i]=read();
int x;
for(int i=2;i<=n;++i)
{
x=read(); a[i]=read(); v[i]=read();
add(x,i);
}
for(int i=1;i<=m;++i)
{
t[i].w=read(); c[i]=read();
ve[c[i]].pb(i);
}
dfs(1);
while(rt[1]!=0)
{
ans2[rt[1]]=deep[c[rt[1]]]+1;
rt[1]=merge(t[rt[1]].ls,t[rt[1]].rs);
}
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;
}