Post 88

Veröffentlicht am | Edited on

背影却，重叠回那少年。

线段树合并SegmentTree Merge

问题引入：有$n$棵权值线段树，线段树点数总和为$n$，怎么合并？可用于合并两个集合元素，同时查询第$k$大等。

算法流程是这样的：

1
2
3
4
5
6
7
void merge(root1,root2){//合并到root1上
    if 两颗左子树中有空树 直接给root1接上不是空树的左子树
        else merge(root1.leftson,root2.leftson)
    if 两颗右子树中有空树 直接给root1接上不是空树的右子树
        else merge(root1.rightson,root2.rightson)
    删掉root2这个点
}

线段树最大深度是$logV$

每次都会删除一个点，总的复杂度不会超过$O(n)$（注意$n$是点数，一般如果进行$n$次操作那么点数应当是$nlogV$）

[Vani有约会]雨天的尾巴

题目背景

深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。

题目描述

首先村落里的一共有n座房屋，并形成一个树状结构。然后救济粮分m次发放，每次选择两个房屋(x,y)，然后对于x到y的路径上（含x和y)每座房子里发放一袋z类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入输出格式

输入格式：

第一行两个正整数n,m，含义如题目所示。
接下来n-1行，每行两个数(a,b)，表示(a,b)间有一条边。
再接下来m行，每行三个数(x,y,z)，含义如题目所示。

输出格式：

n行，第i行一个整数，表示第i座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。
如果某座房屋里没有救济粮，则对应一行输出0。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

输出样例#1：

1
2
3
4
5
2
3
3
0
2

说明

对于20%的数据，1 <= n, m <= 100
对于50%的数据，1 <= n, m <= 2000
对于100%的数据，1 <= n, m <= 100000, 1 <= a, b, x, y <= n, 1 <= z <= 100000
Vani

题解

这种链加减一般使用HLD解决，但是HLD的普通区间线段树解决不了这个问题。

我们给每个点开一颗权值线段树，每次修改$(x,y,z)$在点上差分，然后修改$x,y,LCA{x,y},f{LCA_{x,y}}$分别为$+1,+1,-1,-1$。（这个加减是在点的权值线段树上）

然后这一部分的复杂度是$O(qlogn)$（一般用HLD解决LCA，是$O(qlog^2n)$

接下来我们做”子树和”,自底向上把每个权值线段树合并。这个复杂度是正确的，因为通过差分我们只创建了$O(nlogV)$个点。合并复杂度为$O(nlogV)$，空间复杂度是$O(nlogV)$

注意线段树合并复杂度是线性的，每一次常数复杂度的$merge$调用都会删除一个节点。

线段树合并的思想大概也是信息的可加性使得我们可以迅速合并两个值域相同的区间。

代码咕咕咕了，剩下半小时写数学。其实不会写代码，甚至想写一个暴力

补充一下关于线段树合并的复杂度问题。

感觉我想的稍微有点简单，设点数为$n$。

那么线段树合并的复杂度是

$T(n) = T(a)+T(b) + min\{a,b\} , a+b = n$

发现这就是启发式合并的复杂度，为$O(nlogn)$

然而这个上界并不够好，我们发现如果每次合并到一颗树上，被合并过去的点如果再也不合并，当成删除的话，那么很容易聚合分析出复杂度是$O(n)$的。

那么如果我们合并的时候，假如其中一个点没有子树就把另一个接上，否则新开一个点来继承两个点的信息并

这样做显然分治复杂度依然成立，那么还能不能聚合分析呢？

是可以的，只是要确保每颗树只合并一次（我在说什么每棵树肯定只合并一次，就当我又写了一段废话）

所以线段树合并这题就好写了。

动态开点：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
const int V = 100000;
int tot , ct ,head[maxn] , lc[maxn<<5] , rc[maxn<<5] , seg[2][maxn<<5] , rt[maxn] , ans[maxn],n ,m;
struct edge{
	int next, to;
}e[maxn<<1];

inline void add(int x , int y)
{
	e[++ct] = (edge){head[x] , y};
	head[x] = ct;
}

namespace HLD
{
    int tp[maxn] , sz[maxn] , hs[maxn] , dep[maxn] , f[maxn];
    void dfs1(int x , int fx)
    {
        f[x] = fx , dep[x] = dep[fx] + 1 , sz[x] = 1 ;
        for(int i = head[x] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(v == fx) continue;
            dfs1(v , x) , sz[x] += sz[v];
            if(sz[hs[x]] < sz[v]) hs[x] = v;
        }
    }
    void dfs2(int x , int tpx)
    {
        tp[x] = tpx;
        if(!hs[x]) return;
        dfs2(hs[x] , tpx);
        for(int i = head[x] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(v == f[x] || v == hs[x]) continue;
            dfs2(v , v);
        }
    }
    inline int LCA(int x , int y)
    {
        for( ; tp[x] != tp[y] ; x = f[tp[x]]) if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        return dep[x] < dep[y] ? x : y;
    }
}

inline void pushup(int x){
    if(seg[0][lc[x]] >= seg[0][rc[x]]) seg[0][x] = seg[0][lc[x]] , seg[1][x] = seg[1][lc[x]];
	else seg[0][x] = seg[0][rc[x]] , seg[1][x] = seg[1][rc[x]];
}

void ins(int x , int pos , int nl , int nr , int& nd , int v)
{
    if(!nd) nd = ++tot;
    if(nl == nr){
        seg[0][nd] += v , seg[1][nd] = nr;
        return;
    }
    int mid = nl + nr >> 1;
    if(pos <= mid) ins(x , pos , nl , mid , lc[nd] , v);
    else ins(x , pos , mid + 1 , nr , rc[nd] , v);
    pushup(nd);
}
int merge(int a , int b , int l , int r) 
{ // merge segment tree a and b , return the new tree root
    if(!a || !b) return a ? a : b;
    int root = ++tot;
    if(l == r) {
        seg[0][root] = seg[0][a] + seg[0][b] , seg[1][root] = l;
        return root;
    }
    int mid = l + r >> 1;
    lc[root] = merge(lc[a] , lc[b] , l , mid) , rc[root] = merge(rc[a] , rc[b] , mid + 1 , r);
    pushup(root);
    return root;
}

void getMerge(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next){
        int v = e[i].to;
        if(v == fx) continue;
        getMerge(v , x);
        rt[x] = merge(rt[v] , rt[x] , 1 , V);
    }
    if(seg[0][rt[x]]) ans[x] = seg[1][rt[x]];
	else ans[x] = 0;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i < n ; ++i)
    {
        int x , y;
        scanf("%d%d",&x,&y);
        add(x,y) , add(y,x);
    }
    for(int i = 1 ; i <= n ; ++i)
        rt[i] = ++tot;
    HLD::dfs1(1,1) , HLD::dfs2(1,1);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y , z;
        scanf("%d%d%d",&x,&y,&z);
        int lca = HLD::LCA(x , y);
        ins(x , z , 1 , V , rt[x] , 1);
        ins(y , z , 1 , V , rt[y] , 1);
        ins(lca , z, 1 , V , rt[lca] , -1);
        if(lca != 1) ins(HLD::f[lca] , z , 1 , V , rt[HLD::f[lca]] , -1);
    }
    getMerge(1 , 1);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d\n",ans[i]);
}

由于这个sb题卡了内存，就得不动态开点，不动态开点有时不可做（也不爽）。

稍微改一改$Merge$即可,把一棵树直接加到另一颗树上。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
const int V = 100000;
int tot , ct ,head[maxn] , lc[maxn<<5] , rc[maxn<<5] , seg[2][maxn<<5] , rt[maxn] , ans[maxn],n ,m;
struct edge{
	int next, to;
}e[maxn<<1];

inline void add(int x , int y)
{
	e[++ct] = (edge){head[x] , y};
	head[x] = ct;
}

namespace HLD
{
    int tp[maxn] , sz[maxn] , hs[maxn] , dep[maxn] , f[maxn];
    void dfs1(int x , int fx)
    {
        f[x] = fx , dep[x] = dep[fx] + 1 , sz[x] = 1 ;
        for(int i = head[x] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(v == fx) continue;
            dfs1(v , x) , sz[x] += sz[v];
            if(sz[hs[x]] < sz[v]) hs[x] = v;
        }
    }
    void dfs2(int x , int tpx)
    {
        tp[x] = tpx;
        if(!hs[x]) return;
        dfs2(hs[x] , tpx);
        for(int i = head[x] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(v == f[x] || v == hs[x]) continue;
            dfs2(v , v);
        }
    }
    inline int LCA(int x , int y)
    {
        for( ; tp[x] != tp[y] ; x = f[tp[x]]) if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        return dep[x] < dep[y] ? x : y;
    }
}

inline void pushup(int x){
    if(seg[0][lc[x]] >= seg[0][rc[x]]) seg[0][x] = seg[0][lc[x]] , seg[1][x] = seg[1][lc[x]];
	else seg[0][x] = seg[0][rc[x]] , seg[1][x] = seg[1][rc[x]];
}

void ins(int x , int pos , int nl , int nr , int& nd , int v)
{
    if(!nd) nd = ++tot;
    if(nl == nr){
        seg[0][nd] += v , seg[1][nd] = nr;
        return;
    }
    int mid = nl + nr >> 1;
    if(pos <= mid) ins(x , pos , nl , mid , lc[nd] , v);
    else ins(x , pos , mid + 1 , nr , rc[nd] , v);
    pushup(nd);
}
int merge(int a , int b , int l , int r) 
{ // merge segment tree a and b , return the new tree root
    if(!a || !b) return a ? a : b;
//    int root = ++tot;
    if(l == r) {
        seg[0][a] = seg[0][a] + seg[0][b] , seg[1][a] = l;
        return a;
    }
    int mid = l + r >> 1;
    lc[a] = merge(lc[a] , lc[b] , l , mid) , rc[a] = merge(rc[a] , rc[b] , mid + 1 , r);
    pushup(a);
    return a;
}

void getMerge(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next){
        int v = e[i].to;
        if(v == fx) continue;
        getMerge(v , x);
        rt[x] = merge(rt[x] , rt[v] , 1 , V);
    }
    if(seg[0][rt[x]]) ans[x] = seg[1][rt[x]];
	else ans[x] = 0;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i < n ; ++i)
    {
        int x , y;
        scanf("%d%d",&x,&y);
        add(x,y) , add(y,x);
    }
    for(int i = 1 ; i <= n ; ++i)
        rt[i] = ++tot;
    HLD::dfs1(1,1) , HLD::dfs2(1,1);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y , z;
        scanf("%d%d%d",&x,&y,&z);
        int lca = HLD::LCA(x , y);
        ins(x , z , 1 , V , rt[x] , 1);
        ins(y , z , 1 , V , rt[y] , 1);
        ins(lca , z, 1 , V , rt[lca] , -1);
        if(lca != 1) ins(HLD::f[lca] , z , 1 , V , rt[HLD::f[lca]] , -1);
    }
    getMerge(1 , 1);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d\n",ans[i]);
}

就通过了这道题。

好久没认真写题了吧。

线段树分治

故名思意，是一种在线段树上分治的高级方法。

具体来说，就是每次递归进入一个线段树区间，进行一些处理然后从这个区间出来的时候撤销操作。

下面

「LibreOJ121」「离线可过」动态图连通性 - 线段树分治

题目大意

    你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。
    0：加入一条边。保证它不存在。
    1：删除一条边。保证它存在。
    2：查询两个点是否联通。

题解

线段树分治+可撤销（或者持久化）并查集。

题目要求查时间单点的点对是否联通，一个很显然的暴力想法是把这段时间没有被删的边给连起来判断。显然这样会超时。

对时间建立一颗线段树，每条边存在的时间是一个区间，把它拆成线段树区间。线段树的每个节点将保存一个边集合。这样时空复杂度不超过$O(nlogn)$

如何利用询问呢？按照DFS序处理所有询问。

按照DFS序遍历线段树节点，每次递归进入的时候把边暴力连上，如果是( •̀ ω •́ )叶节点如果有询问就回答询问。否则递归进子树。父节点如果加入了边那它的两个子区间自然这条边依然存在，虽然很sb的问题但我还是问了下mhr，我可能得回想线段树的原理：分解成至多$O(logn)$个区间

这个遍历配合可持久化/可撤销并查集，时间复杂度$O(nlog^2n)$

我们就解决了这道问题。