网站非法篡改,兰州网站建设慕枫,拓网手机版网站管理系统,加盟装修公司哪家不要加盟费城池攻占 bzoj-4003 JLOI-2015 题目大意#xff1a;一颗n个节点的有根数#xff0c;m个有初始战斗力的骑士都站在节点上。每一个节点有一个standard#xff0c;如果这个骑士的战斗力超过了这个门槛#xff0c;他就会根据城池的奖励增加自己的战斗力。具体地#xff1a;每一…城池攻占 bzoj-4003 JLOI-2015 题目大意一颗n个节点的有根数m个有初始战斗力的骑士都站在节点上。每一个节点有一个standard如果这个骑士的战斗力超过了这个门槛他就会根据城池的奖励增加自己的战斗力。具体地每一个城池有一个flag和一个val表示成功到达这个城市的骑士的战斗力会乘上val还是加上val。每个骑士都只会向根节点进攻。输出每个骑士败北的城市编号。如果这个骑士成功到达根节点输出0。 注释$1\le n,m \le 3\cdot 10^5$$-10^{18}\le standard , val , attack \le 10^{18}$。保证每一个骑士的atk不大于longlong。 想法GXZlegend可并堆例题。和上两道题类似地我们对于每一个城池维护一个小根堆元素是是当前节点为子树里的骑士到达这里的atk我们自底向顶修改城墙顺便将骑士向上推以及标记的下传。我们在merge函数中完成pushdown的操作。特别地在维护双标记的时候我默认是先乘后加所以在pushdown的时候如果发现有乘法标记的话需要先将加法标记扩大再下传。 最后附上丑陋的代码... ... #include cstdio
#include cstring
#include algorithm
#define N 300010
using namespace std;
typedef long long ll;
int head[N],to[N],type[N],next[N],cnt,root[N],l[N],r[N],d[N],deep[N],from[N],kill[N],atk[N];
ll val[N],h[N],key[N],tadd[N],tmul[N];
inline void add(int x,int y,int a,ll b)
{to[cnt]y;type[cnt]a;val[cnt]b;next[cnt]head[x];head[x]cnt;
}
inline void pushdown(int x)
{if(!x)return;if(tmul[x]!1){key[l[x]]*tmul[x];tadd[l[x]]*tmul[x];tmul[l[x]]*tmul[x];key[r[x]]*tmul[x];tadd[r[x]]*tmul[x];tmul[r[x]]*tmul[x];tmul[x]1;}if(tadd[x]){key[l[x]]tadd[x];tadd[l[x]]tadd[x];key[r[x]]tadd[x];tadd[r[x]]tadd[x];tadd[x]0;}
}
int merge(int x,int y)
{if(!x) return y;if(!y) return x;pushdown(x),pushdown(y);if(key[x]key[y]) swap(x,y);r[x]merge(r[x],y);if(d[l[x]]d[r[x]]) swap(l[x],r[x]);d[x]d[r[x]]1;return x;
}
void dfs(int x)
{for(int ihead[x];i;inext[i]){deep[to[i]]deep[x]1;dfs(to[i]);if(type[i]){key[root[to[i]]]*val[i];tadd[root[to[i]]]*val[i];tmul[root[to[i]]]*val[i];}else{key[root[to[i]]]val[i];tadd[root[to[i]]]val[i];}root[x]merge(root[x],root[to[i]]);}while(root[x]key[root[x]]h[x]){kill[x],atk[root[x]]x,pushdown(root[x]),root[x]merge(l[root[x]],r[root[x]]);}
}
int main()
{int n,m,x,a;ll b;scanf(%d%d,n,m);for(int i1;in;i) scanf(%lld,h[i]);for(int i2;in;i) scanf(%d%d%lld,x,a,b),add(x,i,a,b);for(int i1;im;i){tmul[i]1,scanf(%lld%d,key[i],from[i]),root[from[i]]merge(root[from[i]],i);}d[0]-1,deep[1]1;dfs(1);for(int i1;in;i){printf(%d\n,kill[i]);}for(int i1;im;i){printf(%d\n,deep[from[i]]-deep[atk[i]]);}return 0;
}小结type标记存在哪里都无所谓qwq 转载于:https://www.cnblogs.com/ShuraK/p/8872352.html
