有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); } }}新闻热点
疑难解答
