BZOJ 4003 [JLOI2015]城池攻占

题目大意

给你一颗树，树上每个节点都有一个权值，还给你许多人，每个人有一个初始权值，每个人从一个节点出发，一直向父亲前进。在抵达一个节点的时候如果自己的权值小于此节点的权值那么就会GG，否则就会获得此点的增益效果（乘上一个数/加上一个数），问每个节点GG多少人&每个人GG在哪里。

这道题可并堆解决。

我想了很长时间如何处理这些问题，咋也没想到= =

实际上，直接用可并堆维护优先队列就可以了。

对于每一个点的增益效果，直接对这个堆维护两个标记——乘标记和加标记，处理的时候注意乘标记对加标记的影响……

怎么WA了！

桑心= =

数据还太大调试不能……

de了很长时间的bug终于发现了哪里出现了问题——删除点的时候理论上我们应该提取出堆顶，将堆的左儿子和右儿子合并作为堆顶，此时就删除成功了……但是我忘记了一点：删除之前应该将标记下传！标记下传！下传！传！

Emmmmmmmmmmmmmmmmmm......

大概就是这样……如果不这样做的话就会GG，有的标记就永远的，留在了被丢弃的根上……

具体请看代码第54行。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 300010

int n,m,fa[N],a[N],c[N],ls[N],rs[N],rt[N],cnt[N],d[N],l[N],depth[N];
long long h[N],v[N],s[N],lzu[N],lzm[N];

int to[N],nex[N],head[N],tot;

inline void AE(int tx,int ty){to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}

inline void pushdown(int pos)
{
	if(lzm[pos]!=1)
	{
		if(ls[pos]) s[ls[pos]]*=lzm[pos],lzm[ls[pos]]*=lzm[pos],lzu[ls[pos]]*=lzm[pos];
		if(rs[pos]) s[rs[pos]]*=lzm[pos],lzm[rs[pos]]*=lzm[pos],lzu[rs[pos]]*=lzm[pos];
		lzm[pos]=1;
	}
	if(lzu[pos])
	{
		if(ls[pos]) s[ls[pos]]+=lzu[pos],lzu[ls[pos]]+=lzu[pos];
		if(rs[pos]) s[rs[pos]]+=lzu[pos],lzu[rs[pos]]+=lzu[pos];
		lzu[pos]=0;
	}
}

int merge(int tx,int ty)
{
	if(!tx) return ty;
	if(!ty) return tx;
	pushdown(tx),pushdown(ty);
	if(s[tx]>s[ty]) swap(tx,ty);
	rs[tx]=merge(rs[tx],ty);
	if(l[ls[tx]]<l[rs[tx]]) swap(ls[tx],rs[tx]);
	l[tx]=l[rs[tx]]+1;
	return tx;
}

void DFS(int pos)
{
	for(int i=head[pos];i;i=nex[i])
	{
		depth[to[i]]=depth[pos]+1;
		DFS(to[i]);
		rt[pos]=merge(rt[pos],rt[to[i]]);
	}
	while(rt[pos]&&s[rt[pos]]<h[pos])
	{
		cnt[pos]++;
		d[rt[pos]]=pos;
		pushdown(rt[pos]);
		rt[pos]=merge(ls[rt[pos]],rs[rt[pos]]);
	}
	if(a[pos]) s[rt[pos]]*=v[pos],lzm[rt[pos]]*=v[pos],lzu[rt[pos]]*=v[pos];
	else s[rt[pos]]+=v[pos],lzu[rt[pos]]+=v[pos];
}

int main()
{
	scanf("%d%d",&n,&m);
	l[0]=-1;
	for(int i=1;i<=m;++i) lzm[i]=1;
	for(int i=1;i<=n;++i) scanf("%lld",h+i);
	for(int i=2;i<=n;++i)
	{
		scanf("%d%d%lld",fa+i,a+i,v+i);
		AE(fa[i],i);
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%lld%d",s+i,c+i);
		rt[c[i]]=merge(rt[c[i]],i);
	}
	depth[1]=1;
	DFS(1);
	for(int i=1;i<=n;++i) printf("%d\n",cnt[i]);
	for(int i=1;i<=n;++i) printf("%d\n",depth[c[i]]-depth[d[i]]);
}