RT，题目P5163。

结果

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll1;
#define int long long
int n,m,q;
struct edge{
	int u,v,nxt;
	int tm;
	bool operator <(const edge&o)const{
		return tm<o.tm;
	}
}g[N],G[N];
int tote=0;
int head[N];
void ae(int u,int v){
	g[++tote]=(edge){u,v,head[u],0};
	head[u]=tote;
}
int dfn[N],low[N],tdfn=0;
int col[N],stk[N],top=0;
void Tarjan(int u){
	dfn[u]=low[u]=++tdfn;
	stk[++top]=u;
	for(int e=head[u],v;e;e=g[e].nxt){
		v=g[e].v;
		if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);
		}else if(!col[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])while(stk[top+1]!=u)col[stk[top--]]=u;
}
void clearpoint(int x){head[x]=dfn[x]=low[x]=col[x]=0;}
edge tmpl[N],tmpr[N];
void solve(int l,int r,int lt,int rt){
	if(l==r)return;
	int mid=(l+r)>>1,u,v;
	tote=top=tdfn=0;
	for(int i=lt;i<=rt;i++){u=G[i].u,v=G[i].v;clearpoint(u);clearpoint(v);}
	for(int i=lt;i<=rt;i++){
		u=G[i].u,v=G[i].v;
		if(G[i].tm>mid)continue;
		ae(u,v);
	}
	for(int i=lt;i<=rt;i++){
		u=G[i].u,v=G[i].v;
		if(G[i].tm>mid)continue;
		if(!dfn[u])Tarjan(u);
		if(!dfn[v])Tarjan(v);
	}
	int cntl=0,cntr=0;
	for(int i=lt;i<=rt;i++){
		u=G[i].u,v=G[i].v;
		if(col[u]!=col[v]||!col[u]||!col[v]){//前mid个不行，放到右边试试
			G[i].tm=max(G[i].tm,mid+1);
			if(col[u])G[i].u=col[u];
			if(col[v])G[i].v=col[v];
			tmpr[++cntr]=G[i];
		}else{//可以在左边尝试
			tmpl[++cntl]=G[i];
		}
	}
	if(cntl)for(int i=lt,j=1; i<lt+cntl;i++,j++)G[i]=tmpl[j];
	if(cntr)for(int i=lt+cntl,j=1;i<=rt;i++,j++)G[i]=tmpr[j];
	solve(l,mid,lt,lt+cntl-1);
	solve(mid+1,r,lt+cntl,rt);
}
map<pair<int,int>,int>mp;
#define mkp make_pair
struct Query{
	int op,u,v;
	int t;
}qys[N];
int a[N];
void init(){
	int u,v,op;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		G[i]=(edge){u,v,0,1};
		mp[mkp(u,v)]=i;
	}
	for(int i=q;i>=1;i--){
		cin>>op>>u>>v;
		if(op==1)G[mp[mkp(u,v)]].tm=i;
		qys[i]=(Query){op,u,v,i};
		if(op==2)qys[i].v=-v,a[u]+=v;
	}
	sort(G+1,G+1+m);
	solve(1,q+1,1,m);
}
const int inf=1e9;
struct Node{
	int l,r;
	int cnt;
	ll1 sm;
	int lson,rson;
}sgt[N*25];
#define ls sgt[o].lson
#define rs sgt[o].rson
#define mid ((l+r)>>1)
#define lson(u) sgt[u].lson
#define rson(u) sgt[u].rson
int totn=0;
int NewNode(int l,int r){sgt[++totn]=(Node){l,r,0,0,0,0};return totn;}
void modify(int o,int p,ll1 ad){
	int l=sgt[o].l,r=sgt[o].r;
	sgt[o].cnt+=ad;sgt[o].sm+=1ll*p*ad;
	if(l==r){return;}
	if(p<=mid){
		if(!ls)ls=NewNode(l,mid);
		modify(ls,p,ad);
	}else{
		if(!rs)rs=NewNode(mid+1,r);
		modify(rs,p,ad);
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	sgt[x].cnt+=sgt[y].cnt,sgt[x].sm+=sgt[y].sm;
	lson(x)=merge(lson(x),lson(y));
	rson(x)=merge(rson(x),rson(y));
	return x;
}
int root[N],fa[N];
int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}
ll1 count(int o,int rk){
	ll1 res=0;int cntr=0,l=0,r=0;
	while(o&&rk>0){
		l=sgt[o].l,r=sgt[o].r;
		if(rk>=sgt[o].cnt){res+=sgt[o].sm;break;}
		if(l==r){res+=rk*1ll*l;break;}
		cntr=sgt[rs].cnt;
		if(rk>=cntr)res+=sgt[rs].sm,o=ls,rk-=cntr;
		else o=rs;
	}
	return res;
}
ll1 Ans[N];
void work(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		root[i]=NewNode(1,inf);
		modify(root[i],a[i],1);
	}
	sort(G+1,G+1+m);
	int e=1,u,v;
	for(int t=1;t<=q;t++){
		while(e<=m&&G[e].tm<=t){
			u=G[e].u,v=G[e].v;e++;
			u=find(u),v=find(v);
			if(u==v)continue;
			root[u]=merge(root[v],root[u]);
			fa[v]=u;
		}
		if(qys[t].op==2){
			v=qys[t].u;u=find(v);
			modify(root[u],a[v],-1);
			modify(root[u],(a[v]+=qys[t].v),1);
		}
		if(qys[t].op==3){
			u=find(qys[t].u),v=qys[t].v;
			Ans[t]=count(root[u],v);
		}
	}
	for(int i=q;i;i--)if(qys[i].op==3)printf("%lld\n",Ans[i]);
}
signed main(){
//	freopen("1.in","r",stdin);
	init();
	work();
	return 0;
}