Skip to content

Latest commit

 

History

History
309 lines (262 loc) · 6.15 KB

1-数据结构.md

File metadata and controls

309 lines (262 loc) · 6.15 KB
Raw

数据结构

树状数组

normal

template<typename T>
struct Bit {
    inline int lowbit(int i) { return i & (-i); }

    T dat[N];

    void clear(int n) {
        memset(dat, 0, sizeof(T) * (n + 1));
    }

    inline void add(int i, T x) {
        for (; i<N; i+=lowbit(i))
            dat[i] += x;
    }

    inline T sum(int i) {
        T res = 0;
        for (; i; i-=lowbit(i))
            res += dat[i];
        return res;
    }
};

线段树

单点

  • 注意把骚操作去掉
template<typename T>
struct node {
    int id;
    T v;
    node(int id=-1, T v=-0x3f3f3f3f) :id(id), v(v) {}

    bool operator < (const node &other) const {
        return v < other.v;
    }
};

template<typename T>
struct segT {
    node<T> dat[M << 2];
    int nn;

    inline void pu(int rt) {
        dat[rt] = max(dat[rt << 1], dat[rt << 1 | 1]);
    }

    void init(int n) {
        nn = 1;
        while (nn < n) nn <<= 1;
        for (int i=1; i<=n; ++i)
            dat[i + nn - 1] = node<T>(i);
        for (int i=nn+n; i<2*nn; ++i)
            dat[i] = node<T>();
        for (int i=nn-1; i>=1; --i)
            pu(i);
    }

    inline void u(int i, T x) {
        i += nn;
        if (dat[i].v >= x)
            return;
        dat[i].v = x;
        for (i>>=1; i; i>>=1)
            pu(i);
    }

    int L, R;
    node<T> q(int l, int r, int rt) {
        // dbg(l, r, rt, L, R, dat[rt].v);
        if (L <= l && r <= R)
            return dat[rt];
        int m = (l+r) >> 1;
        node<T> v1, v2;
        if (L <= m) v1 = q(l, m, rt<<1);
        if (m+1<=R) v2 = q(m+1, r, rt<<1|1);
        return max(v1, v2);
    }

    inline node<T> q(int l, int r) {
        ++l; ++r;
        if (l > r)
            return node<T>();
        L = l; R = r;
        return q(1, nn, 1);
    }
};

lazy

template<typename T>
struct snode {
    int id;
    T v;
    snode (int id=0, T v=0):id(id), v(v) {}

    bool operator < (const snode &other) const {
        if (v != other.v) return v < other.v;
        else return id < other.id;
    }
};

// template<typename T>
// typedef snode T;
template<typename T>
struct segT {
    T dat[N << 2];
    LL lazy[N << 2];
    int nn;

    void init(int n) {
        nn = 1;
        while (nn < n) 
            nn <<= 1;

        for (int i=1; i<=n; ++i)
            dat[i+nn-1] = snode<int>(i, 0);
        for (int i=nn+n; i<2*nn; ++i)
            dat[i] = snode<int>(-1, -INF);
        for (int i=nn-1; i>=0; --i)
            pu(i);
    }

    inline void pd(int rt) {
        if (lazy[rt]) {
            int ls = rt << 1, rs = rt << 1 | 1;
            dat[ls].v = dat[rs].v = lazy[ls] = lazy[rs] = lazy[rt];
            lazy[rt] = 0;
        }
    }

    inline void pu(int rt) {
        dat[rt] = max(dat[rt<<1], dat[rt<<1|1]);
    }

    
    int L, R;

    void u(int l, int r, int rt, int v) {
        if (L <= l && r <= R) {
            dat[rt].v = lazy[rt] = v;
            return;
        }
        int m = (l+r) >> 1;
        pd(rt);
        if (L <= m) u(l, m, rt<<1, v);
        if (m+1<=R) u(m+1, r, rt<<1|1, v);
        pu(rt);
    }
    T q(int l, int r, int rt) {
        // dbg(l, r, rt, dat[rt].v);
        if (L <= l && r <= R) {
            return dat[rt];
        }
        int m = (l + r) >> 1; pd(rt);
        T v1 = snode<int>(-1, -INF), v2 = snode<int>(-1, -INF);
        if (L <= m) v1 = q(l, m, rt<<1);
        if (m+1<=R) v2 = q(m+1, r, rt<<1|1);
        pu(rt);
        return max(v1, v2);
    }
    void u(int l, int r, int x) {
        // dbg(l, r, x);
        L = l;
        R = r;
        u(1, nn, 1, x);
    }
    T q(int l, int r) {
        L = l;
        R = r;
        return q(1, nn, 1);
    }
};

segT<snode<int>> seg;

pbds

头文件：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

hash

用于替代 unordered_map 整数插入操作 stl 3.6s, pbds 探测法 2s

gp_hash_table<int, int> mp;
cc_hash_table<int, int> mp2;

tree

  1. 用来替代 map，第二个类型填 null_type 就是 set
  2. key 会 自动去重

example:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
tree<int, int, greater<int>, rb_tree_tag, tree_order_statistics_node_update> tr;

/*
int key 类型 int value 类型，可用 null_type 替代
less<int> 表示 key 从小到大，对应 greater<int>
rb_tree_tag 红黑树，可用 splay_tree_tag 替代
insert erase order_by_key find_by_order
lower_bound upper_bound
a.join(b) 将 b 并入 a
a.split(v, b) 将 key <= v 保留给 a，其他给 b
*/

int main(int argc, char const *argv[])
{
    tr.insert(make_pair(2, 2));
    tr.insert(make_pair(1, 1));
    tr.find(1)->second ++;
    for (auto x : tr)
        cout << x.first << ' ' << x.second << endl;
    puts("===");
    tr.insert(make_pair(1, 3));
    for (auto x : tr)
        cout << x.first << ' ' << x.second << endl;
    puts("===");
    tr.erase(1);
    for (int i=0; i<tr.size(); ++i)
    {
        auto p = tr.find_by_order(i);
        cout << p->first << ' ' << p->second << ' ' << tr.order_of_key(p->first) << endl;
    }
    puts("===");
    auto x = tr.lower_bound(1);
    cout << (x == tr.end()) << endl;
    return 0;
}
/* outcome
2 2
1 2
===
2 2
1 2
===
2 2 0
===
1
*/

ST 表

standard

int p2[10], Log[N];
struct ST {
    static const int SP = 10;
    int dat[SP][N];
    void init() {
        p2[0] = 1;
        for (int i=1; i<SP; ++i)
            p2[i] = p2[i-1] << 1;
        Log[1] = 0;
        for (int i=2; i<N; ++i)
            Log[i] = Log[i >> 1] + 1;
    }
    void init(int a[], int n)
    {
        for (int i=1; i<=n; ++i)
            dat[0][i] = a[i];
        for (int i=1; i<SP; ++i)
            for (int j=1; j<=n; ++j)
                dat[i][j] = min(dat[i-1][j], dat[i-1][j + p2[i-1]]);
    }
    int q(int l, int r) {
        int Lg = Log[r-l+1];
        return min(dat[Lg][l], dat[Lg][r-p2[Lg]+1]);
    }
} ds[N];