devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构板子——自己用的

作者：代码探险家 | 2024-08-01 10:55:55

赞

踩

数据结构板子

1. 并查集

简便的路径压缩版
const int M = 1e5 + 10;
int fa[M];
void init(int n) { for (int i = 0; i <= n; i++) fa[i] = i; }

int findset(int x) {
    return x == fa[x] ? x : fa[x] = findset(fa[x]);
}

void unite(int a, int b) {
    fa[findset(a)] = findset(b);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
网络赛版
class UF {
public:
    int n;
    // 当前连通分量数目
    int cnt;
    vector<int> size;
    vector<int> parent;

    UF(int _n): n(_n + 1), cnt(_n + 1), size(_n + 1, 1), parent(_n + 1) {
        int i = 0;
        for (auto &x : parent) x = i++;
    }
    
    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --cnt;
        return true;
    }
    
    bool conn(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

  • 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

2. 树状数组

单点修改与区间查询
// 修改复杂度与查询复杂度O(logn)
// 修改复杂度与查询复杂度O(logn)
template<class T>
class fenwich{
    #define lowbit(x) ((x) & (-x))
    vector<T> v;
    int len;
    T get_pre(int i) {
        T res = 0;
        for(; i > 0; i -= lowbit(i)) res += v[i];
        return res;
    }
public:
    fenwich (int len) : v(len + 1, 0), len(len) {}
    void resize(int n, T x = 0) { v.resize(n + 1, x), len = n; }
    void modify(int i, T val) { // 单点修改，用此函数建树
        for (; i <= len; i += lowbit(i)) v[i] += val;
    }
    T get(int l, int r) { // 区间查询
        if (l > r) return 0;
        return get_pre(r) - get_pre(l - 1);
    }
    #undef lowbit
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
区间修改，区间查询
  1. 设 d [ i ] = a [ i ] − a [ i − 1 ] d[i] = a[i] - a[i - 1] d[i]=a[i]−a[i−1]
  2. 则 a [ x ] = ∑ i = 1 x d i a[ x ] = \sum_{i = 1}^{x}{d_i} a[x]=∑i=1x​di​
  3. 设 s u m [ x ] = ∑ i = 1 x a i sum[ x ] = \sum_{i = 1}^{x}{a_i} sum[x]=∑i=1x​ai​
  4. 即 s u m [ x ] = d [ 1 ] + d [ 1 ] + d [ 2 ] + d [ 1 ] + d [ 2 ] + d [ 3 ] + … … + d [ 1 ] + … … + d [ n ] sum[ x ] = d[1] + d[1] + d[2] + d[1] + d[2] + d[3] + …… + d[1] + ……+ d[n] sum[x]=d[1]+d[1]+d[2]+d[1]+d[2]+d[3]+……+d[1]+……+d[n]
  5. 化简得 s u m [ x ] = ∑ i = 1 x d i × ( n − i + 1 ) sum[ x ] = \sum_{i = 1}^{x}{d_i \times (n - i + 1)} sum[x]=∑i=1x​di​×(n−i+1)
  6. 得 s u m [ x ] = ( n + 1 ) × ∑ i = 1 x d i − ∑ i = 1 x i × d i sum[ x ] = (n + 1) \times \sum_{i = 1}^{x}{d_i} - \sum_{i = 1}^{x}{i \times d_i} sum[x]=(n+1)×∑i=1x​di​−∑i=1x​i×di​
  7. 固开两个树状数组，一个维护差分数组 d i d_i di​，一个维护 i × d i i \times d_i i×di​
template<class T>
class Fenwich{
    #define lowbit(x) ((x) & (-x))
    vector<T> d, id;
    int len;
    void update(int indx, T val, vector<T>& vt) {
        for (; indx <= len; indx += lowbit(indx)) vt[indx] += val;
    }
    T get_pre(int indx, vector<T>& vt) {
        T res = 0;
        for (; indx > 0; indx -= lowbit(indx)) res += vt[indx];
        return res;
    }
public:
    Fenwich(int n) : d(n + 1, 0), id(n + 1, 0), len(n) {}
    void resize(int n, T x = 0) {
        d.resize(n + 1, 0), id.resize(n + 1, 0);
        len = n;
    }
    void modify(int l, int r, T val) { // 区间修改，单点修改和建树也调用此函数
        update(l, val, d), update(r + 1, -val, d);
        update(l, val * l, id), update(r + 1, (-val) * (r + 1), id);
    }
    T get(int l, int r) {
        T res = get_pre(r, d) * (r + 1) - get_pre(r, id);
        res -= get_pre(l - 1, d) * l - get_pre(l - 1, id);
        return res;
    }
    #undef lowbit
};

  • 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

3. 线段树

精简版
// 宏
#define ls ((node) << 1)
#define rs (((node) << 1) | 1)
// 变量
const int N = 2e5 + 5;
ll seg[N << 2], lazy[N << 2], arr[N];
// 操作
ll op(ll a, ll b) { return a + b; }
// 题意不同，函数内部不同
void push_down(int l, int r, int node) {
    if (!lazy[node]) return; // 这里如果0也有意义的话多开一个数组标记
    int mid = (l + r) >> 1;
    lazy[ls] += lazy[node], lazy[rs] += lazy[node];
    seg[ls] += (mid - l + 1) * lazy[node];
    seg[rs] += (r - mid) * lazy[node];
    lazy[node] = 0;
}
// 初始化
void build(int l, int r, int node) {
    if (l == r) {
        seg[node] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
    seg[node] = op(seg[ls], seg[rs]);
}
// 单点修改
void update(int indx, ll v, int l, int r, int node) {
    if (l == r) { // 题意不同，这里更新操作不同
        seg[node] = v; 
        return;
    }
    int mid = (l + r) >> 1;
    if (indx <= mid) update(indx, v, l, mid, ls);
    else update(indx, v, mid + 1, r, rs);
    seg[node] = op(seg[ls], seg[rs]);
}
// 区间修改
void update(int ql, int qr, ll v, int l, int r, int node) {
    if (ql <= l && r <= qr) { // 题意不同，这里更新操作不同
        lazy[node] += v;
        seg[node] += (r - l + 1) * v;
        return;
    }
    push_down(l, r, node);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(ql, qr, v, l, mid, ls);
    if (qr > mid) update(ql, qr, v, mid + 1, r, rs);
    seg[node] = op(seg[ls], seg[rs]);
}
// 区间查找
ll get(int ql, int qr, int l, int r, int node) {
    if (ql <= l && r <= qr) return seg[node];
    push_down(l, r, node); // 保证单点的情况下这句话可以注释掉
    int mid = (l + r) >> 1;
    ll ret = 0; // 题意不同，初始化不同
    if (ql <= mid) ret = get(ql, qr, l, mid, ls);
    if (qr > mid) ret = op(get(ql, qr, mid + 1, r, rs), ret);
    return ret;
}
#undef ls
#undef rs

  • 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

4. ST表

const int M = 1e5 + 5;
int st[M][30], lg[M];
// st表预处理, 注意下标从1开始到n结束
void init(int *a, int n) {
	lg[0] = -1;
    for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1, st[i][0] = a[i];
    for (int j = 1; j <= lg[n]; ++j) {
        int k = 1 << (j - 1);
        for (int i = 1; i + k - 1 <= n; ++i) {
            st[i][j] = max(st[i][j - 1], st[i + k][j - 1]);
        }
    }
}
// 询问
// 尽可能让l + 2^(len) - 1接近r
int get(int l, int r) {
    int x = lg[r - l + 1];
    return max(st[l][x], st[r - (1 << x) + 1][x]);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

5. 分块

const int N = 1e5 + 5, M = 500;
#define ll long long
ll a[N];
int belong[N];
struct blocks {
    int l, r;
    ll lazy;
    blocks() : lazy(0){}
}b[M];
// 以下函数是基本不变的
void build(int n) {
    int siz = sqrt(n), cnt = n / siz;
    if (n % siz) ++cnt;
    for (int i = 1; i <= cnt; ++i) {
        b[i].l = (i - 1) * siz + 1;
        b[i].r = i * siz;
    }
    b[cnt].r = n;
    for (int i = 1; i <= n; ++i) belong[i] = (i - 1) / siz + 1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

6. 莫队

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int M = 1e5 + 10;
int n, m, block, arr[M], pos[M], ans[M], res;
struct MO{
    int l, r, k;
    MO(int l = 0, int r = 0, int k = 0) : l(l), r(r), k(k) {}
}q[M];

bool cmp(MO a, MO b) {
    if (pos[a.l] ^ pos[b.l]) {//不在同一个块
        return  pos[a.l] < pos[b.l];
    }
    if (pos[a.l] & 1) return a.r < b.r;
    return b.r < a.r;
}
void add(int x) {

}
void del(int x) {

}

void solve() {
    int l = 1, r = 0;
    for (int i = 0; i < m; i++) {
        while (l > q[i].l) add(--l);
        while (r < q[i].r) add(++r);
        while (l < q[i].l) del(l++);
        while (r > q[i].r) del(r--);
        ans[q[i].k] = res;//res根据题目意思来
    }
}
void init() {
    scanf("%d %d", &n, &m);
    block = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
        pos[i] = i / block;
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        q[i] = MO(l, r, i);
    }
    sort(q, q + m, cmp);
}

int main() {
    init();
    solve();
    return 0;
}

  • 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

7. 平衡树

fhq treap
// 洛谷板子题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <random>
#include <cctype>
inline long long IO() {}
using namespace std;
const int N = 4e5 + 10;
mt19937 rnd(233);
struct treap{
    int val, l, r, size, key;
}fhq[N];
int root, cnt;
inline void update(int now) {
    fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
}

int new_node(int val) {
    fhq[++cnt] = {.val = val, .l = 0, .r = 0, .size = 1, .key = rnd()};
    return cnt;
}
void split(int now, int val, int &x, int &y) {
    if (!now) { x = y = 0; return; }
    if (fhq[now].val <= val) x = now, split(fhq[now].r, val, fhq[now].r, y);
    else y = now, split(fhq[now].l, val, x, fhq[now].l);
    update(now);
}

int merge(int x, int y) {
    if (!x || !y) return x | y;
    // 大根堆
    if (fhq[x].key > fhq[y].key) { //右下角
        fhq[x].r = merge(fhq[x].r, y), update(x);
        return x;
    }
    // 左下角
    fhq[y].l = merge(x, fhq[y].l), update(y);
    return y;
}
// 插入
inline void insert(int val) {
    int x, y;
    split(root, val, x, y);
    root = merge(merge(x, new_node(val)), y);
}
// 按值删除
inline void del(int val) {
    int x, y, z;
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(fhq[y].l, fhq[y].r);
    root = merge(merge(x, y), z);
}
// 按值获取排名
inline int getrank(int val) {
    int x, y, ans;
    split(root, val - 1, x, y);
    ans = fhq[x].size + 1;
    root = merge(x, y);
    return ans;
}
// 按排名获取值
inline int getval(int rank) {
    int now = root;
    while (now) {
        if (fhq[fhq[now].l].size + 1 == rank) break;
        else if (fhq[fhq[now].l].size >= rank) now = fhq[now].l;
        else rank -= fhq[fhq[now].l].size + 1, now = fhq[now].r;
    }
    return fhq[now].val;
}
// 求前驱，即严格比val小的最大值
inline int pre(int val) {
    int x, y;
    split(root, val - 1, x, y);
    int now = x;
    while (fhq[now].r) now = fhq[now].r;
    root = merge(x, y);
    return fhq[now].val;
}
// 求后继，即严格比val大的最小值
inline int nxt(int val) {
    int x, y;
    split(root, val, x, y);
    int now = y;
    while (fhq[now].l) now = fhq[now].l;
    root = merge(x, y);
    return fhq[now].val;
}

int main() {
    int t = IO();
    while (t--) {
        int q = IO(), val = IO();
        if (q == 1) insert(val);
        else if (q == 2) del(val);
        else if (q == 3) printf("%d\n", getrank(val));
        else if (q == 4) printf("%d\n", getval(val));
        else if (q == 5) printf("%d\n", pre(val));
        else printf("%d\n", nxt(val));
    }
    return 0;
}

  • 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
spaly
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
const int N = 1e5 + 5;
template <class T>
class BST {
    static constexpr T inf_max = INT_MAX, inf_min = -inf_max; // LLONG_MAX
public:
    struct node {
        node *ch[2] = {NULL}, *p = NULL;
        int size, cnt, rev = 0;
        T val;
        void init(T v, node *fa) { p = fa, val = v, cnt = size = 1, ch[0] = ch[1] = NULL, rev = 0; }
        void clear() {
            val = cnt = size = rev = 0;
            if (this->ch[0]) delete this->ch[0], this->ch[0] = NULL;
            if (this->ch[1]) delete this->ch[1], this->ch[1] = NULL;
        }
    } *root = NULL;
    BST() { root=NULL, insert(inf_max), insert(inf_min); }
    ~BST() { clear(root); }
private:
#define sons(x, k) (x->ch[k] ? x->ch[k]->size : 0)
    void push_up(node* x) { x->size = sons(x, 0) + sons(x, 1) + x->cnt; }
    void push_down(node *x) {
        if (x && x->rev) {
            swap(x->ch[0], x->ch[1]);
            if (x->ch[0]) x->ch[0]->rev ^= 1;
            if (x->ch[1]) x->ch[1]->rev ^= 1;
            x->rev = 0;
        }
    }
    void rotate(node *x) { // 能进次函数，x必有父亲
        node *y = x->p, *z = y->p;
        int k = x == y->ch[1];
        if (x->ch[k ^ 1]) x->ch[k ^ 1]->p = y;
        if (z) z->ch[y == z->ch[1]] = x;
        y->ch[k] = x->ch[k ^ 1], x->p = z, x->ch[k ^ 1] = y, y->p = x;
        push_up(y), push_up(x);
    }
    void splay(node *x, node *p) { // 将x放到p的儿子的位置
        for (node *y = x->p, *z = NULL; y != p; rotate(x), y = x->p) {
            if ((z = y->p) != p) rotate((y->ch[1] == x) ^ (z->ch[1] == y) ? x : y);
        }
        if (!p) root = x;
    }
    node* FindKth(int k) { // 寻找排第k的数
        if (root->size < k || k < 1) return NULL;
        node *u = root;
        while (u) {
            push_down(u);
            if (sons(u, 0) >= k) u = u->ch[0];
            else if (sons(u, 0) + u->cnt >= k) return u;
            else k -= sons(u, 0) + u->cnt, u = u->ch[1];
        }
        return NULL;
    }
    void output(node *u) {
        if (!u) return;
        push_down(u);
        output(u->ch[0]);
        if (u->val < inf_max && u->val > inf_min) printf("%d ", u->val);
        output(u->ch[1]);
    }
    void clear(node *u) {
        if (u == NULL) return;
        clear(u->ch[0]), clear(u->ch[1]), u->clear();
    }
public:
    node* pre_next(T val, int f) { // 0:pre , 1:next
        find(val);
        if (val < root->val && f) return root;
        if (root->val < val && !f) return root;
        node *u = root->ch[f];
        while (u->ch[f ^ 1]) u = u->ch[f ^ 1];
        // splay(u, NULL); // 这里可以不用splay了，但如果找完之后需要查询排名，则可以直接splay，直接调用find_kth也行
        return u;
    }
    node* find_range(T l, T r) { // 寻找值为[l,r]区间的结点
        node *pre = pre_next(l, 0), *nxt = pre_next(r, 1);
        splay(pre, NULL), splay(nxt, pre);
        return nxt->ch[0];
    }
    int find(T val) { // 查找值为val 的值，找到则返回个数，否则返回0
        node *u = root;
        while (u->ch[u->val < val] && val != u->val) u = u->ch[u->val < val];
        splay(u, NULL);
        return u->val == val ? u->cnt : 0;
    }
    int insert(T val) { // 插入一个数，1表示新插入，0以前插入过
        node *u = root, *p = NULL;
        while (u && u->val != val) p = u, u = u->ch[u->val < val];
        if (u) u->cnt += 1;
        else {
            u = new node, u->init(val, p);
            if (p) p->ch[p->val < val] = u;
        }
        splay(u, NULL);
        return u->cnt == 1;
    }
    void erase(T val, int all) { // all = 1 表示彻底删除值为val的，否则删除1个，必须保证val存在，否则空指针错误
        node *del = find_range(val, val), *nxt = del->p;
        if (del->cnt > 1 && !all) del->cnt -= 1, splay(del, NULL);
        else delete nxt->ch[0], nxt->ch[0] = NULL;
    }
    node* find_kth(int k) { return FindKth(k + 1); } // 不包括负无穷，固找k+1
    node* lower_bound(T val) { return pre_next(val - 1, 1); }
    node* upper_bound(T val) { return pre_next(val, 1); }
    int find_rank(T val) { // 看看val在树中的排名，有多个返回最小的排名
        splay(pre_next(val - 1, 1), NULL);
        return root->ch[0] ? root->ch[0]->size : 1;
    }
    void reverse(int l, int r) { 
        node *L = find_kth(l - 1), *R = find_kth(r + 1);
        splay(L, NULL), splay(R, L);
        R->ch[0]->rev ^= 1;
    }
    void output() { output(root); }
    void clear() {
        clear(root), delete root, root = NULL;
        insert(inf_min), insert(inf_max); 
    }
#undef sons
};
auto main() -> int {
    BST<int> tree;
    int t;
    scanf("%d", &t);
    while (t--) {
        int x = 0, val;
        scanf("%d %d", &x, &val);
        if (x == 1) tree.insert(val);
        else if (x == 2) tree.erase(val, 0);
        else if (x == 3) printf("%d\n", tree.find_rank(val));
        else if (x == 4) printf("%d\n", tree.find_kth(val)->val);
        else if (x == 5) printf("%d\n", tree.pre_next(val, 0)->val);
        else printf("%d\n", tree.pre_next(val, 1)->val);
    }
    return 0;
}

  • 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

8. 左偏树

9. 主席树

  1. 主席树（静态）洛谷模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
inline long long IO() {} // 快读略
using namespace std;

/*************************************离散化********************************************/
// vt存放可用于查询原本的数（用离散化值），打表后用于查询离散化表（用下标）
vector<int> vt;
inline int get_id(const int &x) { return lower_bound(vt.begin(), vt.end(), x) - vt.begin() + 1; }
inline void erase_vt() {
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
}
// 打表, 注意，原数组下标要从1开始，返回离散化后的表大小
inline int id_table(int n, int *a, vector<int> &res) { 
    res.emplace_back(0);
    for (int i = 1; i <= n; ++i) res.emplace_back(get_id(a[i]));
    return vt.size();
}

/*************************************主席树********************************************/
const int N = 2e5 + 5;
struct nodes{
    int l, r, sum;
    nodes() : sum(0) {}
}hjt[N << 5];
int root[N], cnt; // 记录每个根结点的内存池编号， 内存池
int build(int l, int r) {
    int now = ++cnt; // 内存申请
    if (l < r) {
        int mid = (l + r) >> 1;
        hjt[now].l = build(l, mid);
        hjt[now].r = build(mid + 1, r);
    }
    return now;
}
// 插入新节点的操作
int update(int pre, int l, int r, int x) {
    int now = ++cnt; // 内存申请
    hjt[now] = hjt[pre], ++hjt[now].sum; // 继承
    if (l < r) { // 寻找拼接点
        int mid = (l + r) >> 1;
        if (x <= mid) hjt[now].l = update(hjt[now].l, l, mid, x); // 如果x在左边，则让当前新节点的左孩子接继承后的左孩子
        else hjt[now].r = update(hjt[now].r, mid + 1, r, x); // 否则同理
    }
    return now;
}
// 返回第qr版本的主席树 - 第ql版本的主席树， 注意返回的是离散化后的值
int get(int ql, int qr, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int dif = hjt[hjt[qr].l].sum - hjt[hjt[ql].l].sum;
    if (k <= dif) return get(hjt[ql].l, hjt[qr].l, l, mid, k); // 左孩子上
    return get(hjt[ql].r, hjt[qr].r, mid + 1, r, k - dif); // 右孩子上
}

/*************************************主函数********************************************/
int a[N];
int main() {
    int n = IO(), m = IO();
    for (int i = 1; i <= n; ++i) a[i] = IO(), vt.emplace_back(a[i]);
    erase_vt();
    vector<int> id;
    int siz = id_table(n, a, id);
    root[0] = build(1, siz);
    for (int i = 1; i <= n; ++i) root[i] = update(root[i - 1], 1, siz, id[i]);
    while (m--) {
        int l = IO(), r = IO(), k = IO();
        printf("%d\n", vt[get(root[l - 1], root[r], 1, siz, k) - 1]);
    }
    return 0;
}

  • 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

10. LCA

// 洛谷板子题
// 注意，尽量让结点编号从1开始
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#define ll long long
inline long long IO() {} // 快读略
using namespace std;
const int maxn = 5e5 + 5, maxm = 5e5 + 5;
const int INF = 0x3f3f3f3f;

int head[maxn], cnt;

struct edges {
    int to, next;
    void add(int t, int n) {
        to = t, next = n;
    }
}edge[maxm << 1]; //无向图则需要乘2

inline void add(int u, int v) {
    edge[++cnt].add(v, head[u]);
    head[u] = cnt;
}

int fa[maxn][35], dep[maxn], lg[maxn];
/* 另一种写法
void dfs(int u, int f) {
    deep[u] = deep[f] + 1;
    fa[u][0] = f;
    for (int i = 1; (1 << i) <= deep[u]; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int& v : mp[u]) {
        if (v ^ f) dfs(v, u);
    }
}

int lca(int a, int b) {
    if (deep[a] < deep[b]) swap(a, b);
    for (int i = 18; ~i; --i) if (deep[fa[a][i]] >= deep[b]) a = fa[a][i];
    if (a == b) return a;
    for (int i = 20; ~i; --i) {
        if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    }
    return fa[a][0];
}
*/
void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for (int i = 1; i <= lg[dep[u]]; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v ^ f) dfs(v, u);
    }
}
void init(int root, int n) { // 通过检查代码，反向51行dep[root] = -1没意义，具体细节以后填这个坑
    dep[root] = lg[0] = -1;
    memset(head, -1, sizeof head); cnt = 0;
    for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    while (dep[a] > dep[b]) a = fa[a][lg[dep[a] - dep[b]]];
    if (a == b) return a;
    for (int i = lg[dep[a]]; ~i; --i) {
        if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    }
    return fa[a][0];
}
int main() {
    
    int n = IO(), m = IO(), root = IO();
    init(root, n);
    for (int i = 1; i < n; ++i) {
        int u = IO(), v = IO();
        add(u, v), add(v, u);
    }
    dfs(root, 0);
    while (m--) {
        int a = IO(), b = IO();
        printf("%d\n", lca(a, b));
    }
    return 0;
}

  • 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

11. 树链剖分

// 洛谷板子题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
#include <bitset>
using namespace std;
#define ll long long

const int N = 1e5 + 5, M = 2e5 + 5;
const int maxn = 1e5 + 5, maxm = 2e5 + 5;
const int INF = 0x3f3f3f3f;

int head[maxn], cnt;

//初始化
void init() { memset(head, -1, sizeof head); cnt = -1; }

struct edges {
    int to, next;
    void add(int t, int n) {
        to = t, next = n;
    }
}edge[maxm << 1]; //无向图则需要乘2

inline void add(int u, int v) {
    edge[++cnt].add(v, head[u]);
    head[u] = cnt;
}

/*******************************树链剖分**********************************/
int fa[N], dep[N], siz[N], son[N];
void dfs1(int u, int f) {
    fa[u] = f, siz[u] = 1;
    dep[u] = dep[f] + 1;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v; // 找重儿子
    }
}
int v[N]; // 点上的权值
int tim, dfn[N], top[N], w[N]; // w的下标是时间戳，对应的是相应时间戳上的点的点权
void dfs2(int u, int t) {
    dfn[u] = ++tim, top[u] = t;
    w[tim] = v[u];
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
/*******************************线段树******************************/
inline int ls(const int& x) { return x << 1;}
inline int rs(const int& x) { return x << 1 | 1;}
ll seg[N << 2], lazy[N << 2], p;
int n, m;
inline ll op(const ll& a, const ll& b) {
    // seg[x] = max(seg[ls(x)], seg[rs(x)]);
    return (a + b) % p;
}
inline void push_down(const int& l, const int& r, const int& node) {
    if (!lazy[node]) return;
    lazy[ls(node)] += lazy[node], lazy[rs(node)] += lazy[node];
    lazy[ls(node)] %= p, lazy[rs(node)] %= p;
    int mid = (l + r) >> 1;
    seg[ls(node)] = (lazy[node] * (mid - l + 1) + seg[ls(node)]) % p;
    seg[rs(node)] = (lazy[node] * (r - mid) + seg[rs(node)]) % p;
    lazy[node] = 0;
}

void build(int l, int r, int node = 1) {
    if (l == r) {
        seg[node] = w[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls(node)), build(mid + 1, r, rs(node));
    seg[node] = op(seg[ls(node)], seg[rs(node)]);
}

void update(int ql, int qr, ll x, int l = 1, int r = n, int node = 1) {
    if (ql <= l && r <= qr) {
        lazy[node] = (lazy[node] + x) % p;
        seg[node] = (seg[node] + (r - l + 1) * x) % p;
        return;
    }
    push_down(l, r, node);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(ql, qr, x, l, mid, ls(node));
    if (qr > mid) update(ql, qr, x, mid + 1, r, rs(node));
    seg[node] = op(seg[ls(node)], seg[rs(node)]);
}

int get(int ql, int qr, int l = 1, int r = n, int node = 1) {
    if (ql <= l && r <= qr) return seg[node];
    push_down(l, r, node);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res = get(ql, qr, l, mid, ls(node));
    if (qr > mid) res = op(res, get(ql, qr, mid + 1, r, rs(node)));
    return res;
}
/********************************树上操作**********************************/
void update_chain(int x, int y, ll z) {// 将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(dfn[x], dfn[y], z);
}

ll get_chain(int x, int y) {//求树从 x 到 y 结点最短路径上所有节点的值之和。
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = op(res, get(dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return op(res, get(dfn[x], dfn[y]));
}

void update_son(int x, ll z) {// 将以 x 为根节点的子树内所有节点值都加上 z
    update(dfn[x], dfn[x] + siz[x] - 1, z);
}
ll get_son(int x) {// 求以 x 为根节点的子树内所有节点值之和
    return get(dfn[x], dfn[x] + siz[x] - 1);
}
/********************************主函数************************************/

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0), cin.tie(0); 
    init();
    int root;
    cin >> n >> m >> root >> p;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    dfs1(root, root), dfs2(root, root);
    build(1, n);
    while (m--) {
        int q, x, y, z;
        cin >> q >> x;
        if (q == 1) {
            cin >> y >> z;
            update_chain(x, y, z % p);
        } else if (q == 2) {
            cin >> y;
            cout << get_chain(x, y) << endl;
        } else if (q == 3) {
            cin >> z;
            update_son(x, z);
        } else {
            cout << get_son(x) << endl;
        }
    }
    return 0;
}

  • 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
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/913708
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号