聚点建图
简单说就是把很多边经过一个点，从而缩小边数，比如我要从
[
1
,
6
]
[1, 6]
[1,6] 分别连到
[
7
,
12
]
[7, 12]
[7,12]
这时候是
36
36
36 条边，但是如果我让
[
1
,
6
]
[1, 6]
[1,6] 连到一个新点
13
13
13 再从
13
13
13 连到
[
7
,
12
]
[7, 12]
[7,12] 这样建边效果一样，但是只建了
12
12
12 条边和一个新点，从而减少了建边量。如下图。图二中心点就是聚点
而关于边权，在聚点两侧的边任意，但尽量有一个为
0
0
0 权，为了方便赋值变量。
![[聚点建边1.png|350]]
线段树建图
常用于一堆点可以到达另一堆点的情况，且可以叠加
模版题为它 Legacy – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
先看看题意，你会发现无论是聚点建图，还是正常建图，都无可避免的会遇到边数过大的情况，最大
p
×
p
=
1
0
10
p imes p = 10^{10}
p×p=1010 条，这个数量，无论是空间还是时间都没法支持，因此我们需要一中更好的建图方式，即线段树建图。
首先定义两颗线段树树，一颗出树一颗入树，在入树内父节点都连向子节点，在出树内子节点都连向父节点，然后两个数对应节点从入树到出树连一条边。
我们建图，如在
u
u
u 上建一条连向
[
l
,
r
]
[l, r]
[l,r] 的边，即把出树中u节点连向一个新开的聚点，然后让聚点连向入树中的
[
l
,
r
]
[l, r]
[l,r] 的点。
出树意思数，出去的树，开始我们从这里出发，入树是回到出树的树
大体长这样
![[线段树建图1 2.png|475]]
这样实现了个什么呢？
你能发现我从入树的某个点可以到对应的出树点，如果从出树的某个点出发，可以通过绿边到达它的父区间(节点)能到达的点，而通过蓝边(新建边)，可以进入树，到了入树，又可以通过绿边进入子区间(节点)，最后通过红边到达对应出树的子节点。你能发现，这样建图，仅从上面新建的u出发，我可以到达入树的
[
l
,
r
]
[l, r]
[l,r] 区间从而到达出树的
[
l
,
r
]
[l, r]
[l,r] 区间，从而实现了从
u
u
u 点到
[
l
,
r
]
[l, r]
[l,r] 的建图，而我们只用了两条边和新建一个聚点就实现了这个操作。
使用聚点是因为对于出树和入树符合要求的区间(节点)可能不止一个，通过聚点，进一步减少建边量。
关于边权，我们一般放到出树到聚点的那条边上，聚点到入树的边一般设为0，红边和绿边自然也是
0
0
0 权。
关于两个树的存储上，可以定义两个tr数组，也可以在同一个tr上建两棵树这么玩，当然对于某些情况可以把入树和出树变成一棵树，这里分开两棵树是为了防止有些边混乱，导致意想不到的错误，如果空间允许请开两棵树。
一个tr数组的话，第二棵树的下标可以用，+ n * 4的方式偏移。
新开聚点k的下标可以用 n * 8 + m 的方式定义
PS：实际上不用真的定义一个结构体，毕竟我们用到的只是线段树的这个过程，但是这样建图图上点实际上为线段树的下标u，而非题目里给的区间下标，记得对叶节点记录对应num即线段树叶节点下标，方便进行最短路。起点从出树开始。聚点上的边一定是单向的，如果是建无向边就再新开一个聚点k，再从出树入树连边，切记，新建边一定从出树出去。
这时候还没完，大体思路是这样但是建图时还有一个问题，即我们线段树修改一次最多找一个区间，这时候也能看出来用聚点的好处，那么我们连边函数就要写两个，一个从出树到聚点，一个从聚点到入树。
代码
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
void build(int u, int l, int r)
{
add(u, u + n * 4, 0);
if (l != r)
{
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
add(u, u << 1, 0);
add(u, u << 1 | 1, 0);
add((u << 1) + n * 4, u + n * 4, 0);
add((u << 1 | 1) + n * 4, u + n * 4, 0);
}
else num[l] = u + n * 4;
}
void modify1(int u, int l, int r, int a, int b, int k) // 出树的(a, b)到聚点
{
if (a <= l && r > 1;
if (a <= mid) modify1(u << 1, l, mid, a, b, k);
if (mid < b) modify1(u << 1 | 1, mid + 1, r, a, b, k);
}
}
void modify2(int u, int l, int r, int a, int b, int k) // 聚点到入树的(a, b)
{
if (a <= l && r > 1;
if (a <= mid) modify2(u < mid) modify2(u << 1 | 1, mid + 1, r, a, b, k);
}
}
modify1(1, 1, n, a, b, n * 8 + m * 2);
modify2(1, 1, n, c, d, n * 8 + m * 2);
modify1(1, 1, n, c, d, n * 8 + m * 2 - 1);
modify2(1, 1, n, a, b, n * 8 + m * 2 - 1);
关于建双向变的话我有一个更好的代码
这份代码干了两件事，比较麻烦，不建议使用，只是写出来看看。
void modify(int u, int l, int r, int a, int b, int k, int mod)
{
if (a <= l && r > 1;
if (a <= mid) modify(u < mid) modify(u << 1 | 1, mid + 1, r, a, b, k, mod);
}
}
modify(1, 1, n, a, b, n * 8 + m * 2, 0);
modify(1, 1, n, c, d, n * 8 + m * 2, 1);
