首页 > 代码库 > bzoj-4003 城池攻占

bzoj-4003 城池攻占

题意:

给出一个n个结点的有根树,和m个骑士;

树上的结点——城池有一个防御值,骑士有一个战斗力;

当骑士的战斗力大于等于城池时,城池被攻破。骑士的战斗力变化,并向树上的父节点前进;

否则骑士死亡。

求最后每一个城池干掉的人数和每一个人干掉的城数;

骑士之间没有先后关系,就是说事实上每一个骑士是在自己的副本里战斗(笑)。

n,m<=300000。


题解:

首先依据战斗力变化的规则,从某个结点出发,战斗力弱的能到达哪里,战斗力强的也一定能够。

所以考虑一个结点上的所有骑士。仅仅须要比較防御值和最蒟蒻的骑士的战斗力就能够了。

他过不去就把他干掉比較下一个。过去了全部人就都过去了;

这实际上就像一个堆的模型了,仅仅是另一些问题要处理;

一是树形的结构。这个用拓扑排序能够搞定;

然后是树上各点间的转移,显然是要把几个结点的人集合起来,也就是堆的合并;

还有战斗力改变的处理,这里用能够打标记的左偏堆实现(当然左撇子右偏堆也能够啊XD)

之后就是码代码调试了。。

。Pushdown写挂一发。标记没开longlong一发,%I64d一发;

当年省选暴力写炸了= =,似乎是乱搞读入优化的锅咯;


代码:


#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 310000
#define lson a[a[x].l]
#define rson a[a[x].r]
using namespace std;
typedef long long ll;
struct node
{
	int l,r,dis,pos,cnt,c_cnt;
	ll cadd,cmul,val;
}a[N];
ll h[N],v[N];
int f[N],out[N],tree[N];
int ans_of_knight[N],ans_of_city[N];
int q[N],st,en;
bool t[N];
void Pushdown(int x)
{
	if(a[x].c_cnt)
	{
		lson.cnt+=a[x].c_cnt;
		rson.cnt+=a[x].c_cnt;
		lson.c_cnt+=a[x].c_cnt;
		rson.c_cnt+=a[x].c_cnt;
		a[x].c_cnt=0;
	}
	if(a[x].cmul!=1)
	{
		lson.val*=a[x].cmul;
		rson.val*=a[x].cmul;
		lson.cadd*=a[x].cmul;
		rson.cadd*=a[x].cmul;
		lson.cmul*=a[x].cmul;
		rson.cmul*=a[x].cmul;
		a[x].cmul=1;
	}
	if(a[x].cadd)
	{
		lson.val+=a[x].cadd;
		rson.val+=a[x].cadd;
		lson.cadd+=a[x].cadd;
		rson.cadd+=a[x].cadd;
		a[x].cadd=0;
	}
}
int merge(int x,int y)
{
	if(!x||!y)	return x?

x:y; if(a[x].val>a[y].val) swap(x,y); Pushdown(x); a[x].r=merge(a[x].r,y); if(lson.dis<rson.dis) swap(a[x].l,a[x].r); a[x].dis=rson.dis+1; return x; } void update(int x) { int root=tree[x]; a[root].c_cnt++; a[root].cnt++; if(t[x]) { a[root].cmul*=v[x]; a[root].cadd*=v[x]; a[root].val*=v[x]; } else { a[root].cadd+=v[x]; a[root].val+=v[x]; } } int main() { int n,m,i,j,k,x,y; ll temp; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%lld",h+i); for(i=2;i<=n;i++) { scanf("%d%d%lld",f+i,t+i,v+i); out[f[i]]++; } a[0].dis=-1; for(i=1;i<=m;i++) { scanf("%lld%d",&temp,&x); a[i].pos=i,a[i].val=temp,a[i].cmul=1; tree[x]=merge(tree[x],i); } st=1,en=0; for(i=1;i<=n;i++) { if(!out[i]) q[++en]=i; } while(st<=en) { x=q[st++]; while(h[x]>a[tree[x]].val&&tree[x]) { ans_of_city[x]++; ans_of_knight[a[tree[x]].pos]=a[tree[x]].cnt; Pushdown(tree[x]); tree[x]=merge(a[tree[x]].l,a[tree[x]].r); } update(x); tree[f[x]]=merge(tree[f[x]],tree[x]); out[f[x]]--; if(!out[f[x]]) q[++en]=f[x]; } while(tree[0]) { ans_of_knight[a[tree[0]].pos]=a[tree[0]].cnt; Pushdown(tree[0]); tree[0]=merge(a[tree[0]].l,a[tree[0]].r); } for(i=1;i<=n;i++) printf("%d\n",ans_of_city[i]); for(i=1;i<=m;i++) printf("%d\n",ans_of_knight[i]); return 0; }





bzoj-4003 城池攻占