题解 P5163 【WD与地图】
青君
2020-09-12 17:10:04
## 简要题意
给定一个 $n$ 个点 $m$ 条边的有向简单图，点带权，你要实现 $q$ 个操作，操作包括：1）删除一条边；2）单点加；3）询问一个点所在的 DCC 内 前 $k$ 大的点权的和。
$n \le 10^5,m,q\le 2*10^5$ 任意时刻点权不超过 $10^9$。
## 题目分析
首先时光倒流，删边变加边，但动态维护 DCC 依然是不太可做的。考虑换个思路，先约定：
1. 时间轴为 $[0,q+1]$ ，左小右大。
2. 一条边的**出现时间**为它原来的删除时间。如果没有被删除则为 $q+1$。
3. 一条边的**合并时间**为其连接两个顶点合并为一个 DCC 的时间，显然，任意一条边的合并时间小于等于它的出现时间。如果始终没有合并则为 $0$。
如果我们能求出每条边的合并时间，然后按这个**合并时间**从大到小依次合并，就跟动态维护连通块一样做了。至于2)和3）操作，动态开点权值线段树+启发式合并可以轻松解决。现在问题转化为，**求出每条边的合并时间**。考虑用整体二分解决。
## 算法设计——整体二分
定义 $solve(l,r,ll,rr)$ 表示，答案区间为 $[l,r]$ ，当前要求出编号属于 $[ll,rr]$ 的边的合并时间。同时需要保证，已知加入出现时间在 $[r+1,q+1]$ 内的边后图的联通信息，（也就是哪些点属于一个 DCC），这个信息用并查集存储。令 $mid = (l+r)/2$，我们试图把编号在 $[ll,rr]$ 内的边按照合并时间是否**大于** $mid$ 划成两部分，然后可以向两边分治。
算法流程：
1. 如果 $l=r$ ，则 $[ll,rr]$ 内边的合并时间就是 $l$ ，直接 `return`。
2. $mid \gets (l+r)/2$，加入编号在 $[ll,rr]$ 内且出现时间大于 $mid$ 的边。假设要加入一条边 $e(x,y)$， `link(find(x),find(y))` 也就是连接 $x,y$ 所在 DCC 的代表点。
3. 在 **2.** 中建出的图中跑 `tarjan` ，并用并查集合并新的 DCC。注意，只能跑在 **2.** 中连了边的点，否则复杂度是错的。
4. **完全清除** **2.** 中连的边。
5. 遍历 $[ll,rr]$ 内的边，如果一条边的 出现时间大于 $mid$（容易忽略）且两端在同一个 DCC 内，则划分到右边；否则划分到左边。令 $[ll,p]$ 为划分到左边的边。
6. 因为我们还未执行 **7.** ，满足「已知加入出现时间在 $[mid+1,q+1]$ 内的边后图的联通信息」的要求， `solve(l,mid,ll,p)`。
7. 撤销在第二步中执行的并查集操作。
8. `solve(mid+1,r,p+1,rr)`。
这里面有个明显的细节问题（雾）：为什么我们可以把边全部拆了（执行 **4.** ），只保留并查集中的信息，就 `solve(l,mid,ll,p)`？万一这些边对左边有用咋办？
仔细分析发现，这是不可能的。我们加入的边无非有两种命运：
1)被划分到左边，那么问题就不是问题了，反正分治左边时它还能再加进去。
2)被划分到右边，说明它的两端在同一个 DCC 内，而我们已经保留了并查集的信息，也不会信息丢失。
~~好像很不足道的样子。~~
## 代码
代码应该不丑但是有yi点长。~~建议不要看。~~
```cpp
#include<bits/stdc++.h>
#define mk make_pair
#define pk push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
const int N=1e5+5,M=2e5+5;
struct opt{
int op,x,y,t;
opt(int op=0,int x=0,int y=0,int t=0):op(op),x(x),y(y),t(t){}
bool operator < (const opt &tmp)const{return t==tmp.t?op<tmp.op:t>tmp.t;}
}b[M<<1];
struct edge{
int x,y,t,nt;
edge(int x=0,int y=0,int t=0):x(x),y(y),t(t){}
}e[M];
int n,m,q;
namespace prework{
edge t[M<<1];
int idx,dfn[N],low[N],fa[N],sz[N],in[N];
vector<int> to[N];
int find(int x){return x==fa[x]?x:find(fa[x]);}
void merge(int x,int y,stack<pi> &st){
x=find(x),y=find(y);
if(x==y) return ;
if(sz[x]<sz[y]) swap(x,y);
sz[x]+=sz[y];fa[y]=x;st.push(mk(x,y));
}
void tarjan(int x,stack<pi> &st2){
static stack<int> st;
dfn[x]=low[x]=++idx;st.push(x);in[x]=1;
for(auto y:to[x])if(!dfn[y]) tarjan(y,st2),low[x]=min(low[x],low[y]);
else if(in[y]) low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x]){
while(st.top()^x){
merge(st.top(),x,st2);
in[st.top()]=0;
st.pop();
}
in[st.top()]=0;
st.pop();
}
}
void solve(int l,int r,int ll,int rr){
if(l==r){
for(int i=ll;i<=rr;++i) e[i].nt=l;
return ;
}
int mid=(l+r)>>1;
vector<int> nd;
for(int i=ll;i<=rr;++i)if(e[i].t>mid){
int fx=find(e[i].x),fy=find(e[i].y);
to[fx].pk(fy);
nd.pk(fx),nd.pk(fy);
}
stack<pi> st;
for(auto x:nd)if(!dfn[x]) tarjan(x,st);
idx=0;
for(auto x:nd) to[x].clear(),dfn[x]=0;
int p1=ll,p2=rr;
for(int i=ll;i<=rr;++i)
if(e[i].t>mid&&find(e[i].x)==find(e[i].y)) t[p2--]=e[i];
else t[p1++]=e[i];
for(int i=ll;i<=rr;++i) e[i]=t[i];
solve(l,mid,ll,p1-1);
while(st.size()){
int x=st.top().first,y=st.top().second;
sz[x]-=sz[y];fa[y]=y;
st.pop();
}
solve(mid+1,r,p2+1,rr);
}
}
namespace seg{
#define tl ls[id]
#define tr rs[id]
#define mid (l+r>>1)
#define lson tl,l,mid
#define rson tr,mid+1,r
const int M=400,D=1e9;
int tot,a[N],fa[N],sz[N],rt[N],ls[N*M],rs[N*M],sz2[N*M];LL s[N*M];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void insert(int &id,int l,int r,int p,int fg){
if(!id) id=++tot;
s[id]+=p*fg;sz2[id]+=fg;
if(l==r) return ;
p<=mid?insert(lson,p,fg):insert(rson,p,fg);
}
int merge(int x,int y){
if(!x||!y) return x|y;
s[x]+=s[y];sz2[x]+=sz2[y];
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
return x;
}
LL query(int id,int l,int r,int k){
if(!id) return 0;
if(l==r) return 1ll*k*l;
return k<=sz2[tr]?query(rson,k):s[tr]+query(lson,k-sz2[tr]);
}
void solve(int tot){
sort(&b[1],&b[tot+1]);
for(int i=1;i<=n;++i){
fa[i]=i;sz[i]=1;
insert(rt[i],0,D,a[i],1);
}
stack<LL> ans;
for(int i=1;i<=tot;++i){
int &op=b[i].op,&x=b[i].x,&y=b[i].y,fx=find(x);
if(op==1){
int fy=find(y);
if(fx==fy) continue;
if(sz[fx]<sz[fy]) swap(fx,fy),swap(x,y);
sz[fx]+=sz[fy];fa[fy]=fx;rt[fx]=merge(rt[fx],rt[fy]);
}
else if(op==2) insert(rt[fx],0,D,a[x],-1),insert(rt[fx],0,D,a[x]-=y,1);
else{
ans.push(query(rt[fx],0,D,y));
}
}
while(ans.size()) cout<<ans.top()<<endl,ans.pop();
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;++i) cin>>seg::a[i];
map<pi,int> mp;
for(int i=1,x,y;i<=m;++i){
cin>>x>>y;e[mp[mk(x,y)]=i]=(edge){x,y,q+1};
}
int tot=0;
for(int i=1,op,a,b;i<=q;++i){
cin>>op>>a>>b;
if(op==1) e[mp[mk(a,b)]].t=i;
else if(op==2) seg::a[a]+=b,::b[++tot]=opt(2,a,b,i);
else ::b[++tot]=opt(3,a,b,i);
}
for(int i=1;i<=n;++i) prework::fa[i]=i,prework::sz[i]=1;
prework::solve(0,q+1,1,m);
for(int i=1;i<=m;++i) b[++tot]=opt(1,e[i].x,e[i].y,e[i].nt);
seg::solve(tot);
return 0;
}
```