首页 > 代码库 > 【bzoj2333】 SCOI2011—棘手的操作

【bzoj2333】 SCOI2011—棘手的操作

http://www.lydsy.com/JudgeOnline/problem.php?id=2333 (题目链接)

题意

  N个节点维护一些操作。。

Solution

  我们用可并大根堆进行维护。

  对于每个连通块建一个局部可并堆,因为要询问全局最大值,所以还要对全局建一个全局可并堆记录之前局部可并堆堆顶元素。

  U:合并x所在的堆以及y所在的堆,并在全局堆中删除合并前的局部堆堆顶元素,因为它合并以后已经不是其连通块的堆顶了。

  A1:在堆中删除,更新后再加入堆

  A2:找到其堆顶,对堆顶进行修改并打上标记

  A3:对全局都打个标记即可

  F1:将标记下传后输出

  F2:找到其所在的堆顶输出

  F3:输出全局堆的堆顶

细节

  码农题就是细节多

代码

// bzoj2333#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=300010;struct heap {int val,tag,l,r,fa;}q[maxn],qq[maxn];int n,m,rt,Tag;char op[10];void pushdown(heap *q,int k) {   //标记下传	q[q[k].l].val+=q[k].tag;q[q[k].l].tag+=q[k].tag;	q[q[k].r].val+=q[k].tag;q[q[k].r].tag+=q[k].tag;	q[k].tag=0;}int merge(heap *q,int x,int y) {   //合并	if (x==0 || y==0) return x+y;	if (q[x].val<q[y].val) swap(x,y);	if (q[x].tag) pushdown(q,x);	q[x].r=merge(q,q[x].r,y);	q[q[x].r].fa=x;	swap(q[x].l,q[x].r);	return x;}int find(heap *q,int x) {   //寻找堆顶并下传标记,注意下传标记和向上查询的顺序	int tmp=x;	if (q[x].fa) tmp=find(q,q[x].fa);	if (q[x].tag) pushdown(q,x);	return tmp;}int del(heap *q,int x) {   //删除	int f=find(q,x);	int tmp=merge(q,q[x].l,q[x].r);	if (q[q[x].fa].l==x) q[q[x].fa].l=tmp;	else q[q[x].fa].r=tmp;	q[tmp].fa=q[x].fa;	return f==x ? (tmp ? find(q,tmp) : 0) : f;   //返回删除后该堆的堆顶,此处不是很好处理,最好画个图理解一下}int build() {   //对全局建堆	queue<int> Q;	for (int i=1;i<=n;i++) Q.push(i),qq[i]=q[i];	while (Q.size()>1) {		int x=Q.front();Q.pop();		int y=Q.front();Q.pop();		Q.push(merge(qq,x,y));	}	return Q.front();}void newq(heap *q,int x,int val) {   //新建元素	q[x].l=q[x].r=q[x].fa=0;	q[x].val=val;}int main() {	scanf("%d",&n);q[0].val=-inf;	for (int i=1;i<=n;i++) scanf("%d",&q[i].val);	rt=build();	scanf("%d",&m);	for (int x,y,i=1;i<=m;i++) {		scanf("%s",op);		if (op[0]==‘U‘) {			scanf("%d%d",&x,&y);			int r1=find(q,x),r2=find(q,y);			if (r1!=r2) {				if (merge(q,r1,r2)==r1) rt=del(qq,r2);				else rt=del(qq,r1);			}		}		if (op[0]==‘A‘) {			if (op[1]==‘1‘) {				scanf("%d%d",&x,&y);				rt=del(qq,find(q,x));				int k=del(q,x);				newq(q,x,q[x].val+y);				k=merge(q,k,x);				newq(qq,k,q[k].val);				rt=merge(qq,k,rt);			}			if (op[1]==‘2‘) {				scanf("%d%d",&x,&y);				int f=find(q,x);				q[f].val+=y;q[f].tag+=y;				rt=del(qq,f);				newq(qq,f,qq[f].val+y);				rt=merge(qq,rt,f);			}			if (op[1]==‘3‘) scanf("%d",&y),Tag+=y;		}		if (op[0]==‘F‘) {			if (op[1]==‘1‘) {				scanf("%d",&x);				find(q,x),printf("%d\n",q[x].val+Tag);			}			if (op[1]==‘2‘) {				scanf("%d",&x);				printf("%d\n",q[find(q,x)].val+Tag);			}			if (op[1]==‘3‘) printf("%d\n",qq[rt].val+Tag);		}	}    return 0;}

 

【bzoj2333】 SCOI2011—棘手的操作