启发式合并堆就可以了？
使用插入\(O(1)\)的配对堆就是\(O(nlogn)\)了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
// <2333.cpp> - Thu Mar 2 10:39:49 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <ext/pb_ds/priority_queue.hpp> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=300010; const int INF=1e9; int a[MAXN],f[MAXN],k[MAXN]; __gnu_pbds::priority_queue <int>::iterator it; struct heap{ __gnu_pbds::priority_queue <int> A,B,C; void push(int x){A.push(x);} void kill(int x){B.push(x);} void add(int x){C.push_back(x);} int top(){ while(!B.empty()&&A.top()==B.top())A.pop(),B.pop(); return A.top(); } int size(){return C.size();} void join(heap &b,int x){ for(it=b.A.begin();it!=b.A.end();it++)A.push(*it+x); for(it=b.B.begin();it!=b.B.end();it++)B.push(*it+x); for(it=b.C.begin();it!=b.C.end();it++)C.push_back(*it),a[*it]+=x; b.A.clear();b.B.clear();b.C.clear(); } }q[MAXN]; int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];} char s[10]; int main(){ freopen("2333.in","r",stdin); freopen("2333.out","w",stdout); int n=gi(); for(int i=1;i<=n;i++){ a[i]=gi(),f[i]=i; q[i].add(i); q[i].push(a[i]); q[0].push(a[i]); } int m=gi(); while(m--){ scanf("%s",s); if(s[0]=='U'){ int x=gf(gi()),y=gf(gi()); if(x==y)continue; if(q[x].size()>q[y].size())swap(x,y); q[0].kill(q[x].top()+k[x]); q[0].kill(q[y].top()+k[y]); q[y].join(q[x],k[x]-k[y]); q[0].push(q[y].top()+k[y]); f[x]=y; }else if(s[0]=='A'){ if(s[1]=='1'){ int x=gi(),g=gf(x); q[0].kill(q[g].top()+k[g]); q[g].kill(a[x]); a[x]+=gi(); q[g].push(a[x]); q[0].push(q[g].top()+k[g]); }else if(s[1]=='2'){ int x=gf(gi()); q[0].kill(q[x].top()+k[x]); k[x]+=gi(); q[0].push(q[x].top()+k[x]); }else k[0]+=gi(); }else{ if(s[1]=='1'){ int x=gi(); printf("%d\n",a[x]+k[gf(x)]+k[0]); }else if(s[1]=='2'){ int x=gf(gi()); printf("%d\n",q[x].top()+k[x]+k[0]); }else printf("%d\n",q[0].top()+k[0]); } } return 0; } |