[luogu 5163] WD与地图

一、题目

点此看题

二、解法

只能说是精神污染了,虽然每个部分都不难把但是放在一起就很难写了。

考虑无向图的情况是好做的,我们直接离线逆序询问,那么删边操作就变成了加边,单点增加操作就变成了单点减少。那么做法是显然的,我们线段树合并维护加边操作,再支持线段树单点修改和线段树上二分即可。

本题是强连通分量怎么办呢?我们类比无向图的情况,还是先离线逆序询问,考虑把每一条边的效果等效为合并两个强连通块。那么我们求出每一条边有用的时间 \(f\),也就是恰好在这个时刻这条边的两个端点在同一个强连通分量里

发现这个时刻是单调的,而我们要对所有边都求出这样一个时刻,那么可以考虑整体二分。考虑现在要判断一条边的 \(f\) 和 \(mid\) 的大小关系,那么我们保留加入时间在 \([0,mid]\) 的边(为 \(0\) 就表示没有被删除),如果这条边的加入时间 \(\leq mid\) 并且两端点在同一强连通分量中,那么它的 \(f\leq mid\),否则 \(f>mid\)

但是这样做时间复杂度又有点不对,我们可以考虑动态 \(\tt tarjan\),也就是假设我们已经对保留 \([0,l)\) 边的图缩过点了,那么我们再此基础上加入 \([l,mid]\) 的边就可以了。所以我们整体二分的时候先走右边再走左边,走右边的时候把新加入的边也保留,然后使用可撤销并查集就可以维护缩点的结果。

时间复杂度 \(O(n\log^2 n)\),复杂度瓶颈在可撤销并查集。

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
const int M = 200005;
const int N = 30*M;
#define ll long long
const int up = 1e9;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,t,c[M],fa[M],siz[M],top,a[M],b[M],p[M<<1];
int cnt,rt[M],ls[N],rs[N],num[N];ll ans[M],sum[N];
int Ind,low[M],dfn[M],in[M];stack<int> s;
vector<int> g[M];map<ll,int> mp;
struct node
{
	int t,x,y;
	bool operator < (const node &r) const
		{return t<r.t;}
}q[M],e[M],el[M],er[M],d[M];
//namespace : divide and conquer
int find(int x)
{
	return fa[x]==x?x:find(fa[x]);
}
void merge(int u,int v)
{
	int x=find(u),y=find(v);
	if(x==y) return ;
	if(siz[x]<siz[y]) swap(x,y);
	//guarantee that siz[x]>siz[y]
	siz[x]+=siz[y];fa[y]=x;
	top++;a[top]=x;b[top]=y;
}
void tarjan(int u)
{
	low[u]=dfn[u]=++Ind;
	s.push(u);in[u]=1;
	for(int v:g[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(low[u]==dfn[u])
	{
		int v=0;
		do
		{
			v=s.top();s.pop();
			merge(v,u);in[v]=0;
		}while(v!=u);
	}
}
void popout()
{
	int u=a[top],v=b[top--];
	siz[u]-=siz[v];fa[v]=v;
}
void cdq(int l,int r,int L,int R)
{
	if(l>r) return ;
	if(L==R)
	{
		for(int i=l;i<=r;i++)
			d[++t]=node{L,e[i].x,e[i].y};
		return ;
	}
	int mid=(L+R)>>1,tl=0,tr=0,num=0,now=top;
	//build the graph of [L,mid]
	for(int i=l;i<=r;i++)
	{
		if(e[i].t>mid) continue;
		int x=find(e[i].x),y=find(e[i].y);
		p[++num]=x;p[++num]=y;g[x].push_back(y);
	}
	//do partial tarjan
	for(int i=1;i<=num;i++)
		if(!dfn[p[i]]) tarjan(p[i]);
	//partition [l,r]
	for(int i=l;i<=r;i++)
	{
		if(e[i].t<=mid && find(e[i].x)==find(e[i].y))
			el[++tl]=e[i];
		else er[++tr]=e[i];
	}
	for(int i=1;i<=tl;i++) e[l+i-1]=el[i];
	for(int i=1;i<=tr;i++) e[l+tl+i-1]=er[i];
	//clear
	for(int i=1;i<=num;i++)
		low[p[i]]=dfn[p[i]]=0,g[p[i]].clear();
	Ind=num=0;
	//right first !!!
	cdq(l+tl,r,mid+1,R);
	while(top>now) popout();
	cdq(l,l+tl-1,L,mid);
}
//namespace : segment tree
int Find(int x)
{
	if(x!=fa[x]) fa[x]=Find(fa[x]);
	return fa[x];
}
void ins(int &x,int l,int r,int id,int f)
{
	if(!x) x=++cnt;
	sum[x]+=f*id;num[x]+=f;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(mid>=id) ins(ls[x],l,mid,id,f);
	else ins(rs[x],mid+1,r,id,f);
}
int comb(int x,int y)
{
	if(!x || !y) return x+y;
	sum[x]+=sum[y];num[x]+=num[y];
	ls[x]=comb(ls[x],ls[y]);
	rs[x]=comb(rs[x],rs[y]);
	return x;
}
ll ask(int x,int l,int r,int k)
{
	if(num[x]<=k) return sum[x];
	if(!x) return 0;
	if(l==r) return 1ll*min(num[x],k)*l;
	int mid=(l+r)>>1;
	if(num[rs[x]]>=k) return ask(rs[x],mid+1,r,k);
	return ask(ls[x],l,mid,k-num[rs[x]])+sum[rs[x]];
}
signed main()
{
	//initialize
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)
		c[i]=read(),fa[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		e[i].x=u;e[i].y=v;mp[1ll*u*n+v]=i;
	}
	for(int i=1;i<=k;i++)
	{
		q[i].t=read(),q[i].x=read(),q[i].y=read();
		if(q[i].t==2) c[q[i].x]+=q[i].y;
	}
	//reverse the queries
	reverse(q+1,q+1+k);
	//calc the time in queries and go to cdq
	for(int i=1;i<=k;i++) if(q[i].t==1)
		e[mp[1ll*q[i].x*n+q[i].y]].t=i;
	cdq(1,m,0,k+1);
	//calc the answer as undirected graph
	sort(d+1,d+1+t);
	for(int i=1;i<=n;i++)
		fa[i]=i,ins(rt[i],0,up,c[i],1);
	for(int i=1,j=1;i<=k;i++)
	{
		//link the edge
		while(j<=t && d[j].t<=i)
		{
			int x=Find(d[j].x),y=Find(d[j].y);j++;
			if(x==y) continue ;
			fa[y]=x;rt[x]=comb(rt[x],rt[y]);
		}
		int x=q[i].x,y=q[i].y;ans[i]=-1;
		if(q[i].t==2)
		{
			ins(rt[Find(x)],0,up,c[x],-1);
			c[x]-=y;
			ins(rt[Find(x)],0,up,c[x],1);
		}
		if(q[i].t==3)
			ans[i]=ask(rt[Find(x)],0,up,y);
	}
	for(int i=k;i>=1;i--) if(ans[i]!=-1)
		printf("%lld\n",ans[i]);
}
上一篇:结构体与共同体第一节


下一篇:Java基础复习