NC20561. [JLOI2015]城池攻占
描述
输入描述
第 1 行包含两个正整数 n;m，表示城池的数量和骑士的数量。第 2 行包含 n 个整数，其中第 i 个数为 hi，表示城池 i 的防御值。第 3 到 n +1 行，每行包含三个整数。其中第 i +1 行的三个数为 fi;ai;vi，分别表示管辖这座城池的城池编号和两个战斗力变化参数。第 n +2 到 n + m +1 行，每行包含两个整数。其中第 n + i 行的两个数为 si;ci，分别表示初始战斗力和第一个攻击的城池。
输出描述
输出 n + m 行，每行包含一个非负整数。其中前 n 行分别表示在城池 1 到 n 牺牲的骑士数量，后 m 行分别表示骑士 1 到 m 攻占的城池数量。
示例1
输入:
5 5 50 20 10 10 30 1 1 2 2 0 5 2 0 -10 1 0 10 20 2 10 3 40 4 20 4 35 5
输出:
2 2 0 0 0 1 1 3 1 1
C++(clang++11) 解法, 执行用时: 608ms, 内存消耗: 39292K, 提交时间: 2020-12-29 11:22:46
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<" "
#define el <<endl
#define fgx cerr<<" ------------------------------------------------ "<<endl
#define LL long long
#define DB double
#define mpt make_pair
#define pb push_back
inline LL read(){
LL nm=0; bool fh=true; char cw=getchar();
for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return fh?nm:-nm;
}
#define M 300200
int n,m,F[M],op[M],rt[M]; LL h[M],v[M],val[M];
namespace HP{
LL tgM[M],tgA[M]; int ls[M],rs[M],dst[M];
inline void add(int x,LL y){tgA[x]+=y,val[x]+=y;}
inline void mul(int x,LL y){tgM[x]*=y,tgA[x]*=y,val[x]*=y;}
inline void pushdown(int x){
if(tgM[x]^1ll){if(ls[x])mul(ls[x],tgM[x]); if(rs[x])mul(rs[x],tgM[x]); tgM[x]=1ll;}
if(tgA[x]){if(ls[x])add(ls[x],tgA[x]); if(rs[x])add(rs[x],tgA[x]); tgA[x]=0ll;}
}
inline int mg(int x,int y){
if(!x||!y) return x+y; pushdown(x),pushdown(y);
if(val[x]>val[y]) swap(x,y); rs[x]=mg(rs[x],y);
if(dst[rs[x]]>dst[ls[x]]) swap(ls[x],rs[x]);
dst[x]=dst[rs[x]]+1; return x;
}
}
int to[M],nt[M],fs[M],tot,f[M],dep[M],ans[M],hv[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline void dfs(int x){
dep[x]=dep[F[x]]+1;
for(int i=fs[x];i;i=nt[i]) if(to[i]^F[i]) dfs(to[i]),rt[x]=HP::mg(rt[x],rt[to[i]]);
while(rt[x]&&val[rt[x]]<h[x]) HP::pushdown(rt[x]),++ans[x],hv[rt[x]]=dep[f[rt[x]]]-dep[x],rt[x]=HP::mg(HP::ls[rt[x]],HP::rs[rt[x]]);
(!op[x])?(HP::add(rt[x],v[x])):(HP::mul(rt[x],v[x]));
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) h[i]=read();
for(int i=2;i<=n;i++) F[i]=read(),op[i]=read(),v[i]=read(),link(F[i],i);
for(int i=1;i<=m;i++) HP::tgM[i]=1ll;
for(int i=1,x;i<=m;i++) val[i]=read(),f[i]=read(),rt[f[i]]=HP::mg(rt[f[i]],i);
//for(int i=1;i<=n;i++) debug(rt[i])el;
dfs(1); while(rt[1]) hv[rt[1]]=dep[f[rt[1]]],rt[1]=HP::mg(HP::ls[rt[1]],HP::rs[rt[1]]);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);for(int i=1;i<=m;i++)printf("%d\n",hv[i]);
return 0;
}