首页 > 代码库 > 【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—棘手的操作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。