Reincarnation

正因为梦易碎，才格外美好。

建图优化

发表于 更新于 分类于 ，
本文字数： 4.9k 阅读时长 ≈ 4 分钟

「末世追忆」：”天将降之于神罚，而风霜雨雪皆有其间。”

优化建图

在某一天的 的某一道题的某一个 的暴力题里，是一个跑 的板子，但是注意到 ，且边是 级别的。然后中午吃饭的时候 就一脸震惊告诉我这绝对会爆（事实证明那点分还是拿到了）。当时 爷就说了一个东西——线段树优化建图，虽然听说过，但是总的来说还是不会，就跑回来学。

大体作用就是，将 级别的边数通过一系列优化使其达到 级别，根据不同题目的限制条件，优化可以是线段树，倍增，主席树以及 加成的前缀和，可以优化的范围也不仅仅最短路和网络流。

我们一个一个地来学习。

线段树优化建图

给出一道板子题，显而易见地，抛开一个比较神秘的连边方式不言，这就是一个最短路的板子题。但是呢，如果就那样连的话，因为有 ，那么，不要说跑 了，就是连边，都有几率 ，所以，考虑优化。

因为限制在于，如果是区间连边，一定是一个连续区间，这个表示形式和线段树很类似，我们就往线段树那个方向去想，考虑建立一个虚点 表示区间 ，然后往 连边，这个东西就和线段树有点类似了。我们把一个区间划分成若干个小区间，这样的话，就可以将 处理为 ，达到优化的效果。

但对于这道题而言，有两个操作分别是单点对区间和区间对单点，所以需要两个线段树，而实际上，两棵线段树的叶结点，也就是对应原图的单点，应该是一致的，也就是说，两棵线段树共用子结点，用图片表示应该是这个样子：

from Luogu sol.

图片来自——洛谷。

其中粉色的线和橙色的线就是两种区间边的连接方式。

注意到：入树边由子结点连向父结点，出树的边由父结点连向子结点，两边叶结点互通，而这些边的代价都是 。

然后就结束了。

注意的是，因为需要开两棵线段树，空间消耗会很大，需要仔细思考应该开多大，可以选择定义一个常数 来使只进行一次 build() 操作。

调了老半天居然是 Dijkstra 写挂了。调得比归程还长……

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// Problem: CF786B Legacy
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF786B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
	read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(char c)
{
	putchar(c);
}
template<>
inline void write(char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
	write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const ll INF=1e18;
const int MAXN=1e6+10,MAXM=1e7+10;
const int K=5e5;
int N,Q,S;
struct G
{
	int next,to;ll val;
}Edge[MAXM];
int Head[MAXN],Total;
inline void addEdge(int u,int v,ll w)
{
	// std::cout<<"addEdge:"<<u<<" "<<v<<" "<<w<<std::endl;
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
struct Que
{
	int x;ll d;
	Que(int x=0,ll d=0):x(x),d(d){}
	bool operator<(const Que &x) const
	{
		return x.d<d;
	}
};
int a[MAXN];
ll Dist[MAXN];
bool Vis[MAXN];
inline void Dijkstra(int st)
{
	std::priority_queue<Que>Q;
	Q.push(Que(st,0));
	for(int i=1;i<=(K<<1);++i) Dist[i]=INF;
	Dist[st]=0;
	memset(Vis,0,sizeof(Vis));
	while(!Q.empty())
	{
		int u=Q.top().x;Q.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(Dist[v]>Dist[u]+Edge[e].val)
			{
				Dist[v]=Dist[u]+Edge[e].val;
				Q.push(Que(v,Dist[v]));
			}
		}
	}
}
#define ls (p<<1)
#define rs (p<<1|1)
void build(int p,int l,int r)
{
	// std::cout<<"add:"<<p<<" "<<l<<" "<<r<<std::endl;
	if(l==r)
	{
		a[l]=p;
		return ;
	}
	int mid=(l+r)>>1;
	addEdge(p,ls,0),addEdge(p,rs,0);
	addEdge(ls+K,p+K,0),addEdge(rs+K,p+K,0);
	// addEdge(p,p+K,0);
	build(ls,l,mid),build(rs,mid+1,r);
	return ;
}
void modify(int opt,int p,int l,int r,int v,int ql,int qr,int x)
{
	if(ql<=l&&r<=qr)
	{
		if(opt==2) addEdge(a[x]+K,p,v);
		else addEdge(p+K,a[x],v);
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) modify(opt,ls,l,mid,v,ql,qr,x);
	if(mid<qr) modify(opt,rs,mid+1,r,v,ql,qr,x);
	return ;
}
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q,S);
	build(1,1,N);
	for(int i=1;i<=N;++i) addEdge(a[i],a[i]+K,0),addEdge(a[i]+K,a[i],0);
	for(int i=1,opt,x,l,r,w;i<=Q;++i)
	{
		read(opt);
		if(opt==1) read(l,r,w),addEdge(a[l]+K,a[r],w);
		else
		{
			read(x,l,r,w);
			modify(opt,1,1,N,w,l,r,x);
		}
	}
	Dijkstra(a[S]+K);
	for(int i=1;i<=N;++i) write(Dist[a[i]]==INF?-1:Dist[a[i]],' ');
	return 0;
}
/*

*/

P5025

CF1007D

可持久化线段树建图优化

相关文章