细节要人命.jpg

这题思路太新奇了……首先不难发现可以倒着做变成加边，但是它还需要我们资瓷加边的同时维护强连通分量。显然加边之后暴力跑是不行的

然后有一个想法，对于一条边\((u,v)\)，如果所有加入时间在\((0,t)\)之间的边能够使\(u,v\)在同一个强连通分量里，那么\((u,v)\)这条边的成立时间就是最小的满足条件的\(t\)。

对于每一个强联通分量维护一棵权值线段树，修改的话就是一个权值出现次数\(+1\)，另一个\(-1\)，找前\(k\)大的总和可以类似于主席树的那种二分，强联通分量的合并可以线段树合并。

于是就可以枚举时间\(t\)，对于每一条成立时间为\(t\)的边\((u,v)\)，我们用并查集把它们连起来，再把他们对应的强连通分量的权值线段树合并起来，这样就查询和修改就直接在权值线段树上进行即可

现在的问题是如何求出每条边的成立时间。这个可以整体二分。每次二分一个\(mid\)，把所有加入时间小于等于\(mid\)的边加入图中跑一遍\(tarjan\)，就可以知道哪些边的成立时间小于等于\(mid\)，然后继续二分下去就好了。然后可以用一个什么东西来维护当前并查集的情况，这样左边做完之后就不用再做一次，可以直接进右边做了

注意细节

//minamoto#include
    
     #define R register#define ll long long#define pi pair
     
      #define IT vector
      
       ::iterator#define fp(i,a,b) for(R int i=a,I=b+1;i
       
        I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)#define gg(mp) for(IT it=mp.begin();it!=mp.end();++it)template
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}template
         
          inline bool cmax(T&a,const T&b){return a
          
           '9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e6+5;struct eg{int v,nx;}e[N];int head[N],tot;struct node{int u,v,t;}a[N],b[N];vector
           
            path[N];struct point{int ls,rs,s;ll sum;}t[N<<5];ll ans[N];set
            
             s;int fa[N],rt[N],low[N],dfn[N],st[N],ins[N],q[N],type[N],aa[N],bb[N],val[N];int n,m,tim,qaq,top,cnt,h,u,v,lim;int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}void unite(R int x,R int y){ x=find(x),y=find(y);if(x==y)return; fa[x]=y;}void tarjan(int u){ dfn[u]=low[u]=++tim,st[++top]=u,ins[u]=1; go(u)if(!dfn[v])tarjan(v),cmin(low[u],low[v]); else if(ins[v])cmin(low[u],dfn[v]); if(low[u]==dfn[u])do{ins[st[top]]=0,unite(st[top],u);}while(st[top--]!=u);}void update(int &p,int l,int r,int k,int x){// printf("%d %d\n",l,r); if(!p)p=++cnt;t[p].s+=k,t[p].sum+=x*k;if(l==r)return; int mid=(l+r)>>1; x<=mid?update(t[p].ls,l,mid,k,x):update(t[p].rs,mid+1,r,k,x);}ll query(int p,int l,int r,int k){ if(k>=t[p].s)return t[p].sum; if(l==r)return t[p].sum/t[p].s*k; int mid=(l+r)>>1; if(t[t[p].rs].s>=k)return query(t[p].rs,mid+1,r,k); return query(t[p].ls,l,mid,k-t[t[p].rs].s)+t[t[p].rs].sum;}int merge(int x,int y){ if(!x||!y)return x|y; t[x].s+=t[y].s,t[x].sum+=t[y].sum; t[x].ls=merge(t[x].ls,t[y].ls); t[x].rs=merge(t[x].rs,t[y].rs); return x;}void solve(int l,int r,int ql,int qr){// printf("%d %d %d %d\n",l,r,ql,qr); if(l==r){ fp(i,ql,qr)path[l].push_back(a[i]); return; }if(ql==qr){ if(find(a[ql].u)==find(a[ql].v)) path[a[ql].t].push_back(a[ql]); return; }int mid=(l+r)>>1;tot=h=0; fp(i,ql,qr)if(a[i].t<=mid){ int u=find(a[i].u),v=find(a[i].v); q[++h]=u,q[++h]=v,head[u]=head[v]=0; }for(R int i=1;i<=h;i+=2){ int u=q[i],v=q[i+1]; e[++tot]={v,head[u]},head[u]=tot; dfn[u]=low[u]=ins[u]=0; dfn[v]=low[v]=ins[v]=0; }top=tim=0; fp(i,1,h)if(!dfn[q[i]])tarjan(q[i]); vector
             
              mp;int t1=0,t2=ql; h=1; fp(i,ql,qr){ int flag=0; if(a[i].t<=mid){ int u=q[h],v=q[h+1];h+=2; if(find(u)==find(v))flag=1; mp.push_back(pi(u,fa[u])); mp.push_back(pi(v,fa[v])); }if(flag)a[t2++]=a[i]; else b[++t1]=a[i]; }fp(i,t2,qr)a[i]=b[i-t2+1]; fp(i,1,h-1)fa[q[i]]=q[i];// printf("%d %d\n",t1,t2); if(ql
              
               first]=it->second; if(qr>=t2)solve(mid+1,r,t2,qr);}int main(){// freopen("testdata.in","r",stdin);// freopen("testdata.out","w",stdout); n=read(),m=read(),qaq=read(); fp(i,1,n)val[i]=read(),fa[i]=i; fp(i,1,m)u=read(),v=read(),s.insert(pi(u,v)); fd(i,qaq,1){ int op=read(),u=read(),v=read(); type[i]=op,aa[i]=u,bb[i]=v; if(op==1)a[++tot]={u,v,i},s.erase(pi(u,v)); else if(op==2)val[u]+=v; }for(set
               
                ::iterator it=s.begin();it!=s.end();++it)a[++tot]={it->first,it->second,0}; solve(0,qaq+1,1,m); tot=top=0,type[0]=1; fp(i,1,n)cmax(lim,val[i]),fa[i]=i; fp(i,1,n)update(rt[i],1,lim,1,val[i]);// puts("QAQ"); fp(i,0,qaq)if(type[i]==1){ for(vector
                
                 ::iterator it=path[i].begin();it!=path[i].end();++it){ it->u=find(it->u),it->v=find(it->v); if(it->u==it->v)continue; fa[it->v]=it->u; rt[it->u]=merge(rt[it->u],rt[it->v]); } }else if(type[i]==2){ int u=find(aa[i]);update(rt[u],1,lim,-1,val[aa[i]]); val[aa[i]]-=bb[i];update(rt[u],1,lim,1,val[aa[i]]); }else ans[++top]=query(rt[find(aa[i])],1,lim,bb[i]); while(top)print(ans[top--]); return Ot(),0;}