线段树分治学习笔记（未完待续）
发表更新ICPC/CCPC / Notes12 分钟读完 (大约1833个字)

线段树分治学习笔记（未完待续）

参考博客：1 2

简述

线段树分治解决一类具有撤销操作的问题。

与可持久化不同，可持久化在某个历史版本上做更改后不会影响到后续的结果，而这里的撤销操作会影响到后续的结果（即这是一个 ‘Retroactive Data Structure’ 而非 ‘Persistent Data Structure’，相关内容参看Eric Demaine的论文或者视频）。

为解决该问题，我们以时间为域建立一棵线段树，则所有的操作、询问对应了线段树上表示相关时间区间的一些节点。节点内储存解决问题需要的数据结构。

如此，倘若我们 $dfs$ 整棵线段树，并在路途中记录操作、在回溯时撤销操作，则到达线段树的每个叶节点时，我们就知道了在当前叶节点所表示的时刻，我们进行了哪些操作。

练习

[TJOI2018]数学计算

题目链接

乍一看以为直接模拟，但是 $mod$ 不保证质数或者互质，处理逆元不方便。

转换思路，以时间为域建立线段树，节点存储该时间乘上的数。除掉某一次操作其实就是更改乘数为 $1$，所以单点修改区间查询即可。

>folded
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
#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 100005;

int T, q, opt;
LL m, MOD;

struct segTree{
    int l, r;
    LL res, mul;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
    tr[id].res = tr[lid].res * tr[rid].res % MOD;
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].res = tr[id].mul = 1;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void modify(int id, int pos, LL val){
    if(tr[id].l == tr[id].r){
        tr[id].mul = val;
        tr[id].res = val;
        return;
    }
    if(pos <= mid)  modify(lid, pos, val);
    else    modify(rid, pos, val);
    pushup(id);
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%lld", &q, &MOD);
        build(1, 1, q);
        for(int i = 1; i <= q; i++){
            scanf("%d%lld", &opt, &m);
            if(opt == 1)    modify(1, i, m);
            else    modify(1, m, 1);
            printf("%lld\n", tr[1].res);
        }
    }
    return 0;
}

luoguP5787 / bzoj4025二分图

题目链接

每一条边对应着一段持续时间，即对应了线段树的若干节点。线段树的每个节点开一个 vector，记录该节点时间段内存在的边，于是我们 $dfs$ 遍历整棵线段树，凡到达一个叶节点就能获知此时图中有哪些边。

由于一个图是二分图当且仅当该图不含奇环，我们只需要判断这些边是否形成奇环，这一点可以用带权并查集完成。回溯时需要撤掉边，所以带权并查集需要是可撤销的——开一个栈记录搜索过程中在并查集中加入了哪些边，回溯时弹栈撤掉这些边，此并查集不能路径压缩，所以要按秩合并以保证复杂度。

再多说一点带权并查集：带的权是一个点到其父节点在原图中的距离的奇偶性。当我们连接 $u,v$ 时，若它们同在一个并查集内且到并查集代表元素的距离同奇偶，则再连上 $(u,v)$ 这条边会导致奇环，输出 No；若它们不在同一个并查集内，设 $u,v$ 各自并查集代表元素为 $x,y$，则我们在并查集中实际上连接的是 $(x,y)$，这条边的权是 $(x,y)$ 在原图中的距离奇偶性，即 $x$ 到 $u$ 的距离奇偶性异或 $y$ 到 $v$ 的距离奇偶性异或 $1$.

时间复杂度：$O(k\lg k\lg n)$

>folded
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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, m, k, u[N], v[N];

struct segTree{
    int l, r;
    vector<int> vec;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].vec.clear();
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
}
void add(int id, int l, int r, int val){
    if(tr[id].l == l && tr[id].r == r){
        tr[id].vec.pb(val);
        return;
    }
    if(r <= mid)  add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
}

stack<pii> sta;
int fa[N], sz[N], dis[N];
int findfa(int x){ return x == fa[x] ? x : findfa(fa[x]); }
int getDis(int x){ return x == fa[x] ? dis[x] : dis[x] ^ getDis(fa[x]); }
void unionn(int x, int y){
    int tx = x, ty = y;
    x = findfa(x), y = findfa(y);
    if(x == y)  return;
    if(sz[x] < sz[y]) swap(x, y);
    sta.push(mp(x, y));
    fa[y] = x, sz[x] += sz[y];
    dis[y] ^= getDis(tx) ^ getDis(ty) ^ 1;
}

void dfs(int id){
    bool ok = true;
    int siz = sta.size();
    for(auto i: tr[id].vec){
        if(findfa(u[i]) == findfa(v[i])){
            if(getDis(u[i]) == getDis(v[i])){
                ok = false;
                break;
            }
        }
        else    unionn(u[i], v[i]);
    }
    if(!ok) for(int i = tr[id].l; i <= tr[id].r; i++)   puts("No");
    else if(tr[id].l == tr[id].r)   puts("Yes");
    else    dfs(lid), dfs(rid);
    while(sta.size() > siz){
        pii cur = sta.top(); sta.pop();
        int x = cur.first, y = cur.second;
        fa[y] = y, sz[x] -= sz[y];
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; i++) fa[i] = i, sz[i] = 1;
    build(1, 1, k);
    for(int i = 1; i <= m; i++){
        int l, r; scanf("%d%d%d%d", &u[i], &v[i], &l, &r);
        if(l < r)   add(1, l + 1, r, i);
    }
    dfs(1);
    return 0;
}

「LibreOJ Round #6」花团

题目链接

线段树每个节点开一个 vector，记录该节点时间段内有哪些物品。然后 $dfs$ 整棵线段树，在搜索的过程中做 $01$ 背包，到达询问点就输出结果。

回溯撤销操作时，需要把 $dp$ 数组置为上一层的 $dp$ 数组，所以 $dp$ 数组开成二维的，以线段树层数为第一维。

复杂度：$O(vq\lg q)$ （不知为何就是可以过～）

>folded
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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)

const int N = 15005;

int q, maxv, T, lastans;

struct segTree{
    int l, r;
    vector<pii> vec;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].vec.clear();
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
}
void add(int id, int l, int r, pii val){
    if(tr[id].l == l && tr[id].r == r){
        tr[id].vec.emplace_back(val);
        return;
    }
    if(r <= mid)    add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
}

int dp[20][N];
void dfs(int dep, int id){
    for(auto k: tr[id].vec)
        for(int j = maxv; j >= k.first; j--)
            dp[dep][j] = max(dp[dep][j-k.first] + k.second, dp[dep][j]);
    if(tr[id].l == tr[id].r){
        int op, v, w, e; scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%d", &v, &w, &e);
            v -= T * lastans, w -= T * lastans, e -= T * lastans;
            if(tr[id].l < e)    add(1, tr[id].l + 1, e, mp(v, w));
        }
        else{
            scanf("%d", &v); v -= T * lastans;
            if(dp[dep][v] < 0){
                puts("0 0");
                lastans = 0;
            }
            else{
                printf("1 %d\n", dp[dep][v]);
                lastans = 1 ^ dp[dep][v];
            }
        }
        return;
    }
    for(int j = 0; j <= maxv; j++)  dp[dep+1][j] = dp[dep][j];
    dfs(dep + 1, lid);
    for(int j = 0; j <= maxv; j++)  dp[dep+1][j] = dp[dep][j];
    dfs(dep + 1, rid);
}

int main(){
    scanf("%d%d%d", &q, &maxv, &T);
    build(1, 1, q);
    for(int i = 1; i <= maxv; i++)  dp[1][i] = -1e9;
    dfs(1, 1);
    return 0;
}

线段树分治学习笔记（未完待续）

http://xyfjason.github.io/blog-xcpc/2020/03/21/线段树分治学习笔记/

作者

xyfJASON

发布于

2020-03-21

更新于

2021-02-25

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×