线段树扩展

[toc]

CF 1083C 线段树二分 - 查询树上拥有最大MEX值的简单路径

给出一棵树,树上所有点的点权是[0, n - 1]的一个排列

进行Q次操作:

  • 交换某两个点之间的点权
  • 查询树上拥有最大MEX值的简单路径,输出MEX值

维护一个线段树,线段树上区间[l, r]记录着数值[l, r]是否在一条简单路径内,如果是的话同时记录简单路径的两个端点

相比于一般的线段树比较不同的是up函数的设置,算法中采用了这样的办法:已经两条简单路径各自的两个端点,从这4个点中枚举2个点尝试作为新路径的端点,分别检查剩余两个点到这两个端点的距离之和是否等于路径本身的距离。

因为要查询两点的距离,所以掏出前阵子的点分树中O1 ST表

接下来在线段树上做二分,查询出最长的连续的前缀即可

复杂度$O(nlogn)$ 写的很挫 常数巨大

在merge中及时的breakreturn、以及修改vector<int> vecint vec[4]才算卡过去

果然nlognlogn是不太可能通过 二分加线段树查询的算法不可行

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
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int maxn = 2e5 + 10;
const int N = 20;
const double eps = 1e-8;

int n, w[manx];
int head[manx], par[maxn], top = 0;
struct {int to, next;}edge[maxn];
void add(int u, int v){
edge[top].to = v;
edge[top].next = head[u];
par[v] = u;
haed[u] = top++;
}

int dfn[maxn << 1], pos[manx], cnt = 0;
int dep[maxn];
void dfs(int now, int par){
dfn[cnt] = now; pos[now] = cnt; cnt++;
for(int i = head[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(to == par) continue;
dep[to] = dep[now] + 1;
dfs(to, now);
dfn[cnt++] = now;
}
}

namespace TEMP{
int st[maxn << 1][N];
//通过深度数组获取st表, st维护区间中深度最小的节点标号
void getst(){
dfs(1, 0);
for(int i = 0; i < cnt; i++) st[i][0] = dfn[i];
for(int j = 1; j < N; j++){
for(int i = 0; i < cnt; i++){
int nxt = i + (1 << (j - 1));
if(nxt >= cnt) st[i][j] = st[i][j - 1];
else if(dep[st[i][j - 1]] < dep[st[nxt][j - 1]]) st[i][j] = st[i][j - 1];
else st[i][j] = st[nxt][j - 1];
}
}
}
};
//O1获取两点之间的距离
int getdis(int x, int y){
if(x == y) return 0;
int l = min(pos[x], pos[y]), r = max(pos[x], pos[y]);
int k = (int)(log2(r - l) + eps);
int lca = TEMP::st[l][k];
if(dep[lca] > dep[TEMP::st[r - (1 << k) + 1][k]]) lca = TEMP::st[r - (1 << k) + 1][k];
return dep[x] + dep[y] - 2 * dep[lca];
}

//线段树st上区间[l, r]表示数值[l, r]是否在一条简单路径上,同时维护简单路径的两个端点
struct NODE{
int l, r;
NODE(){l = r = -1;}
};

NODE st[maxn << 2];
int vec[4];
//检查a和b所代表的两个简单路径是否能被一个新的简单路径包含
bool check(int i, int j){
int dis = getdis(vec[i], vec[j]);
for(int k = 0; k < 4; k++) if(k != i && k != j){
if(getdis(vec[k], vec[i]) + getdis(vec[k], vec[j]) != dis) return 0;
}
return 1;
}

NODE merge(NODE &a, NODE &b){
NODE temp;
if(a.l == -1 || b.l == -1) return temp;
vec[0] = a.l; vec[1] = a.r; vec[2] = b.l; vec[3] = b.r;

for(int i = 0; i < 4; i++) for(int j = i + 1; j < 4; j++) if(check(i, j)){
temp.l = vec[i];
temp.r = vec[j];
return temp;
}
return temp;
}
//k值现在处在节点x的位置
void update(int p, int l, int r, int k, int x){
if(l == r && l == k){
st[p].l = st[p].r = x;
return ;
}
if(k <= mid) update(ls, l, mid, k, x);
else update(rs, mid + 1, r, k, x);
st[p] = merge(st[ls], st[rs]);
}

//根据ans.first尝试缀上某个前缀
pair<int, NODE> ans;
void query(int p, int l, int r){
if(st[p].l != -1 && ans.first + 1 == l){
NODE temp;
if(ans.first == -1){
ans.first = r;
ans.second = st[p];
return ;
}
else temp = merge(ans.second, st[p]);
if(temp.l != -1){
ans.first = r;
ans.second = temp;
return ;
}
}
if(l == r) return;
query(ls, l, mid);
if(ans.first == mid) query(rs, mid + 1, r);
}


int main(){
// Fastin;
scnaf("%d", &n);
clr(head, -1);
for(int i = 1; i <= n; i++) scanf("%d", w + i);
for(int i = 2; i <= n; i++){
int x; scnaf("%d", &x);
add(x, i);
}
TEMP::getst();

for(int i = 1; i <= n; i++)
update(1, 0, n - 1, w[i], i);
int q; scnaf("%d", &q);
while(q--){
int op; scanf("%d", &op);
if(op == 1){
int x, y; scanf("%d %d", &x, &y);
update(1, 0, n - 1, w[y], x);
update(1, 0, n - 1, w[x], y);
swap(w[x], w[y]);
}
else{
ans.first = -1;
query(1, 0, n -1);
printf("%d\n", ans.first + 1);
}
}
return 0;
}

bzoj3073 线段树优化建图

给出n个节点、m种边。

对于某一种边而言,有4个参数:a, b, c, d,表示对于所有的$a \leq x \leq b, c \leq y \leq d$都有一条无向边$$相连。

询问对于某个指定点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完成最短路的求解。

具体实现如下(使用双端队列):

1
2
3
4
5
6
7
8
while(队列非空){
取出队首元素now
for(now的相邻节点){
更新距离
if(边权为0) 添加到队首
else 添加到队尾
}
}

AC代码

在开设A、B两棵树、添加有向边的时候可以精心选择偏移量等数值,使得快速获取想要的下标。

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
#define mid ((l + r) >> 1)

const int maxn = 5e5 + 10;
const int maxe = 4e7 + 10;
int M;

int n, m, p;
struct {int to, next, w;}edge[maxe];
int head[maxe], top = 0;
void add(int u, int v, int w){
edge[top].to = v;
edge[top].w = w;
edge[top].next = head[u];
head[u] = top++;
}


int cnt = 0, pos[maxn], ls[maxn << 3], rs[maxn << 3];
int build(int l, int r){
int now = cnt++;
if(l == r){
add(now, now + M, 0);
return pos[l] = now;
}
ls[now] = build(l, mid);
add(now, ls[now], 0); add(ls[now] + M, now + M, 0);
rs[now] = build(mid + 1, r);
add(now, rs[now], 0); add(rs[now] + M, now + M, 0);
return now;
}


void update(int p, int l, int r, int L, int R, int u, int type){
if(L <= l && r <= R){
if(type) add(p + M, u, 1); else add(u, p, 0);
return ;
}
if(L <= mid) update(ls[p], l, mid, L, R, u, type);
if(R > mid) update(rs[p], mid + 1, r, L, R, u, type);
}

int dis[5000000];
deque<int> q;
void bfs(){
clr(dis, 0x3f);
while(!q.empty()) q.pop_back();

dis[pos[p]] = 0; q.push_back(pos[p]);
while(!q.empty()){
int now = q.front(); q.pop_front();

for(int i = head[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(dis[to] != 0x3f3f3f3f) continue;
dis[to] = dis[now] + edge[i].w;
if(edge[i].w) q.push_back(to);
else q.push_front(to);
}
}
}


int main(){
// Fastin;
clr(head, -1);
scanf("%d %d %d", &n, &m, &p);
M = n << 2; build(1, n);
for(int i = 0; i < m; i++){
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
//加入虚点i + 2M与i + 1 + 2M;
update(0, 1, n, a, b, 2 * i + 2 * M, 1); update(0, 1, n, c, d, 2 * i + 2 * M, 0);
update(0, 1, n, c, d, 2 * i + 2 * M + 1, 1); update(0, 1, n, a, b, 2 * i + 2 * M + 1, 0);
}
bfs();
for(int i = 1; i <= n; i++) printf("%d\n", dis[pos[i]]);
return 0;
}

线段树合并

线段树合并是这样的一种操作:

当构造规则指定、左右边界确定后,任意两棵线段树的结构一定相同,所以我们可以据此将两颗边界相同的线段树进行合并。

CF 600E 子树最多出现次数颜色和的查询

给出一棵n节点的树,每个节点具有一个颜色。

输出在以1为根时,每个节点及其子树上所有节点中最多数量的颜色的和。

$n \leq 1e5, c_i \leq n$

每插入一个节点,会产生logn个新节点,因而总共至多产生nlogn个新节点。

而在每一次merge时,会合并掉一个节点,合并的复杂度是$O(1)$,所以至多进行nlogn次合并。

因而线段树合并的总体复杂度是$O(nlogn)$

相比于$O(nlog^2n)$的启发式合并复杂度更小,更好写。

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
/*
动态开点线段树:
- 插入一个节点
- 合并两棵树
维护出现最多的次数的颜色的和,记录两个值(出现次数,颜色和)
*/
#define mid ((l + r) >> 1)
const int maxn = 1e5 + 10;
const int M = 1e5 * 20 * 4;

int n;
int haed[maxn], top = 0, root[maxn];
star edge[maxn << 2];
void add(int u, int v){
edge[top].to = v;
edge[top].next = head[u];
head[u] = top++;
}

struct NODE{int mx; ll sum;};
NODE st[M];
int ls[M], rs[M], cnt = 1;
//cnt必须从1开始!这是由merge的实现所决定的!
//加入一个单点作为初始化
void update(int &p, int l, int r, int k){
if(!p) p = cnt++;
if(l == r && l == k){
st[p].mx = 1; st[p].sum = k;
return ;
}
if(k <= mid){
update(ls[p], l, mid, k);
st[p] = st[ls[p]];
}
else{
update(rs[p], mid + 1, r, k);
st[p] = st[rs[p]];
}
}

void up(int p){
if(st[ls[p]].mx > st[rs[p]].mx) st[p] = st[ls[p]];
else if(st[ls[p]].mx < st[rs[p]].mx) st[p] = st[rs[p]];
else{
st[p].mx = st[ls[p]].mx;
st[p].sum = st[ls[p]].sum + st[rs[p]].sum;
}
}
//将r1与r2对应的两棵结构相同的线段树进行合并,返回值为合并后的树的标号
int merge(int r1, int r2, int l, int r){
if(!r1) return r2;
if(!r2) return r1;

if(l == r){
st[r1].mx += st[r2].mx;
return r1;
}
ls[r1] = merge(ls[r1], ls[r2], l, mid);
rs[r1] = merge(rs[r1], rs[r2], mid + 1, r);
up(r1);
return r1;
}

ll ans[maxn];
void dfs(int now, int par){
for(int i = head[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(to == par) continue;
dfs(to, now);
root[now] = merge(root[now], root[to], 1, n);
}
ans[now] = st[root[now]].sum;
}


int main(){
// Fastin;
clr(head, -1);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int c; scnaf("%d", &c);
udpate(root[i], 1, n, c);
}
for(int i = 0; i < n - 1; i++){
int u, v; scanf("%d %d", &u, &v);
add(u, v); add(v, u);
}
dfs(1, 0);
prt(ans + 1, n);

return 0;
}

更多的例题 (未补

https://www.luogu.com.cn/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-qi

线段树分裂

区间最值操作与历史最值操作