数据结构

fsjhhh Lv2
  2023-11-22 16:41:04 2023-11-22 16:41:04 创建   2024-08-09 14:43:26 2024-08-09 14:43:26 更新    

树状数组

  • 区间求和

    数组形式

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
const int N = 5e5 + 10;
int n;
int tr[N];

int lowbit(int x) {
    // lowbit返回x二进制最后一个1的位置
    // 树状数组中x + lowbit(x) 是x父节点的位置 
    return x & (-x);
}

void modify(int u, int x) {
    // 修改u以及u的负节点（单点修改）
    for (int i = u; i <= n; i += lowbit(i)) {
        tr[i] += x;
    }
}

int query(int u) {
    int ans = 0;
    // 查询u以及u的子节点
    for (int i = u; i; i -= lowbit(i)) {
        ans += tr[i];
    }
    return ans;
}

​ 版

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
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
 
    Fenwick(int n_ = 0) {
        init(n_);
    }
 
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
 
    void add(int x, const T &v) { 
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
 
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
 
    T rangeSum(int l, int r) { // [l, r)
        return sum(r) - sum(l);
    }
};

例题：洛谷P3374 , P3368
单点修改和区间查询 与 区间修改和单点查询
中的查询相当于前缀和中的
所以，对于区间修改可以按照差分的思想优化, 例如：在 中每个数加上 , 就是

  • 区间求最大值，最小值

洛谷P2880 

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
const int N = 2e5 + 10;
int n;
int a[N], tr_max[N], tr_min[N];

int lowbit(int x) {
    return x & (-x);
}

void modify(int u, int x) {
    // 单点修改
    for (int i = u; i <= n; i += lowbit(i)) {
        tr_max[i] = std::max(tr_max[i], x);
        tr_min[i] = std::min(tr_min[i], x);
    }
}

int query_max(int l, int r) {
    // 区间查询最大值
    if (r > l) {
        if (r - lowbit(r) > l) {
            return std::max(tr_max[r], query_max(l, r - lowbit(r)));
        } else {
            return std::max(a[r], query_max(l, r - 1));
        }
    } else {
        return a[l];
    }
}

int query_min(int l, int r) {
    // 区间查询最小值
    if (r > l) {
        if (r - lowbit(r) > l) {
            return std::min(tr_min[r], query_min(l, r - lowbit(r)));
        } else {
            return std::min(a[r], query_min(l, r - 1));
        }
    } else {
        return a[l];
    }
}

线段树

洛谷P3372

区间求和

  • 区间为的线段树
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
struct Node {
    int l, r;
    int sum = 0;
    int lazy = 0;
};

struct SegmentTree {
    std::vector<Node> tr;

    SegmentTree() {}
    SegmentTree(int n) {
        init(n);
    }

    void init(int n) {
        tr.resize(4 * (n + 1));
    }

    void merge_node(Node& res, Node x, Node y) {
        res.sum = x.sum + y.sum;
    }

    void push_up(int u) {
        merge_node(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }

    void build(int u, int l, int r, std::vector<int>& w) {
        if (l == r) {
            tr[u].l = tr[u].r = r;
            tr[u].lazy = 0;
            tr[u].sum = w[l];
            return ;
        }
        tr[u].l = l;
        tr[u].r = r;
        tr[u].lazy = 0;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, w);
        build(u << 1 | 1, mid + 1, r, w);
        push_up(u);
    }

    void push_down(int u) {
        if (!tr[u].lazy) {
            return ;
        }
        tr[u << 1].lazy += tr[u].lazy;
        tr[u << 1].sum += tr[u].lazy * (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].lazy += tr[u].lazy;
        tr[u << 1 | 1].sum += tr[u].lazy * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
        tr[u].lazy = 0;
    }

    void modify(int u, int l, int r, int x) {
        if (l <= tr[u].l && r >= tr[u].r) {
            tr[u].lazy += x;
            tr[u].sum += x * (tr[u].r - tr[u].l + 1);
            return ;
        }
        push_down(u); // 单点修改可去掉
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) {
            modify(u << 1, l, r, x);
        }
        if (r > mid) {
            modify(u << 1 | 1, l, r, x);
        }
        push_up(u);
    }

    Node query(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) {
            return tr[u];
        }
        push_down(u); /// 单点修改可去掉
        bool ok = false;
        int mid = (tr[u].l + tr[u].r) >> 1;
        Node ans;
        if (l <= mid) {
            ok = true;
            ans = query(u << 1, l, r);
        }
        if (r > mid) {
            if (!ok) {
                ans = query(u << 1 | 1, l, r);
            } else {
                Node res = query(u << 1 | 1, l, r);
                merge_node(ans, ans, res);
            }
        }
        push_up(u);
        return ans;
    }

};

  • 区间为的线段树

    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
    struct Node {
        int l, r; // 区间为[l, r)
        LL sum = 0;
        LL lazy = 0;
    };

    struct SegmentTree {
        std::vector<Node> tr;

        SegmentTree() {}
        SegmentTree(int n) {
            init(n);
        }

        void init(int n) {
            tr.resize(4 * (n + 1));
        }

        void merge_node(Node& res, Node x, Node y) {
            res.sum = x.sum + y.sum;
        }

        void push_up(int u) {
            merge_node(tr[u], tr[u << 1], tr[u << 1 | 1]);
        }

        void build(int u, int l, int r, std::vector<int>& w) { // 建树区间为[l, r)
            tr[u].l = l;
            tr[u].r = r;
            if (r - l == 1) {
                tr[u].lazy = 0;
                tr[u].sum = w[l];
                return ;
            }
            tr[u].lazy = 0;
            int mid = (l + r) >> 1;
            build(u << 1, l, mid, w);
            build(u << 1 | 1, mid, r, w);
            push_up(u);
        }

        void push_down(int u) {
            if (!tr[u].lazy) {
                return ;
            }
            tr[u << 1].lazy += tr[u].lazy;
            tr[u << 1].sum += tr[u].lazy * (tr[u << 1].r - tr[u << 1].l);
            tr[u << 1 | 1].lazy += tr[u].lazy;
            tr[u << 1 | 1].sum += tr[u].lazy * (tr[u << 1 | 1].r - tr[u << 1 | 1].l);
            tr[u].lazy = 0;
        }

        void modify(int u, int l, int r, int x) { // 修改区间为[l, r)
            if (tr[u].l >= r || tr[u].r <= l) {
                return ;
            }
            if (tr[u].l >= l && tr[u].r <= r) {
                tr[u].lazy += x;
                tr[u].sum += x * (tr[u].r - tr[u].l);
                return ;
            }
            push_down(u); // 单点修改可去掉
            modify(u << 1, l, r, x);
            modify(u << 1 | 1, l, r, x);
            push_up(u);
        }

        Node query(int u, int l, int r) { // 查询区间为[l, r)
            if (tr[u].l >= r || tr[u].r <= l) {
                return Node();
            }
            if (l <= tr[u].l && r >= tr[u].r) {
                return tr[u];
            }
            push_down(u); // 单点修改可去掉
            Node ans;
            merge_node(ans, query(u << 1, l, r), query(u << 1 | 1, l, r));
            push_up(u);
            return ans;
        }

    };

扫描线

洛谷P1502 

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
const int N = 1e5 + 10;

int n, W, H;
struct matrix {
    int l, r, h;
    int val;
} mat[N << 2];

struct node {
    int l, r;
    int lazy;
    int maxx;
} tr[N << 2];

std::vector<int> all;

void init() {
    all.clear();
    memset(mat, 0, sizeof mat);
    memset(tr, 0, sizeof tr);
}

int find(int x) {
    int l = 0, r = all.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (all[mid] >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return r + 1;
}

void push_up(int u) {
    tr[u].maxx = std::max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u].l = l, tr[u].r = r;
        tr[u].lazy = 0;
        tr[u].maxx = 0;
        return ;
    }

    tr[u].l = l, tr[u].r = r;
    tr[u].lazy = 0;

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void push_down(int u) {
    tr[u << 1].maxx += tr[u].lazy;
    tr[u << 1 | 1].maxx += tr[u].lazy;
    tr[u << 1].lazy += tr[u].lazy;
    tr[u << 1 | 1].lazy += tr[u].lazy;
    tr[u].lazy = 0;
}

void modify(int u, int l, int r, int w) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].maxx += w;
        tr[u].lazy += w;
        return ;
    }
    push_down(u);

    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) {
        modify(u << 1, l, r, w);
    }
    if (r > mid) {
        modify(u << 1 | 1, l, r, w);
    }

    push_up(u);

}


void solve() {
    init();

    std::cin >> n >> H >> W;

    for (int i = 1; i <= n; i++) {
        int x, y, l;
        std::cin >> x >> y >> l;
        mat[(i << 1) - 1] = {y, y + W - 1, x, l};
        mat[(i << 1)] = {y, y + W - 1, x + H - 1, -l};
        all.push_back(y);
        all.push_back(y + W - 1);
    }

    n <<= 1;

    std::sort(all.begin(), all.end());
    std::sort(mat + 1, mat + n + 1, [&](matrix a, matrix b) -> bool {
        if (a.h == b.h) {
            return a.val > b.val;
        }
        return a.h < b.h;
    });
    all.erase(std::unique(all.begin(), all.end()), all.end());

    for (int i = 1; i <= n; i++) {
        int l1 = find(mat[i].l);
        int r1 = find(mat[i].r);
        std::cerr << l1 << " " << r1 << "\n";
        mat[i].l = l1;
        mat[i].r = r1;
    }
    std::cerr << "\n";

    build(1, 1, all.size());
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        modify(1, mat[i].l, mat[i].r, mat[i].val);
        ans = std::max(ans, tr[1].maxx);
    }

    std::cout << ans << "\n";

}

动态开点线段树

洛谷P3369 

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
const int N = 1e6 + 10, range = 1e7 + 5;

struct Node {
    int l = 0, r = 0;
    int cnt = 0;
} tr[N * 30];
int root[N], idx = 2;

void push_down(int u) {
    if (!tr[u].l) {
        tr[u].l = idx ++ ;
    }
    if (!tr[u].r) {
        tr[u].r = idx ++ ;
    }
}

void push_up(int u) {
    tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}

void modify(int u, int l, int r, int pos, int value) {
    if (l == r) {
        tr[u].cnt += value;
        return ;
    }
    int mid = (l + r) >> 1;
    push_down(u);
    if (pos <= mid) {
        modify(tr[u].l, l, mid, pos, value);
    } else {
        modify(tr[u].r, mid + 1, r, pos, value);
    }
    push_up(u);
}

void add(int pos, int value) {
    modify(1, -range, range, pos, value);
}

void insert(int x) {
    add(x, 1);
}

void remove(int x) {
    add(x, -1);
}

int query1(int u, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        return tr[u].cnt;
    }
    if (l > R || r < L) {
        return 0;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    return query1(tr[u].l, l, mid, L, R) + query1(tr[u].r, mid + 1, r, L, R);
}

int query2(int u, int l, int r, int x) {
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    if (x <= tr[tr[u].l].cnt) {
        return query2(tr[u].l, l, mid, x);
    } else {
        return query2(tr[u].r, mid + 1, r, x - tr[tr[u].l].cnt);
    }
}

int query3(int x) {
    int t = query1(1, -range, range, -range, x - 1);
    return query2(1, -range, range, t); 
}

int query4(int x) {
    int t = query1(1, -range, range, -range, x) + 1;
    return query2(1, -range, range, t);
}

void solve() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int op, x;
        std::cin >> op >> x;
        if (op == 1) {
            insert(x);
        } else if(op == 2) {
            remove(x);
        } else if (op == 3) {
            std::cout << query1(1, -range, range, -range, x - 1) + 1 << "\n";
        } else if (op == 4) {
            std::cout << query2(1, -range, range, x) << "\n";
        } else if (op == 5) {
            std::cout << query3(x) << "\n";
        } else {
            std::cout << query4(x) << "\n";
        }
    }
}

主席树

可持久化线段树

洛谷P3919 

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
const int N = 1e6 + 10;

struct Node {
    int l, r;
    int val;
} tr[N * 30];
int root[N], idx;

int n, m;
int a[N];

int build(int l, int r) {
    int p = ++ idx;
    if (l == r) {
        tr[p].val = a[l];
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].val = 0;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}

int modify(int u, int l, int r, int loc, int value) {
    int p = ++ idx;
    tr[p] = tr[u];
    if (l == r && l == loc) {
        tr[p].val = value;
        return p;
    }
    int mid = (l + r) >> 1;
    if (loc <= mid) {
        tr[p].l = modify(tr[u].l, l, mid, loc, value);
    } else {
        tr[p].r = modify(tr[u].r, mid + 1, r, loc, value);
    }
    return p;
}

int query(int u, int l, int r, int loc) {
    if (l == r && l == loc) {
        return tr[u].val;
    }
    int mid = (l + r) >> 1;
    if (loc <= mid) {
        return query(tr[u].l, l, mid, loc);
    } else {
        return query(tr[u].r, mid + 1, r, loc);
    }
}

void solve() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    root[0] = build(1, n);
    for (int i = 1; i <= m; i++) {
        int v, op, loc, value;
        std::cin >> v >> op >> loc;
        if (op == 1) {
            std::cin >> value;
            root[i] = modify(root[v], 1, n, loc, value);
        } else {
            root[i] = root[v];
            std::cout << query(root[v], 1, n, loc) << "\n";
        }
    }
    
}

可持久化线段树

洛谷P3834 

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
// 离线主席树
const int N = 2e5 + 10;
struct Node {
    int l, r;
    int cnt;
} tr[N * 30];

int root[N], idx;

std::vector<int> nums;
int n, m;
int a[N];

int find(int x) {
    return std::lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

void push_up(int u) {
    tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}

int build(int l, int r) {
    int p = ++ idx;
    if (l == r) {
        tr[p].cnt = 0;
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    push_up(p);
    return p;
}

int modify(int u, int l, int r, int x) {
    int p = ++ idx;
    tr[p] = tr[u];
    if (l == r) {
        tr[p].cnt ++ ;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        tr[p].l = modify(tr[u].l, l, mid, x);
    } else {
        tr[p].r = modify(tr[u].r, mid + 1, r, x);
    }
    push_up(p);
    return p;
}

int query(int p, int q, int l, int r, int x) {
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    int count = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    if (x <= count) {
        return query(tr[p].l, tr[q].l, l, mid, x);
    } else {
        return query(tr[p].r, tr[q].r, mid + 1, r, x - count);
    }
}

void solve() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        nums.push_back(a[i]);
    }
    
    // 离散化
    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

    int cn = nums.size() - 1;

    root[0] = build(0, cn);
    for (int i = 1; i <= n; i++) {
        root[i] = modify(root[i - 1], 0, cn, find(a[i]));
    }

    while (m -- ) {
        int l, r, k;
        std::cin >> l >> r >> k;
        std::cout << nums[query(root[l - 1], root[r], 0, cn, k)] << "\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
// 二分在线版（XyeeCheng）
const int N = 2e5 + 5;
const int M = 1e6 + 5;

struct node
{
    int sum = 0;
    int l = 0, r = 0;
} tree[M * 30];

#define ls(x) (tree[x].l)
#define rs(x) (tree[x].r)
#define sum(x) tree[x].sum
int tot = 1;
int root[N], a[N], n, m;

void pushup(int x)
{
    sum(x) = sum(ls(x)) + sum(rs(x));
}

void update(int last, int now, int pos, int k, int l, int r)
{
    //过去的节点 现在的节点 修改的位置，k ，当前节点表示的区间[l,r]
    if (l == r)
    {
        sum(now) = sum(last) + k;
    }
    else
    {
        ls(now) = ls(last), rs(now) = rs(last);
        int mid = (l + r - 1) / 2;
        if (pos <= mid)
            ls(now) = ++tot, update(ls(last), ls(now), pos, k, l, mid);
        else
            rs(now) = ++tot, update(rs(last), rs(now), pos, k, mid + 1, r);
        pushup(now);
    }
}

const int up = 1e9 + 5;
const int down = -(1e9 + 5);

void update(int last, int now, int pos, int k)
{
    update(last, now, pos, k, down, up);
}

int kth(int last, int now, int k, int l, int r)
{
    if (l == r)
        return l;
    int mid = (l + r - 1) / 2;
    int val = sum(ls(now)) - sum(ls(last));
    if (val >= k)
        return kth(ls(last), ls(now), k, l, mid);
    else
        return kth(rs(last), rs(now), k - val, mid + 1, r);
}

int kth(int last, int now, int k)
{
    return kth(last, now, k, down, up);
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        root[i] = ++tot;
        update(root[i - 1], root[i], a[i], 1);
    }
    while (m--)
    {
        int L, R, k;
        cin >> L >> R >> k;
        cout << kth(root[L - 1], root[R], k) << endl;
    }
}

可持久化线段树

求区间mex

洛谷P4137 

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
const int N = 2e5 + 10;
struct Node {
    int l, r;
    int minn;
} tr[N * 30];
int root[N], idx;
int a[N], n, m;

void push_up(int u) {
    tr[u].minn = std::min(tr[tr[u].l].minn, tr[tr[u].r].minn);
}

int build(int l, int r) {
    int p = ++ idx;
    if (l == r) {
        tr[p].minn = 0;
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    push_up(p);
    return p;
}

int modify(int u, int l, int r, int x, int t) {
    int p = ++ idx;
    tr[p] = tr[u];
    if (l == r) {
        tr[p].minn = t;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        tr[p].l = modify(tr[u].l, l, mid, x, t);
    } else {
        tr[p].r = modify(tr[u].r, mid + 1, r, x, t);
    }
    push_up(p);
    return p;
}

int query(int u, int l, int r, int x) {
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    if (x > tr[tr[u].l].minn) {
        return query(tr[u].l, l, mid, x);
    } else {
        return query(tr[u].r, mid + 1, r, x);
    }
    push_up(u);
}

void solve() {
    std::cin >> n >> m;
    int z = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        z = std::max(z, a[i]);
    }

    root[0] = build(0, z + 1);

    for (int i = 1; i <= n; i++) {
        root[i] = modify(root[i - 1], 0, z + 1, a[i], i);
    }

    while (m -- ) {
        int l, r;
        std::cin >> l >> r;
        std::cout << query(root[r], 0, z + 1, l) << "\n";
    }

}
  • 标题: 数据结构
  • 作者: fsjhhh
  • 创建于 : 2023-11-22 16:41:04
  • 更新于 : 2024-08-09 14:43:26
  • 链接: https://fsjhhh.github.io/2023/11/22/数据结构/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
数据结构
  1. 树状数组
  2. 线段树
  3. 扫描线
  4. 动态开点线段树
  5. 主席树