正题

题目链接:https://www.luogu.com.cn/problem/P5163

---

给出\(n\)个点\(m\)条有向边，点有权值，要求支持操作

1. 删除一条边
2. 修改一个点的权值
3. 求一个点所在强连通分量中前\(k\)大权值和

\(1\leq n\leq 10^5,1\leq m,q\leq 2\times 10^5\)

---

首先删边肯定是时光倒流改成加边，然后考虑怎么继续做。

我们需要处理一些点集什么时候合并，这样的合并其实不会超过\(n-1\)次。

而且每次肯定是合并某条边\((x,y)\)两个点所在的强连通分量，但是每次加入的一条边\((x,y)\)不一定会即使生效。

我们可以考虑对于每条边求出它在后来加入哪条边加入之后生效了，这个可以考虑整体二分，我们每次把所有询问的边集在\([0,mid]\)区间的边加入然后跑\(tarjan\)，把跑出来的强连通分量缩成一个点然后继续丢到右边跑，跑完右边的子区间之后再撤销这次\(tarjan\)缩起来的点然后跑左边。

这样一定是对的因为如果一条答案不在这个区间的边生效，那么它要不就在之前被合并了要么在这个区间内都合并不了，所以没有作用。

这个要用一个可撤销并查集，记得安秩合并就好了。

之后我们就有一个操作变成合并两个集合了，线段树合并做剩下的部分就行了

时间复杂度\(O(n\log^2 n)\)（反正差不多同级就不写这么详细了）

---

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=8e5+10;
struct node{
    ll to,next;
}a[N];
struct enode{
    ll x,y,t,T;
}e[N],p1[N],p2[N];
struct qnode{
    ll x,k;
}q[N];
struct snode{
    ll x,y,fa,dep;
}st[N];
ll n,m,t,tot,snt,clt,cnt,s[N];
ll ls[N],fa[N],dep[N],cl[N];
ll dfn[N],low[N],rt[N],ans[N];
bool ins[N];stack<ll> S;
map<pair<ll,ll> ,ll> emp;
void addl(ll x,ll y){
    a[++tot].to=y;
    a[tot].next=ls[x];
    ls[x]=tot;return;
}
ll find(ll x)
{return (fa[x]==x)?x:find(fa[x]);}
ll Find(ll x)
{return (fa[x]==x)?x:(fa[x]=Find(fa[x]));}
void unionn(ll x,ll y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(dep[x]>dep[y])swap(x,y);
    st[++snt]=(snode){x,y,fa[x],dep[y]};
    fa[x]=y;dep[y]=max(dep[y],dep[x]+1);
}
void clearto(ll z){
    while(snt>z){
        dep[st[snt].y]=st[snt].dep;
        fa[st[snt].x]=st[snt].fa;
        snt--;
    }
    return;
}
void tarjan(ll x){
    dfn[x]=low[x]=++cnt;
    S.push(x);ins[x]=1;
    for(ll i=ls[x];i;i=a[i].next){
        ll y=a[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        while(S.top()!=x){
            unionn(S.top(),x);
            ins[S.top()]=0;S.pop();
        }
        ins[x]=0;S.pop();
    }
    return;
}
void solve(ll l,ll r,ll L,ll R){
    if(L>R)return;
    if(l==r){
        for(ll i=L;i<=R;i++)
            e[i].T=l;
        return;
    }
    ll mid=(l+r)>>1,zt=snt;
    for(ll i=L;i<=R;i++)
        if(e[i].t<=mid){
            ll x=find(e[i].x),y=find(e[i].y);
            addl(x,y);cl[++clt]=x;cl[++clt]=y;
        }
    cnt=tot=0;
    for(ll i=1;i<=clt;i++)
        if(!dfn[cl[i]])tarjan(cl[i]);
    ll t1=0,t2=0;
    for(ll i=L;i<=R;i++){
        ll x=find(e[i].x),y=find(e[i].y);
        if(x==y)p1[++t1]=e[i];else p2[++t2]=e[i];
    }
    for(ll i=1;i<=t1;i++)e[L+i-1]=p1[i];
    for(ll i=1;i<=t2;i++)e[L+t1+i-1]=p2[i];
    while(clt)ls[cl[clt]]=dfn[cl[clt]]=low[cl[clt]]=0,clt--;
    solve(mid+1,r,L+t1,R);clearto(zt);
    solve(l,mid,L,L+t1-1);
    return;
}
bool cmp(enode x,enode y)
{return x.t<y.t;}
struct SegTree{
    ll cnt,w[N<<5],s[N<<5],ls[N<<5],rs[N<<5];
    void Change(ll &x,ll L,ll R,ll pos,ll val){
        if(!x)x=++cnt;w[x]+=val;s[x]+=pos*val;
        if(L==R)return;
        ll mid=(L+R)>>1;
        if(pos<=mid)Change(ls[x],L,mid,pos,val);
        else Change(rs[x],mid+1,R,pos,val);
        return;
    }
    ll Ask(ll x,ll L,ll R,ll k){
        if(k>=w[x])return s[x];
        if(L==R)return L*k;
        ll mid=(L+R)>>1;
        if(w[rs[x]]>=k)return Ask(rs[x],mid+1,R,k);
        return s[rs[x]]+Ask(ls[x],L,mid,k-w[rs[x]]);
    }
    ll Merge(ll x,ll y){
        if(!x||!y)return x+y;
        w[x]=w[x]+w[y];s[x]=s[x]+s[y];
        ls[x]=Merge(ls[x],ls[y]);
        rs[x]=Merge(rs[x],rs[y]);
        return x;
    }
//    ll Merge(ll x,ll y,ll L,ll R){
//        if(!x||!y)return x+y;
//        w[x]=w[x]+w[y];
//        if(L==R)return x;
//        ll mid=(L+R)>>1;
//        ls[x]=Merge(ls[x],ls[y],L,mid);
//        rs[x]=Merge(rs[x],rs[y],mid+1,R);
//        return x;
//    }
}T;
void Merge(ll x,ll y){
    x=Find(x),y=Find(y);
    if(x==y)return;
    rt[x]=T.Merge(rt[x],rt[y]);
    fa[y]=x;return;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&t);
    for(ll i=1;i<=n;i++)scanf("%lld",&s[i]),fa[i]=i;
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld",&e[i].x,&e[i].y);
        emp[mp(e[i].x,e[i].y)]=i;
    }
    for(ll i=t;i>=1;i--){
        ll op,x,y;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)e[emp[mp(x,y)]].t=i;
        else if(op==2)q[i].x=-x,q[i].k=y,s[x]+=y;
        else if(op==3)q[i].x=x,q[i].k=y;
    }
    sort(e+1,e+1+m,cmp);
    solve(0,t+1,1,m);
    ll z=1;
    for(ll i=1;i<=n;i++)
        fa[i]=i,T.Change(rt[i],1,1e9,s[i],1);
    for(ll i=1;i<=t;i++){
        while(z<=m&&e[z].T<=i)
            Merge(e[z].x,e[z].y),z++;
        if(q[i].x<0){
            ll x=-q[i].x,w=q[i].k,f=Find(x);
            T.Change(rt[f],1,1e9,s[x],-1);
            s[x]-=w;
            T.Change(rt[f],1,1e9,s[x],1);
        }
        else if(q[i].x>0){
            ll x=Find(q[i].x),k=q[i].k;
            ans[i]=T.Ask(rt[x],1,1e9,k);
        }
    }
    for(ll i=t;i>=1;i--)
        if(ans[i])printf("%lld\n",ans[i]);
    return 0;
}