登录
← 返回首页 | 代码片段 › 3 图论 › 3.7 线段树优化建图 › 线段树优化建图 / 搜索
JSON MD

3.7 线段树优化建图

线段树优化建边+Dijkstra最短路 Legacy
69 行
CPP JSON
【线段树优化建边+Dijkstra最短路(Legacy)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op) — 核心算法函数 void dijkstra(Re st) — Dijkstra最短路 核心结构体:QAQ, Segment_Tree, QAQ, QWQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 68 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,x,y,w,l,r,o,op,st,head[N<<3];bool pan[N<<3];LL dis[N<<3];
struct QAQ{int w,to,next;}a[(N<<3)+(N<<2)+N*18*2];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int in,out;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=tr[p].out=L;return;}
		tr[p].in=++O,tr[p].out=++O,add(tr[p].in,tr[p].out,0);
		build(pl,L,mid),build(pr,mid+1,R);
		add(tr[p].in,tr[pl].in,0),add(tr[p].in,tr[pr].in,0);
		add(tr[pl].out,tr[p].out,0),add(tr[pr].out,tr[p].out,0);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op){
		if(l<=L&&R<=r){
			if(op)add(tr[p].out,x,w);
			else add(x,tr[p].in,w);
			return;
		}
		if(l<=mid)change(pl,L,mid,l,r,x,w,op);
		if(r>mid)change(pr,mid+1,R,l,r,x,w,op);
	}
}TR;
struct QWQ{int x;LL d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void dijkstra(Re st){
	for(Re i=1;i<=TR.O;++i)dis[i]=inf;
	Q.push((QWQ){st,dis[st]=0});
	while(!Q.empty()){
		Re x=Q.top().x;Q.pop();
		if(pan[x])continue;
		pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w)
				Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(st);
	TR.O=n,TR.build(1,1,n);
	while(m--){
		in(op),in(x);
		if(op<2)in(y),in(w),TR.change(1,1,n,y,y,x,w,0);
		else if(op<3)in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,0);
		else in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,1);
	}
	dijkstra(st);
	for(Re i=1;i<=n;++i)printf("%lld ",dis[i]==inf?-1:dis[i]);
}
线段树优化建边+Dinic最大流 Last chance
100 行
CPP JSON
【线段树优化建边+Dinic最大流(Last chance)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void add_(Re x,Re y,Re flow) — 加法更新 void add(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void dinic(Re st,Re ed) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) 核心结构体:Network_Flow, QAQ, Segment_Tree, QAQ 关键配置: N=5003+3,M=25e4+3,inf=2e9 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 99 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5003+3,M=25e4+3,inf=2e9;
int n,m,x,y,z,O,op,st,ed,X[N],Y[N],Z[N],Ans[N],cnt[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Network_Flow{
	int o,h,t,maxflow,Q[N*3],dis[N*3],cur[N*3],head[N*3];
	struct QAQ{int to,next,flow;}a[M<<1];
	inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
	inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
	inline int bfs(Re st,Re ed){
		for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
		h=1,t=0,dis[Q[++t]=st]=1;
		while(h<=t){
			Re x=Q[h++];
			for(Re i=head[x],to;i;i=a[i].next)
				if(a[i].flow&&!dis[to=a[i].to]){
					dis[Q[++t]=to]=dis[x]+1;
					if(to==ed)return 1;
				}
		}
		return 0;
	}
	inline int dfs(Re x,Re flow){
		if(x==ed||!flow)return flow;
		Re tmp=0,to,f;
		for(Re i=cur[x];i;i=a[i].next){
			cur[x]=i;
			if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(a[i].flow,flow-tmp)))){
				a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
				if(tmp==flow)break;
			}
		}
		return tmp;
	}
	inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
	inline int find(Re x){
		Re last=ed;
		while(x<=O||x>O+n){
			for(Re i=head[x];i;i=a[i].next)
				if(a[i^1].to==x&&a[i].to!=last&&a[i].flow){
					--a[i].flow,last=x,x=a[i].to;break;
				}
		}
		return x-O;
	}
}T1;
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	struct QAQ{int in;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=L;return;}
		tr[p].in=++O,build(pl,L,mid),build(pr,mid+1,R);
		T1.add(tr[p].in,tr[pl].in,inf),T1.add(tr[p].in,tr[pr].in,inf);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w){
		if(l<=L&&R<=r){T1.add(x,tr[p].in,w);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,w);
		if(r>mid)change(pr,mid+1,R,l,r,x,w);
	}
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),T1.o=1,O=m,TR.build(1,1,m),st=O+n+1,ed=st+1;
	for(Re i=1;i<=n;++i){
		in(op);
		if(op<1){
			in(x),T1.add(st,O+i,1);
			while(x--)in(y),T1.add(O+i,y,1);
		}
		else if(op<2)in(x),in(y),T1.add(st,O+i,1),TR.change(1,1,m,x,y,O+i,1);
		else{
			in(x),in(y),in(z),T1.add(st,O+i,2),X[i]=x,Y[i]=y,Z[i]=z;
			T1.add(O+i,x,1),T1.add(O+i,y,1),T1.add(O+i,z,1);
		}
	}
	for(Re j=1;j<=m;++j)T1.add(j,ed,1);
	T1.dinic(st,ed),printf("%d\n",T1.maxflow);
	for(Re i=T1.head[ed];i;i=T1.a[i].next)
		if(T1.a[i].flow)++cnt[Ans[T1.a[i].to]=T1.find(T1.a[i].to)];
	for(Re i=1;i<=n;++i)
		if(X[i]&&cnt[i]==1){
			if(Ans[X[i]]==i)Ans[Y[i]]=i;
			else Ans[X[i]]=i;
		}
	for(Re i=1;i<=m;++i)if(Ans[i])printf("%d %d\n",Ans[i],i);
}
线段树优化建边+Tarjan缩点 炸弹
103 行
CPP JSON
【线段树优化建边+Tarjan缩点(炸弹)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y) — 加法更新 template<typename T>inline void in(T &x) — 核心算法函数 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re x) — 核心算法函数 int find1(LL x,Re r) — 查找(并查集寻根/二分查找) int find2(LL x,Re l) — 查找(并查集寻根/二分查找) void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ, Segment_Tree, QAQ, Tuopu, QAQ 关键配置: N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7 复杂度:建树 O(N),单次操作 O(log N) 说明:printf("(x=%d) -> (l=%d,r=%d) w=%d\n",x,l,r,w);return;;freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 102 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7;
int o,n,Ans,head[N<<2];LL X[N],R[N];
struct QAQ{int x,to,next;}a[M];map<pair<int,int>,int>vis;
inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int in;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=L;return;}
		tr[p].in=++O;
		build(pl,L,mid),build(pr,mid+1,R);
		add(tr[p].in,tr[pl].in),add(tr[p].in,tr[pr].in);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x){
//		printf("(x=%d) -> (l=%d,r=%d) w=%d\n",x,l,r,w);return;
		if(l<=L&&R<=r){add(x,tr[p].in);return;}
		if(l<=mid)change(pl,L,mid,l,r,x);
		if(r>mid)change(pr,mid+1,R,l,r,x);
	}
}TR;
inline int find1(LL x,Re r){
	Re l=1;
	while(l<r){
		Re Mid=l+r>>1;
		if(X[Mid]<x)l=Mid+1;
		else r=Mid;
	}
	return r;
}
inline int find2(LL x,Re l){
	Re r=n;
	while(l<r){
		Re Mid=l+r+1>>1;
		if(X[Mid]>x)r=Mid-1;
		else l=Mid;
	}
	return l;
}
struct Tuopu{
	int o,n,L[N<<2],R[N<<2],ru[N<<2],pan[N<<2],head[N<<2];queue<int>Q;
	struct QAQ{int to,next;}a[M];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		if(pan[x])return;
		pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			dfs(to=a[i].to),L[x]=min(L[x],L[to]),R[x]=max(R[x],R[to]);
	}
	inline void sakura(){for(Re i=1;i<=n;++i)if(!ru[i])dfs(i);}
}T2;
int Q_o,ip[N<<2];
struct Tarjan{
	int n,t,dfn_o,Q[N<<2],low[N<<2],dfn[N<<2],pan[N<<2];
	inline void tarjan(Re x){
		dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o,T2.L[Q_o]=n+1,T2.R[Q_o]=-1;
			while(1){
				ip[Q[t]]=Q_o,pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void sakura(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
		for(Re i=1,x,y;i<=o;++i)
			if((x=ip[a[i].x])!=(y=ip[a[i].to])&&!vis[mp(x,y)])
				vis[mp(x,y)]=1,++T2.ru[y],T2.add(x,y);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),TR.O=n,TR.build(1,1,n);
	for(Re i=1;i<=n;++i)in(X[i]),in(R[i]);
	for(Re i=1;i<=n;++i)TR.change(1,1,n,find1(X[i]-R[i],i),find2(X[i]+R[i],i),i);
	T1.n=TR.O,T1.sakura();
	for(Re i=1;i<=n;++i)T2.L[ip[i]]=min(T2.L[ip[i]],i),T2.R[ip[i]]=max(T2.R[ip[i]],i);;
	T2.n=Q_o,T2.sakura();
	for(Re i=1;i<=n;++i)(Ans+=(LL)i*(T2.R[ip[i]]-T2.L[ip[i]]+1)%P)%=P;
	printf("%d\n",Ans);
}
已复制