BZOJ4003：[JLOI2015]城池攻占

浅谈左偏树：https://www.cnblogs.com/AKMer/p/10246635.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4003

从下往上合并左偏树然后把战斗力低的踢掉。做完之后打标记。因为不会乘负数所以小根堆的性质不会被破坏。

不知道为什么用\(struct\)封装左偏树会\(RE\)，改成\(namespace\)之后才\(AC\)。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=3e5+5;

bool a[maxn];

int dep[maxn];

ll h[maxn],v[maxn];

int n,m,tot,rt[maxn],ans[maxn];

int now[maxn],pre[maxn],to[maxn];

struct Knight {int c,ans;ll s;}p[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

ll READ() {

	ll x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot,to[tot]=b;

}

namespace T {//用struct会RE，我也不清楚

	int dist[maxn];

	int son[maxn][2];

	ll add_tag[maxn],mul_tag[maxn];

	void init() {

		dist[0]=-1;

		for(int i=1;i<=m;i++)

			add_tag[i]=0,mul_tag[i]=1;

	}

	void make_mul_tag(int u,ll v) {

		p[u].s*=v,add_tag[u]*=v,mul_tag[u]*=v;

	}

	void make_add_tag(int u,ll v) {

		p[u].s+=v,add_tag[u]+=v;

	}

	void push_down(int p) {

		if(mul_tag[p]!=1) {

			make_mul_tag(son[p][0],mul_tag[p]);

			make_mul_tag(son[p][1],mul_tag[p]);

			mul_tag[p]=1;

		}

		if(add_tag[p]) {

			make_add_tag(son[p][0],add_tag[p]);

			make_add_tag(son[p][1],add_tag[p]);

			add_tag[p]=0;

		}

	}

	int merge(int a,int b) {

		if(!a||!b)return a+b;

		if(p[a].s>p[b].s)swap(a,b);

		push_down(a);

		son[a][1]=merge(son[a][1],b);

		if(dist[son[a][1]]>dist[son[a][0]])

			swap(son[a][1],son[a][0]);

		dist[a]=dist[son[a][1]]+1;

		return a;

	}

	int pop(int u) {

		push_down(u);

		int tmp=merge(son[u][0],son[u][1]);

		son[u][0]=son[u][1]=0;

		return tmp;

	}

}

void dfs(int u) {

	for(int P=now[u],V=to[P];P;P=pre[P],V=to[P])

		dep[V]=dep[u]+1,dfs(V),rt[u]=T::merge(rt[u],rt[V]);

	while(rt[u]&&p[rt[u]].s<h[u]) {

		ans[u]++;p[rt[u]].ans=dep[p[rt[u]].c]-dep[u];

		rt[u]=T::pop(rt[u]);

	}

	if(a[u])T::make_mul_tag(rt[u],v[u]);

	else T::make_add_tag(rt[u],v[u]);

}

int main() {

	n=read(),m=read();

	for(int i=1;i<=n;i++)h[i]=READ();

	for(int i=2;i<=n;i++) {

		int f=read();add(f,i);

		a[i]=read(),v[i]=READ();

	}T::init();

	for(int i=1;i<=m;i++) {

		p[i].s=READ(),p[i].c=read();

		rt[p[i].c]=T::merge(rt[p[i].c],i);

	}dep[1]=1;dfs(1);

	while(rt[1]) {

		p[rt[1]].ans=dep[p[rt[1]].c];

		rt[1]=T::pop(rt[1]);

	}

	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);

	for(int i=1;i<=m;i++)printf("%d\n",p[i].ans);

	return 0;

}

巴特西

BZOJ4003：[JLOI2015]城池攻占

最新文章

热门文章