题解 P5163 【WD与地图】

· · 题解

整体二分神题，搞了半天，只能说出题人太强了。

题意

给定一张n个点m条边的有向图，每个点有一个点权，要求支持以下操作：

  1. 删掉一条之前存在的边。
  2. 更改一个点的点权。
  3. 询问某个点所在强连通分量内部前k大的点权之和。如果不足k个点，则输出全部点权之和。

题解

首先，套路性地反转时间轴，转化为加边。接下来的问题就是如何维护强连通分量。
如果我们能求出在什么时候，一条边所连接的两个点处于同一个强连通分量中，那么将所有边按这一时间点排序，从小往大遍历，将每条边的两个端点所在的强连通分量合并，这样就可以维护每个点所在的强连通分量了。这一过程，我们用并查集来维护每个点所在的强连通分量。
为了处理询问，我们可以同时对每个强连通分量维护一棵权值线段树，保存分量内部的所有点权，每次加边时，我们将两棵线段树合并，就可以处理询问了。而对于修改，我们只需要改动一棵线段树上的一个位置，同样不是问题。

那么，怎么求出每条边两端被合并到同一个强连通分量中的时间呢？
先考虑一条边的情况，我们尝试二分答案。
设当前答案为x，我们把出现时间\le x的边全部加入一张图，对这张图跑tarjan，判断两端是否在同一强连通分量内部即可。
尝试改写成整体二分的形式。设当前答案的区间为[l,r]，mid=\frac{l+r}{2}，在这个答案区间内的边为[a,b]，我们将出现时间在[0,l-1]之间的所有边加入，然后遍历[a,b]间的所有边，将[a,b]中出现时间\le mid的边全部加入，在这张图上就有了所有出现时间\le mid的边。跑一遍tarjan即可。
但是我们无法支持每次都加入出现时间在[0,mid]之间的边，考虑利用上一层递归的结果。我们用可撤销并查集来维护当前区间tarjan缩点的结果，每次在上一层已经缩了一部分点的“虚图”上加边，在tarjan的过程中将同一分量内部的点在并查集上合并。每次处理完区间[l,r]之后，我们直接递归求解[mid+1,r]，等到处理完右半边之后再撤销当前区间的操作，然后再递归处理左半边的[l,mid]。由于tarjan的复杂度是O(m)的，每条边最多只会被处理\log n次，这样，我们就能保证复杂度是正确的。

总结一下，将时间轴取反，运用整体二分求出每条边两端被合并到同一强连通分量中的时间。对每条边求出这个值，从小到大排序，依次合并一条边两端的强连通分量和相应的权值线段树，在过程中顺便处理询问和修改，我们就做完了这道神仙题。
主要的复杂度瓶颈在整体二分上，是O(m\log^2n)的，线段树合并和排序都是O(m\log n)，可以接受。

代码

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
typedef pair<int,int>pii;
const int MN=1e5+5;
const int MM=2e5+5;
//边表 
int to[MM],nxt[MM],h[MN],cnt;
inline void ins(int s,int t){to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;}
//一些变量的声明 
int n,m,q,a[MN];
map<pii,int>mp;
int opt[MM],A[MM],B[MM];
ll Ans[MM];
int N,M,b[MN*3],aa[MN];
struct data{int opt,s,t,tim;}d[MM*2];
inline int getid(int x){return lower_bound(b+1,b+1+N,x)-b;}
//权值线段树 
int tot,rt[MN],ls[MN*60],rs[MN*60],siz[MN*60];
ll sum[MN*60];
#define mid (l+r>>1)
void update(int& t,int l,int r,int pos,int v){
    if(!t)t=++tot;siz[t]+=v;sum[t]+=v*b[pos];
    if(l==r)return;
    if(pos<=mid)update(ls[t],l,mid,pos,v);
    else update(rs[t],mid+1,r,pos,v);
}
int merge(int rt1,int rt2,int l,int r){
    if(!rt1||!rt2)return rt1+rt2;
    if(l==r){siz[rt1]+=siz[rt2];sum[rt1]+=sum[rt2];return rt1;}
    ls[rt1]=merge(ls[rt1],ls[rt2],l,mid);
    rs[rt1]=merge(rs[rt1],rs[rt2],mid+1,r);
    siz[rt1]=siz[ls[rt1]]+siz[rs[rt1]];
    sum[rt1]=sum[ls[rt1]]+sum[rs[rt1]];
    return rt1;
}
ll query(int t,int l,int r,int k){
    if(l==r)return 1ll*k*b[l];
    if(k<=siz[rs[t]])return query(rs[t],mid+1,r,k);
    return sum[rs[t]]+query(ls[t],l,mid,k-siz[rs[t]]);
}
//按秩合并的并查集，用于tarjan和线段树合并 
int par[MN],rnk[MN];
int find(int x){return par[x]==x?x:find(par[x]);}
int stkx[MM],stky[MM],top;
inline void merge(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(rnk[x]<rnk[y])swap(x,y);
    par[y]=x;stky[++top]=y;
    if(rnk[x]==rnk[y])rnk[x]++,stkx[top]=x;
}
inline void Merge(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(rnk[x]<rnk[y])swap(x,y);
    par[y]=x;
    if(rnk[x]==rnk[y])rnk[x]++;
    rt[x]=merge(rt[x],rt[y],1,N);
}
//tarjan
int dfn[MN],low[MN],stk[MN],Top,idx;
bool vis[MN];
void tarjan(int st){
    dfn[st]=low[st]=++idx;
    vis[stk[++Top]=st]=true;
    for(reg int i=h[st];i;i=nxt[i]){
        if(!dfn[to[i]])tarjan(to[i]),low[st]=min(low[st],low[to[i]]);
        else if(vis[to[i]])low[st]=min(low[st],dfn[to[i]]);
    }
    if(dfn[st]==low[st]){
        reg int loc=stk[Top--];
        vis[loc]=false;
        while(stk[Top+1]!=st){
            vis[stk[Top]]=false;
            merge(loc,stk[Top--]);
        }
    }
}
//整体二分 
int node[MM*2];
struct edge{int s,t,tim;}es[MM],t1[MM],t2[MM];
void solve(int l,int r,int a,int b){
    if(a>b)return;
    if(l==r){
        for(reg int i=a;i<=b;i++)es[i].tim=l;
        return;
    }
    reg int ncnt=0,ttop=top;
    for(reg int i=a,s,t;i<=b;i++)
        if(es[i].tim<=mid){
            s=find(es[i].s);t=find(es[i].t);
            node[++ncnt]=s;node[++ncnt]=t;
            ins(s,t);
        }
    for(reg int i=1;i<=ncnt;i++)
        if(!dfn[node[i]])tarjan(node[i]);
    reg int cnt1=0,cnt2=0;
    for(reg int i=a;i<=b;i++){
        //注意一下，这里应该要同时满足两个条件，即这条边已经出现，且两端在同一强连通分量中 
        if(find(es[i].s)==find(es[i].t)&&es[i].tim<=mid)t1[++cnt1]=es[i];
        else t2[++cnt2]=es[i];
    }
    for(reg int i=1;i<=cnt1;i++)es[a+i-1]=t1[i];
    for(reg int i=1;i<=cnt2;i++)es[a+cnt1+i-1]=t2[i];
    cnt=idx=0;
    for(reg int i=1;i<=ncnt;i++)
        h[node[i]]=dfn[node[i]]=low[node[i]]=0;
    solve(mid+1,r,a+cnt1,b);
    while(top!=ttop){
        par[stky[top]]=stky[top];
        if(stkx[top])rnk[stkx[top]]--;
        top--;
    }
    solve(l,mid,a,a+cnt1-1);
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(reg int i=1;i<=n;i++)scanf("%d",a+i),b[++N]=aa[i]=a[i];
    for(reg int i=1;i<=n;i++)par[i]=i,rnk[i]=1;
    for(reg int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        es[i]=(edge){x,y,0};
        mp[make_pair(x,y)]=i;
    }
    for(reg int i=1,id;i<=q;i++){
        scanf("%d%d%d",opt+i,A+i,B+i);
        if(opt[i]==1)es[mp[make_pair(A[i],B[i])]].tim=q-i+1;
        if(opt[i]==2)b[++N]=aa[A[i]]+B[i],aa[A[i]]+=B[i];
    }
    solve(0,q+1,1,m);
    for(reg int i=1;i<=m;i++)
        d[++M]=(data){1,es[i].s,es[i].t,es[i].tim};
    for(reg int i=1;i<=q;i++)
        if(opt[i]>1)d[++M]=(data){opt[i],A[i],B[i],q-i+1};
    sort(d+1,d+1+M,[](data a,data b){
        return a.tim==b.tim?a.opt<b.opt:a.tim<b.tim;
    });
    sort(b+1,b+1+N);N=unique(b+1,b+1+N)-b-1;
    for(reg int i=1;i<=n;i++)
        update(rt[i],1,N,getid(aa[i]),1),par[i]=i;
    for(reg int i=1;i<=n;i++)par[i]=i,rnk[i]=1;
    memset(Ans,-1,sizeof(Ans));
    for(reg int i=1,x,y;i<=M;i++){
        if(d[i].opt==1){
            Merge(d[i].s,d[i].t);
        }
        if(d[i].opt==2){
            y=find(x=d[i].s);
            update(rt[y],1,N,getid(aa[x]),-1);
            aa[x]-=d[i].t;
            update(rt[y],1,N,getid(aa[x]),1);
        }
        if(d[i].opt==3){
            x=find(d[i].s);
            Ans[q-d[i].tim+1]=query(rt[x],1,N,min(d[i].t,siz[rt[x]]));
        }
    }
    for(reg int i=1;i<=q;i++)
        if(~Ans[i])printf("%lld\n",Ans[i]);
    return 0;
}