【LuoguP5163】WD与地图

【LuoguP5163】WD与地图

Description

有一个\(n\)个点\(m\)条边的有向图

每个点有点权\(a_i\)

维护三种操作：

1.删去\(a\)到\(b\)的边

2.\(a_i\)加上\(b\)

3.查询\(a\)所在强联通分量中前\(k\)大的点权和

Input

第一行三个数\(n,m,q\)

然后读入\(a_i\)

然后读入图

然后读入操作

Output

对于每次询问输出一行一个数表示答案

Sample Input

5 8 8
4 2 1 1 3
2 5
4 2
5 3
1 3
4 5
5 1
1 5
1 4
3 3 1
1 4 5
3 3 3
3 4 1
3 1 5
3 2 4
1 5 3
2 3 4

Sample Output

1
1
4
10
10

Data Constraint

\(1\le n\le 10^5,1\le m,q\le 2*10^5\)

Solution

典。

动态维护强联通性肯定是不可做的

所以考虑倒着做，然后整体二分出每条边所连接的两个点变为强联通的时间

具体来说，对于\([l,r,mid]\)

我们先加入\([l,mid]\)中的边跑Tarjan

然后若一条边在SCC中，那么显然放在左儿子

若其不在SCC中，因为已经加入了\([l,mid]\)的所有边，

所以往左肯定更不可能使连接的点缩起来，故往右边放

那么每次我们都对边集进行了划分，然后跑Tarjan时每条边最多做\(O(\log m)\)次

于是这部分是\(O(m\log m)\)的

最后只要按时间顺序加边，做线段树合并和单点修改，线段树二分就行了

总复杂度\(O(n\log n)\)（视同阶）

Code

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 400010
#define M 200010
#define S 15000000

LL a[N],ea[N],h[N],ans[N];
int n,m,tot,et,ta;
int dfn[N],low[N],st[N],col,scc[N],top,dt,in[N];
vector<int>e[N],p[N*4];
struct node{
	int x,y,num,t;
	node(int _x=0,int _y=0,int _num=0,int _t=0){x=_x;y=_y;num=_num;t=_t;}
};
int ls[S],rs[S],cnt[S],id;
LL sum[S];
struct tree{
	int root;
	void ul(int x){if(!ls[x])ls[x]=++id;}
	void ur(int x){if(!rs[x])rs[x]=++id;}
	int merge(int x,int y,int l,int r){
		if(!x||!y)return x|y;
		if(l==r){sum[x]+=sum[y];cnt[x]+=cnt[y];return x;}
		int mid=l+r>>1;
		ls[x]=merge(ls[x],ls[y],l,mid);
		rs[x]=merge(rs[x],rs[y],mid+1,r);
		sum[x]=sum[ls[x]]+sum[rs[x]];
		cnt[x]=cnt[ls[x]]+cnt[rs[x]];
		return x;
	}
	void change(int x,int l,int r,int pos,int v1,int v2){
		if(l==r){sum[x]+=v1;cnt[x]+=v2;return;}
		int mid=l+r>>1;
		if(pos<=mid)ul(x),change(ls[x],l,mid,pos,v1,v2);
		else ur(x),change(rs[x],mid+1,r,pos,v1,v2);
		sum[x]=sum[ls[x]]+sum[rs[x]];
		cnt[x]=cnt[ls[x]]+cnt[rs[x]];
	}
	LL query(int x,int l,int r,int k){
		if(!x)return 0;
		if(l==r)return 1ll*k*h[l];
		int mid=l+r>>1;
		if(k<=cnt[rs[x]])return query(rs[x],mid+1,r,k);
		return sum[rs[x]]+query(ls[x],l,mid,k-cnt[rs[x]]);
	}
}t[M];
vector<node>E[N*4];
node edge[N];

void Tarjan(int u){
	dfn[u]=low[u]=++dt;st[++top]=u;in[u]=1;
	for(auto v:e[u]){
		if(!dfn[v])Tarjan(v),low[u]=min(low[u],low[v]);
		else if(in[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		col++;
		while(st[top]!=u)scc[st[top]]=col,in[st[top--]]=0;
		scc[st[top]]=col;in[st[top--]]=0;
	}
}

int u[N],v[N];

struct mode{int op,x,y;}ask[N];

void solve(int x,int l,int r){
	if(l==r){
		for(auto d:E[x]){
			if(d.num<=m)
				edge[++tot]=node(u[d.num],v[d.num],0,l);
			else edge[++tot]=node(ask[d.num-m].x,ask[d.num-m].y,0,l);
		}
		return;
	}
	int mid=l+r>>1;
	for(auto d:p[x])dfn[d]=low[d]=in[d]=0,e[d].clear();
	dt=top=col=0;
	for(auto d:E[x])if(d.t<=mid)e[d.x].push_back(d.y);
	for(auto d:p[x])if(!dfn[d])Tarjan(d);
	for(auto d:E[x]){
		if(d.t<=mid){
			if(scc[d.x]==scc[d.y]){
				E[x<<1].push_back(d);
				p[x<<1].push_back(d.x);p[x<<1].push_back(d.y);
			}else{
				E[(x<<1)|1].push_back(node(scc[d.x],scc[d.y],d.num,d.t));
				p[(x<<1)|1].push_back(scc[d.x]);p[(x<<1)|1].push_back(scc[d.y]);
			}
		}else{
			E[(x<<1)|1].push_back(node(scc[d.x],scc[d.y],d.num,d.t));
			p[(x<<1)|1].push_back(scc[d.x]);p[(x<<1)|1].push_back(scc[d.y]);
		}
	}
	E[x].clear();
	p[x].clear();
	solve((x<<1)|1,mid+1,r);
	solve(x<<1,l,mid);
}

int q,fa[N];

int get(int x){return fa[x]==x?x:(fa[x]=get(fa[x]));}

unordered_map<int,int>d[N];

unordered_map<LL,int>rk;

bool cmp(node x,node y){return x.t<y.t;}

void merge(int x,int y){
	int A=get(x),B=get(y);
	if(A==B)return;
	fa[B]=A;
	t[A].root=t[A].merge(t[A].root,t[B].root,1,ta);
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	F(i,1,n)fa[i]=i;
	F(i,1,n)scanf("%lld",&a[i]),ea[++et]=a[i];
	F(i,1,n)p[1].push_back(i);
	F(i,1,m){
		int x,y;
		scanf("%d%d",&u[i],&v[i]);
	}
	F(i,1,q){
		scanf("%d%d%d",&ask[i].op,&ask[i].x,&ask[i].y);
		if(ask[i].op==1){
			d[ask[i].x][ask[i].y]=1;
			E[1].push_back(node(ask[i].x,ask[i].y,i+m,q-i+1));
		}else{
			if(ask[i].op==2)a[ask[i].x]+=ask[i].y,ea[++et]=a[ask[i].x];
		}
	}
	sort(ea+1,ea+et+1);
	F(i,1,et)if(ea[i]>h[ta])h[++ta]=ea[i],rk[ea[i]]=ta;
	F(i,1,n){
		t[i].root=++id;
		t[i].change(t[i].root,1,ta,rk[a[i]],a[i],1);
	}
	F(i,1,m)if(!d[u[i]][v[i]]){
		E[1].push_back(node(u[i],v[i],i,0));
	}
	solve(1,0,q+1);
	sort(edge+1,edge+tot+1,cmp);
	int he=0;
	F(i,0,q){
		while(edge[he+1].t<=i&&he+1<=tot){
			he++;
			merge(edge[he].x,edge[he].y);
		}
		if(!i)continue;
		int P=q-i+1;
		if(ask[P].op!=1){
			int A=get(ask[P].x);
			if(ask[P].op==2){
				t[A].change(t[A].root,1,ta,rk[a[ask[P].x]],-a[ask[P].x],-1);
				a[ask[P].x]-=ask[P].y;
				t[A].change(t[A].root,1,ta,rk[a[ask[P].x]],a[ask[P].x],1);
			}else{
				if(ask[P].y>=cnt[t[A].root])ans[P]=sum[t[A].root];
				else ans[P]=t[A].query(t[A].root,1,ta,ask[P].y);
			}
		}
	}
	F(i,1,q)if(ask[i].op==3){
		printf("%lld\n",ans[i]);
	}
	return 0;
}