BZOJ 4003 (可并堆）

题面

小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。

这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，

其中 fi <i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其

中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。

每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可

以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力

将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。

除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

分析

直接模拟，初始时候每个树上的节点都属于一个单独的可并堆（堆顶元素最小）

把每个骑士放到它出发节点的可并堆中，值为初始战斗力

DFS回溯的时候将子节点的可并堆和当前节点的可并堆合并

弹出所有战斗力小于防御值的节点

然后打标记区间更新，增加战斗力的值

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 300005

using namespace std;

inline void qread(int &x) {

	x=0;

	int sign=1;

	char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') sign=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	x*=sign;

}

inline void qread(long long &x) {

	x=0;

	long long sign=1;

	char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') sign=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	x*=sign;

}

inline void qprint(int x) {

	if(x<0) {

		putchar('-');

		qprint(-x);

	} else if(x==0) {

		putchar('0');

		return;

	} else {

		if(x/10>0) qprint(x/10);

		putchar(x%10+'0');

	}

}

struct edge {

	int from;

	int to;

	int next;

} E[maxn<<1];

int sz=1;

int head[maxn];

void add_edge(int u,int v) {

	sz++;

	E[sz].from=u;

	E[sz].to=v;

	E[sz].next=head[u];

	head[u]=sz;

}

struct left_tree {

	int l[maxn],r[maxn];

	int root[maxn];

	int dis[maxn];

	long long val[maxn];

	long long atag[maxn];//加法标记

	long long mtag[maxn];//乘法标记

	void add_tag(int x,long long addv,long long mulv) {//给某个节点打标记，简化代码

		if(x==0) return;

		val[x]=(val[x]*mulv)+addv;

		mtag[x]=mtag[x]*mulv;

		atag[x]=(atag[x]*mulv)+addv;

	}

	void push_down(int x) {

		add_tag(l[x],atag[x],mtag[x]);

		add_tag(r[x],atag[x],mtag[x]);

		atag[x]=0;

		mtag[x]=1;

	}

	int _merge(int x,int y) {

		if(!x||!y) return x+y;

		push_down(x);

		push_down(y);

		if(val[x]>val[y]) swap(x,y);

		r[x]=_merge(r[x],y);

		swap(l[x],r[x]);

		return x;

	}

	void merge(int x,int y) {

		root[x]=_merge(root[x],root[y]);

	}

	void insert(int x,long long v){

		val[x]=v;

		atag[x]=0;

		mtag[x]=1;

	}

	void del(int &x) {

		push_down(x);

		x=_merge(l[x],r[x]);

	}

} T;

int n,m;

long long h[maxn];

long long v[maxn];

int town[maxn],man[maxn];

int deep[maxn];

int is_mul[maxn];

int	start[maxn];

void dfs(int x,int fa) {

//	printf("%d\n",x);

	deep[x]=deep[fa]+1;

	for(int i=head[x]; i; i=E[i].next) {

		int y=E[i].to;

		if(y!=fa) {

			dfs(y,x);

			T.merge(x,y);

		}

	}

	while(T.root[x]&&T.val[T.root[x]]<h[x]) {

		town[x]++;

		man[T.root[x]]=deep[start[T.root[x]]]-deep[x];

		T.del(T.root[x]);

	}

	if(is_mul[x]) {

		T.add_tag(T.root[x],0,v[x]);

	} else {

		T.add_tag(T.root[x],v[x],1);

	}

}

int main() {

	qread(n);

	qread(m);

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

		qread(h[i]);

	}

	int fa,s,c;

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

		qread(fa);

		qread(is_mul[i]);

		qread(v[i]);

		add_edge(fa,i);

		add_edge(i,fa);

	}

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

		qread(s);

		qread(c);

		start[i]=c;

		T.insert(i,s);

		T.root[c]=T._merge(T.root[c],i);

	}

	dfs(1,0);

	while(T.root[1]){

		man[T.root[1]]=deep[start[T.root[1]]];

		T.del(T.root[1]);

	}

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

		qprint(town[i]);

		putchar('\n');

	}

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

		qprint(man[i]);

		putchar('\n');

	}

}

巴特西

BZOJ 4003 (可并堆）

题面

分析

代码

最新文章

热门文章