安徽省建设工程八大员报名网站,网络推广服务公司外包,护卫神 安装wordpress,做企业网站找谁正题
题目链接:https://www.luogu.com.cn/problem/P3261 题目大意 nnn个点的树#xff0c;每个节点有一个防御值和一个攻击后的影响(让你的伤害加上一个数或者乘上一个数)
然后mmm个骑士#xff0c;给定初始攻击点和初始伤害#xff0c;不停往上走#xff0c;遇到防御小于…正题
题目链接:https://www.luogu.com.cn/problem/P3261 题目大意
nnn个点的树每个节点有一个防御值和一个攻击后的影响(让你的伤害加上一个数或者乘上一个数)
然后mmm个骑士给定初始攻击点和初始伤害不停往上走遇到防御小于他伤害的城堡就攻占否则就死亡
求每个城堡干死了多少个勇士每个勇士干死了多少个城堡。 解题思路
显然以伤害建立一个小根堆每次想不满足的丢出去然后打上延迟标记全部修改。然后每次把所有子树的堆都合并。
这里比较懒就骑士和节点都建立了堆所有速度比较慢。 codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N6e510;
ll n,m,h[N],dep[N],ans1[N],ans2[N],val[N];
struct Left_Tree{#define ls t[x][0]#define rs t[x][1]ll fa[N],add[N],mul[N],dis[N],t[N][2];void Change(ll x,ll v1,ll v2){if(!x) return;val[x]*v1;val[x]v2;add[x]*v1;mul[x]*v1;add[x]v2;return;}void PushDown(ll x){Change(ls,mul[x],add[x]);Change(rs,mul[x],add[x]);mul[x]1;add[x]0;return;}ll Get(ll x){return (fa[x]x)?(x):(fa[x]Get(fa[x]));}ll Merge(ll x,ll y){if(!x||!y) return xy;if(val[x]val[y]) swap(x,y);PushDown(x);PushDown(y);rsMerge(rs,y);fa[ls]fa[rs]x;if(dis[ls]dis[rs]) swap(ls,rs);dis[x]dis[rs]1;return x;}void Del(ll x){PushDown(x);Change(x,0,0);fa[ls]ls;fa[rs]rs;fa[x]Merge(ls,rs);return;} #undef ls#undef rs
}T;
struct node{ll to,next;
}a[N];
ll mul[N],add[N],s[N],ls[N],tot;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x){for(ll ils[x];i;ia[i].next){ll ya[i].to;dep[y]dep[x]1;dfs(y);T.Merge(T.Get(x),T.Get(y));}ll k;while(val[kT.Get(x)]h[x]k){if(kn){ans1[x];ans2[k-n]dep[s[k-n]]-dep[x];}T.Del(k);}T.Change(T.Get(x),mul[x],add[x]);return;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld,h[i]),T.fa[i]i,mul[i]1;for(ll i2;in;i){ll op,x,y;scanf(%lld%lld%lld,x,op,y);if(op) mul[i]y;else add[i]y;addl(x,i);}for(ll i1;im;i){scanf(%lld%lld,val[in],s[i]);ans2[i]-1;T.fa[in]in;T.Merge(in,T.Get(s[i]));}dep[1]1;dfs(1);for(ll i1;in;i)printf(%lld\n,ans1[i]);for(ll i1;im;i)if(ans2[i]0) printf(%lld\n,dep[s[i]]);else printf(%lld\n,ans2[i]);return 0;
}
