有N個節點，標號從1到N，這N個節點一開始相互不連通。第i個節點的初始權值為a[i]，接下來有如下一些操作： U x y: 加一條邊，連接第x個節點和第y個節點 A1 x v: 將第x個節點的權值增加v A2 x v: 將第x個節點所在的連通塊的所有節點的權值都增加v A3 v: 將所有節點的權值都增加v F1 x: 輸出第x個節點當前的權值 F2 x: 輸出第x個節點所在的連通塊中，權值最大的節點的權值 F3: 輸出所有節點中，權值最大的節點的權值
每個點維護一個可并堆，U的操作就是合并x,y所處的堆；A1,A2堆上操作，A3開個全局變量記錄；F1,F2堆上操作，F3的話用優先隊列記錄每個堆頂元素大小就可以了（注意是每個堆頂元素，維護的可并堆是大根堆，所以這樣記錄正確性是可以保證的）。
不是第一次寫可并堆了，個人偏愛寫左偏樹（其他的不會啊2333），不過這是我用Emacs碼的第一個代碼，調了一個晚上和一個上午。
…還是很有紀念價值2333
#include <cstdio>#include <queue>#include <algorithm>#include <iostream>#define N 300010using namespace std;int n,m,tot,x,v,tp,i;int w[N],sta[N];char op[5];struct node{ int f,l,r,d,flg,w;}T[N<<1];PRiority_queue<int> Q,del;inline int Getr(int x){ while(T[x].f) x=T[x].f; return x;}inline void swap(int &x,int &y){ int z=x;x=y;y=z;}inline void Erase(int x){ while(del.size()&&del.top()==Q.top()) del.pop(),Q.pop(); del.push(x);}inline void Insert(int x){ while(del.size()&&del.top()==Q.top()) del.pop(),Q.pop(); Q.push(x);}inline int Top(){ while(del.size()&&del.top()==Q.top()) del.pop(),Q.pop(); return Q.top();}inline void mark(int x,int y){ T[x].w+=y; T[x].flg+=y;}inline void pushdown(int x){ if(T[x].flg==0) return; if(T[x].l) mark(T[x].l,T[x].flg); if(T[x].r) mark(T[x].r,T[x].flg); T[x].flg=0;}inline void fixtop(int x){ sta[tp=1]=x; for(int i=x;T[i].f;i=T[i].f)sta[++tp]=T[i].f; for(;tp;--tp)pushdown(sta[tp]);}int merge(int x,int y,int f){ if(x==0||y==0){T[x+y].f=f;return x+y;} pushdown(x); pushdown(y); if(T[x].w<T[y].w)swap(x,y); T[x].r=merge(T[x].r,y,x); if(T[T[x].l].d<T[T[x].r].d) swap(T[x].l,T[x].r); if(T[x].r)T[x].d=T[T[x].r].d+1; else T[x].d=0; T[x].f=f; return x;}inline int query(int x){ fixtop(x); return T[x].w;}inline int qmx(int x){ fixtop(x); return T[Getr(x)].w;}inline void Fix(int x){ fixtop(x); int R=Getr(x); if(R==x) { int k=merge(T[x].l,T[x].r,x); T[x].l=T[x].r=0; Insert(T[merge(x,k,0)].w); return; } if(x==T[T[x].f].l) T[T[x].f].l=merge(T[x].l,T[x].r,T[x].f); else T[T[x].f].r=merge(T[x].l,T[x].r,T[x].f); T[x].l=T[x].r=0; Insert(T[merge(x,R,0)].w);}inline int max(const int &a,const int &b){ return a<b?b:a;}inline void reaD(int &x){ char Ch=getchar();x=0;int f=1; for(;Ch>'9'||Ch<'0';Ch=getchar())if(Ch=='-')f=-1; for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());x*=f;}inline void reaD(char *x){ char Ch=getchar();int len=0; for(;!((Ch>='A'&&Ch<='Z')||(Ch>='0'&&Ch<='9'));Ch=getchar()); for(;(Ch>='A'&&Ch<='Z')||(Ch>='0'&&Ch<='9');x[len++]=Ch,Ch=getchar());}int main(){ reaD(n); for(i=1;i<=n;i++) reaD(T[i].w),Q.push(T[i].w); reaD(m); for(i=1;i<=m;i++){ reaD(op); if(op[0]=='A'){ if(op[1]=='1'){ reaD(x);reaD(v); Erase(T[Getr(x)].w); T[x].w+=v; Fix(x); } else if(op[1]=='2'){ reaD(x),reaD(v); int k=Getr(x); Erase(T[k].w); Insert(T[k].w+v); mark(k,v); } else reaD(v),tot+=v; } else if(op[0]=='U'){ reaD(x);reaD(v); int a=Getr(x),b=Getr(v); if(a==b) continue; Erase(T[a].w);Erase(T[b].w); Insert(T[merge(a,b,0)].w); } else{ if(op[1]=='1') reaD(x),printf("%d/n",query(x)+tot); else if(op[1]=='2') reaD(x),printf("%d/n",tot+qmx(x)); else printf("%d/n",Top()+tot); } }}新聞熱點
疑難解答
