链接
贴一下青君大佬的博客~
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
#define pi pair<int,int>
#define mk make_pair
using namespace std;
const int N=4e5+3;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
struct kk{
int op,x,y,t;
bool operator<(const kk &a) const{
return t^a.t?t>a.t:op<a.op;}
}q[N],ql[N],qr[N],l[N];
int n,m,Q,c1,c2,val[N];
map<pi,int>mp;
struct hh{
int to,nxt;
};
struct pre{
int num,cnt,fir[N],fa[N],siz[N],dfn[N],low[N],bo[N],sta[N];hh e[N];
IL void add(int x,int y){e[++num]=(hh){y,fir[x]},fir[x]=num;}
IL int find(int x){return x^fa[x]?find(fa[x]):x;}
void merge(int x,int y,stack<pi> &s){
int fx=find(x),fy=find(y);
if(fx==fy) return;
if(siz[fx]<siz[fy]) swap(fx,fy);
s.push(mk(fx,fy));
siz[fx]+=siz[fy],fa[fy]=fx;
}
void tarjan(int u,stack<pi> &s){
dfn[u]=low[u]=++cnt,sta[++sta[0]]=u,bo[u]=1;
for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
if(!dfn[v]) tarjan(v,s),low[u]=min(low[u],low[v]);
else if(bo[v]) low[u]=min(low[u],dfn[v]);
if(dfn[u]==low[u]){
while(sta[sta[0]]^u) merge(u,sta[sta[0]],s),bo[sta[sta[0]--]]=0;
bo[u]=0,--sta[0];
}
}
void solve(int L,int R,int ll,int rr){
//cout<<L<<' '<<R<<' '<<ll<<' '<<rr<<endl;
if(ll>rr) return;
if(L==R){
for(int i=ll;i<=rr;++i)
q[++c2]=(kk){1,l[i].x,l[i].y,l[i].t=L};
return;
}
int mid=L+R>>1,nl=0,nr=0;
vector<int>node;
for(int i=ll;i<=rr;++i)
if(l[i].t>mid){
int fx=find(l[i].x),fy=find(l[i].y);
add(fx,fy),node.pb(fx),node.pb(fy);
}
stack<pi>s;cnt=0;
for(int i=0;i<node.size();++i)
if(!dfn[node[i]]) tarjan(node[i],s);
num=0;for(int i=0;i<node.size();++i) fir[node[i]]=dfn[node[i]]=0;
for(int i=ll;i<=rr;++i)
if(l[i].t>mid&&find(l[i].x)==find(l[i].y)) qr[++nr]=l[i];
else ql[++nl]=l[i];
for(int i=1;i<=nl;++i) l[i+ll-1]=ql[i];
for(int i=1;i<=nr;++i) l[i+ll+nl-1]=qr[i];
solve(L,mid,ll,ll+nl-1);
while(s.size()){
siz[s.top().first]-=siz[s.top().second],
fa[s.top().second]=s.top().second,s.pop();
}
solve(mid+1,R,ll+nl,rr);
}
}T1;
struct seg{
int cnt,rt[N],fa[N],ls[N*200],rs[N*200],c[N*200];LL sum[N*200];
IL int find(int x){return x^fa[x]?fa[x]=find(fa[x]):x;}
void upd(int &o,int l,int r,int u,int op){
if(!o) o=++cnt;sum[o]+=op*u,c[o]+=op;
if(l==r) return;
int mid=l+r>>1;
if(u<=mid) upd(ls[o],l,mid,u,op);
else upd(rs[o],mid+1,r,u,op);
}
void merge(int &p1,int p2,int l,int r){
if(!p1||!p2){p1+=p2;return;}
sum[p1]+=sum[p2],c[p1]+=c[p2];
if(l==r) return;
int mid=l+r>>1;
merge(ls[p1],ls[p2],l,mid),
merge(rs[p1],rs[p2],mid+1,r);
}
LL ask(int o,int l,int r,int k){
if(!o) return 0;
if(l==r) return 1ll*l*k;
int mid=l+r>>1;
if(c[rs[o]]>=k) return ask(rs[o],mid+1,r,k);
return sum[rs[o]]+ask(ls[o],l,mid,k-c[rs[o]]);
}
void solve(int m){
stack<LL>ans;
for(int i=1;i<=n;++i) upd(rt[i],0,1e9,val[i],1),fa[i]=i;
for(int i=1;i<=m;++i)
if(q[i].op==1){
int fx=find(q[i].x),fy=find(q[i].y);
if(fx==fy) continue;
merge(rt[fx],rt[fy],0,1e9),fa[fy]=fx;
}
else if(q[i].op==2){
upd(rt[find(q[i].x)],0,1e9,val[q[i].x],-1),
upd(rt[find(q[i].x)],0,1e9,val[q[i].x]=q[i].y,1);
}
else ans.push(ask(rt[find(q[i].x)],0,1e9,q[i].y));
while(ans.size()) printf("%lld
",ans.top()),ans.pop();
}
}T2;
int main()
{
//freopen("1.in","r",stdin);
int op,x,y;
n=in(),m=in(),Q=in();
for(int i=1;i<=n;++i) val[i]=in();
for(int i=1;i<=m;++i) x=in(),y=in(),mp[mk(x,y)]=i,l[i]=(kk){0,x,y,Q+1};
for(int i=1;i<=Q;++i){
op=in(),x=in(),y=in();
if(op==1) l[mp[mk(x,y)]].t=i;
else if(op==2) q[++c2]=(kk){2,x,val[x],i},val[x]+=y;
else q[++c2]=(kk){3,x,y,i};
}
for(int i=1;i<=n;++i) T1.fa[i]=i,T1.siz[i]=1;
T1.solve(0,Q+1,1,m);
sort(q+1,q+c2+1),T2.solve(c2);
return 0;
}