CF 1083C 线段树二分 - 查询树上拥有最大MEX值的简单路径
给出一棵树，树上所有点的点权是[0, n - 1]的一个排列
进行Q次操作：
- 交换某两个点之间的点权
- 查询树上拥有最大MEX值的简单路径，输出MEX值
维护一个线段树，线段树上区间[l, r]记录着数值[l, r]是否在一条简单路径内，如果是的话同时记录简单路径的两个端点
相比于一般的线段树比较不同的是up函数的设置，算法中采用了这样的办法：已经两条简单路径各自的两个端点，从这4个点中枚举2个点尝试作为新路径的端点，分别检查剩余两个点到这两个端点的距离之和是否等于路径本身的距离。
因为要查询两点的距离，所以掏出前阵子的点分树中O1 ST表
接下来在线段树上做二分，查询出最长的连续的前缀即可
复杂度$O(nlogn)$ 写的很挫 常数巨大
在merge中及时的break和return、以及修改vector<int> vec为 int vec[4]才算卡过去
果然nlognlogn是不太可能通过 二分加线段树查询的算法不可行
cpp
1#define ls (p << 1)
2#define rs ((p << 1) | 1)
3#define mid ((l + r) >> 1)
4
5const int maxn = 2e5 + 10;
6const int N = 20;
7const double eps = 1e-8;
8
9int n, w[manx];
10int head[manx], par[maxn], top = 0;
11struct {int to, next;}edge[maxn];
12void add(int u, int v){
13 edge[top].to = v;
14 edge[top].next = head[u];
15 par[v] = u;
16 haed[u] = top++;
17}
18
19int dfn[maxn << 1], pos[manx], cnt = 0;
20int dep[maxn];
21void dfs(int now, int par){
22 dfn[cnt] = now; pos[now] = cnt; cnt++;
23 for(int i = head[now]; ~i; i = edge[i].next){
24 int to = edge[i].to; if(to == par) continue;
25 dep[to] = dep[now] + 1;
26 dfs(to, now);
27 dfn[cnt++] = now;
28 }
29}
30
31namespace TEMP{
32 int st[maxn << 1][N];
33 //通过深度数组获取st表, st维护区间中深度最小的节点标号
34 void getst(){
35 dfs(1, 0);
36 for(int i = 0; i < cnt; i++) st[i][0] = dfn[i];
37 for(int j = 1; j < N; j++){
38 for(int i = 0; i < cnt; i++){
39 int nxt = i + (1 << (j - 1));
40 if(nxt >= cnt) st[i][j] = st[i][j - 1];
41 else if(dep[st[i][j - 1]] < dep[st[nxt][j - 1]]) st[i][j] = st[i][j - 1];
42 else st[i][j] = st[nxt][j - 1];
43 }
44 }
45 }
46};
47//O1获取两点之间的距离
48int getdis(int x, int y){
49 if(x == y) return 0;
50 int l = min(pos[x], pos[y]), r = max(pos[x], pos[y]);
51 int k = (int)(log2(r - l) + eps);
52 int lca = TEMP::st[l][k];
53 if(dep[lca] > dep[TEMP::st[r - (1 << k) + 1][k]]) lca = TEMP::st[r - (1 << k) + 1][k];
54 return dep[x] + dep[y] - 2 * dep[lca];
55}
56
57//线段树st上区间[l, r]表示数值[l, r]是否在一条简单路径上，同时维护简单路径的两个端点
58struct NODE{
59 int l, r;
60 NODE(){l = r = -1;}
61};
62
63NODE st[maxn << 2];
64int vec[4];
65//检查a和b所代表的两个简单路径是否能被一个新的简单路径包含
66bool check(int i, int j){
67 int dis = getdis(vec[i], vec[j]);
68 for(int k = 0; k < 4; k++) if(k != i && k != j){
69 if(getdis(vec[k], vec[i]) + getdis(vec[k], vec[j]) != dis) return 0;
70 }
71 return 1;
72}
73
74NODE merge(NODE &a, NODE &b){
75 NODE temp;
76 if(a.l == -1 || b.l == -1) return temp;
77 vec[0] = a.l; vec[1] = a.r; vec[2] = b.l; vec[3] = b.r;
78
79 for(int i = 0; i < 4; i++) for(int j = i + 1; j < 4; j++) if(check(i, j)){
80 temp.l = vec[i];
81 temp.r = vec[j];
82 return temp;
83 }
84 return temp;
85}
86//k值现在处在节点x的位置
87void update(int p, int l, int r, int k, int x){
88 if(l == r && l == k){
89 st[p].l = st[p].r = x;
90 return ;
91 }
92 if(k <= mid) update(ls, l, mid, k, x);
93 else update(rs, mid + 1, r, k, x);
94 st[p] = merge(st[ls], st[rs]);
95}
96
97//根据ans.first尝试缀上某个前缀
98pair<int, NODE> ans;
99void query(int p, int l, int r){
100 if(st[p].l != -1 && ans.first + 1 == l){
101 NODE temp;
102 if(ans.first == -1){
103 ans.first = r;
104 ans.second = st[p];
105 return ;
106 }
107 else temp = merge(ans.second, st[p]);
108 if(temp.l != -1){
109 ans.first = r;
110 ans.second = temp;
111 return ;
112 }
113 }
114 if(l == r) return;
115 query(ls, l, mid);
116 if(ans.first == mid) query(rs, mid + 1, r);
117}
118
119
120int main(){
121// Fastin;
122 scnaf("%d", &n);
123 clr(head, -1);
124 for(int i = 1; i <= n; i++) scanf("%d", w + i);
125 for(int i = 2; i <= n; i++){
126 int x; scnaf("%d", &x);
127 add(x, i);
128 }
129 TEMP::getst();
130
131 for(int i = 1; i <= n; i++)
132 update(1, 0, n - 1, w[i], i);
133 int q; scnaf("%d", &q);
134 while(q--){
135 int op; scanf("%d", &op);
136 if(op == 1){
137 int x, y; scanf("%d %d", &x, &y);
138 update(1, 0, n - 1, w[y], x);
139 update(1, 0, n - 1, w[x], y);
140 swap(w[x], w[y]);
141 }
142 else{
143 ans.first = -1;
144 query(1, 0, n -1);
145 printf("%d\n", ans.first + 1);
146 }
147 }
148 return 0;
149}bzoj3073 线段树优化建图
给出n个节点、m种边。
对于某一种边而言，有4个参数：a, b, c, d，表示对于所有的$a \leq x \leq b, c \leq y \leq d$都有一条无向边$<x, y>$相连。
询问对于某个指定点p而言，到其他所有点的最短距离
数据范围 $n \leq 5e5, m \leq 1e5$
线段树优化建图
朴素的做法是对每一种边都用虚点刻画相连关系，即将所有的[a, b]连向虚点u，再将u连向所有的[c, d]。时空复杂度为$O(mn^2)$
线段树优化建图则利用了线段树的分治特性，不再暴力地将所有的[a, b]或[c, d]节点与虚点相连，而是将线段树上对应的区间节点与虚点相连，这样可以保证对于任意一段区间，都只有$logn$个节点与虚点相连，空间复杂度$O(m*log^2n)$。
具体的实现如下：
建立两棵线段树结构的树形结构，第一棵从父亲节点向儿子节点连边，称为树A，第二棵从儿子节点向父亲节点连边，称为树B。A树的所有叶子相应地连向B中所有的叶子。
接下来每读入一组abcd, 将将B树中对应[a, b]区间的节点连向虚点，再将该虚点连向A树中[c, d]区间对应的节点。反过来再对[c, d]和[a, b]进行同样的连接。为了使得权值总为1，可以不妨使得入边权为1，出边权为0。
这样，便利用了线段树的结构完成了较为高效的图的建立。
01 BFS
由于该图边权仅为0或1，所以考虑使用01BFS完成最短路的求解。
具体实现如下（使用双端队列）：
cpp
1while(队列非空){
2 取出队首元素now
3 for(now的相邻节点){
4 更新距离
5 if(边权为0) 添加到队首
6 else 添加到队尾
7 }
8}
AC代码
在开设A、B两棵树、添加有向边的时候可以精心选择偏移量等数值，使得快速获取想要的下标。
cpp
1#define mid ((l + r) >> 1)
2
3const int maxn = 5e5 + 10;
4const int maxe = 4e7 + 10;
5int M;
6
7int n, m, p;
8struct {int to, next, w;}edge[maxe];
9int head[maxe], top = 0;
10void add(int u, int v, int w){
11 edge[top].to = v;
12 edge[top].w = w;
13 edge[top].next = head[u];
14 head[u] = top++;
15}
16
17
18int cnt = 0, pos[maxn], ls[maxn << 3], rs[maxn << 3];
19int build(int l, int r){
20 int now = cnt++;
21 if(l == r){
22 add(now, now + M, 0);
23 return pos[l] = now;
24 }
25 ls[now] = build(l, mid);
26 add(now, ls[now], 0); add(ls[now] + M, now + M, 0);
27 rs[now] = build(mid + 1, r);
28 add(now, rs[now], 0); add(rs[now] + M, now + M, 0);
29 return now;
30}
31
32
33void update(int p, int l, int r, int L, int R, int u, int type){
34 if(L <= l && r <= R){
35 if(type) add(p + M, u, 1); else add(u, p, 0);
36 return ;
37 }
38 if(L <= mid) update(ls[p], l, mid, L, R, u, type);
39 if(R > mid) update(rs[p], mid + 1, r, L, R, u, type);
40}
41
42int dis[5000000];
43deque<int> q;
44void bfs(){
45 clr(dis, 0x3f);
46 while(!q.empty()) q.pop_back();
47
48 dis[pos[p]] = 0; q.push_back(pos[p]);
49 while(!q.empty()){
50 int now = q.front(); q.pop_front();
51
52 for(int i = head[now]; ~i; i = edge[i].next){
53 int to = edge[i].to; if(dis[to] != 0x3f3f3f3f) continue;
54 dis[to] = dis[now] + edge[i].w;
55 if(edge[i].w) q.push_back(to);
56 else q.push_front(to);
57 }
58 }
59}
60
61
62int main(){
63// Fastin;
64 clr(head, -1);
65 scanf("%d %d %d", &n, &m, &p);
66 M = n << 2; build(1, n);
67 for(int i = 0; i < m; i++){
68 int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
69 //加入虚点i + 2M与i + 1 + 2M;
70 update(0, 1, n, a, b, 2 * i + 2 * M, 1); update(0, 1, n, c, d, 2 * i + 2 * M, 0);
71 update(0, 1, n, c, d, 2 * i + 2 * M + 1, 1); update(0, 1, n, a, b, 2 * i + 2 * M + 1, 0);
72 }
73 bfs();
74 for(int i = 1; i <= n; i++) printf("%d\n", dis[pos[i]]);
75 return 0;
76}线段树合并
线段树合并是这样的一种操作：
当构造规则指定、左右边界确定后，任意两棵线段树的结构一定相同，所以我们可以据此将两颗边界相同的线段树进行合并。
CF 600E 子树最多出现次数颜色和的查询
给出一棵n节点的树，每个节点具有一个颜色。
输出在以1为根时，每个节点及其子树上所有节点中最多数量的颜色的和。
$n \leq 1e5, c_i \leq n$
每插入一个节点，会产生logn个新节点，因而总共至多产生nlogn个新节点。
而在每一次merge时，会合并掉一个节点，合并的复杂度是$O(1)$，所以至多进行nlogn次合并。
因而线段树合并的总体复杂度是$O(nlogn)$
相比于$O(nlog^2n)$的启发式合并复杂度更小，更好写。
cpp
1/*
2 动态开点线段树：
3 - 插入一个节点
4 - 合并两棵树
5 维护出现最多的次数的颜色的和，记录两个值(出现次数，颜色和)
6 */
7#define mid ((l + r) >> 1)
8const int maxn = 1e5 + 10;
9const int M = 1e5 * 20 * 4;
10
11int n;
12int haed[maxn], top = 0, root[maxn];
13star edge[maxn << 2];
14void add(int u, int v){
15 edge[top].to = v;
16 edge[top].next = head[u];
17 head[u] = top++;
18}
19
20struct NODE{int mx; ll sum;};
21NODE st[M];
22int ls[M], rs[M], cnt = 1;
23//cnt必须从1开始！这是由merge的实现所决定的！
24//加入一个单点作为初始化
25void update(int &p, int l, int r, int k){
26 if(!p) p = cnt++;
27 if(l == r && l == k){
28 st[p].mx = 1; st[p].sum = k;
29 return ;
30 }
31 if(k <= mid){
32 update(ls[p], l, mid, k);
33 st[p] = st[ls[p]];
34 }
35 else{
36 update(rs[p], mid + 1, r, k);
37 st[p] = st[rs[p]];
38 }
39}
40
41void up(int p){
42 if(st[ls[p]].mx > st[rs[p]].mx) st[p] = st[ls[p]];
43 else if(st[ls[p]].mx < st[rs[p]].mx) st[p] = st[rs[p]];
44 else{
45 st[p].mx = st[ls[p]].mx;
46 st[p].sum = st[ls[p]].sum + st[rs[p]].sum;
47 }
48}
49//将r1与r2对应的两棵结构相同的线段树进行合并，返回值为合并后的树的标号
50int merge(int r1, int r2, int l, int r){
51 if(!r1) return r2;
52 if(!r2) return r1;
53
54 if(l == r){
55 st[r1].mx += st[r2].mx;
56 return r1;
57 }
58 ls[r1] = merge(ls[r1], ls[r2], l, mid);
59 rs[r1] = merge(rs[r1], rs[r2], mid + 1, r);
60 up(r1);
61 return r1;
62}
63
64ll ans[maxn];
65void dfs(int now, int par){
66 for(int i = head[now]; ~i; i = edge[i].next){
67 int to = edge[i].to; if(to == par) continue;
68 dfs(to, now);
69 root[now] = merge(root[now], root[to], 1, n);
70 }
71 ans[now] = st[root[now]].sum;
72}
73
74
75int main(){
76// Fastin;
77 clr(head, -1);
78 scanf("%d", &n);
79 for(int i = 1; i <= n; i++){
80 int c; scnaf("%d", &c);
81 udpate(root[i], 1, n, c);
82 }
83 for(int i = 0; i < n - 1; i++){
84 int u, v; scanf("%d %d", &u, &v);
85 add(u, v); add(v, u);
86 }
87 dfs(1, 0);
88 prt(ans + 1, n);
89
90 return 0;
91}更多的例题 （未补
https://www.luogu.com.cn/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-qi