实用数据结构和算法

发表于 更新于

一、数据结构

1、ST表

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
template<typename T, typename F>
struct disjoint_sparse_table {
    int n;
    vector<int> log2;
    vector<vector<T>> mat;
    F func;
    disjoint_sparse_table(const vector<T>& arr, const F& f) : n(int(arr.size())), func(f) {
        build_log2();
        mat.push_back(arr);
        int k = log2[n];
        for (int i = 1; i <= k; ++i) {
            mat.emplace_back(n);
            for (int j = 0; j < n - (1 << (i - 1)); ++j) {
                mat[i][j] = func(mat[i - 1][j], mat[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    void build_log2() {
        log2.resize(n + 5, 0);
        log2[1] = 0;
        log2[2] = 1;
        for (int i = 3; i <= n; ++i) log2[i] = log2[i >> 1] + 1;
    }
    T query(int l, int r) {
        int k = log2[r - l + 1];
        return func(mat[k][l], mat[k][r - (1 << k) + 1]);
    }
};
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
// https://vjudge.net/problem/POJ-3264
using namespace std;
const int maxn = 100010;
int FA[maxn][18];
int FB[maxn][18];
int Log2[maxn];

inline int read()
{
    int x=0,f=1;int ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for(int i = 3; i < maxn; ++i) Log2[i] = Log2[i >> 1] + 1;
}
int Max(int a, int b) {
    return a > b ? a : b;
}
int Min(int a, int b){
    return a < b ? a: b;
}
int Query(int l, int r){
    int k = Log2[r - l + 1];
    int a = Max(FA[l][k], FA[r-(1<<k) + 1][k]);
    int b = Min(FB[l][k], FB[r-(1<<k) + 1][k]);
    return a - b;
}


int main() {
    int m, n, k;
    pre();
    m = read();
    n = read();
    k = Log2[m];
    for (int i = 0; i < m; ++i) FA[i][0] = FB[i][0]= read();
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j < m - (1 << (i - 1)); ++j)
            FA[j][i] = Max(FA[j][i - 1], FA[j + (1 << (i - 1))][i - 1]),
            FB[j][i] = Min(FB[j][i - 1], FB[j + (1 << (i - 1))][i - 1]);
    }
    for(int i = 0; i < n; ++i){
        if(i != 0) puts("");
        int l = read() - 1, r = read() - 1;
        printf("%d", Query(l, r));
    }
    return 0;
}

2、求TopK的数据结构

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
// https://leetcode.cn/problems/find-number-of-coins-to-place-in-tree-nodes/
// 保存最小的N个数字
template<int N>
struct T120A {
    int arr[N];
    int cnt = 0;
    T120A() {
        for (int i = 0; i < N; ++i) arr[i] = INT_MAX;
    }
    void add(int x) {
        int i = 0, j = N - 2;
        while (i < N && x >= arr[i]) ++i;
        if (i == N) return;
        while (j >= i) arr[j + 1] = arr[j], --j;
        arr[i] = x;
        if (cnt < N) ++cnt;
       // for (int k = 0; k < cnt; ++k) printf("%2d ", arr[k]); puts("");
    }
};
// 保存最大的N个数字
template<int N>
struct T120B {
    int arr[N];
    int cnt = 0;
    T120B() {
        for (int i = 0; i < N; ++i) arr[i] = INT_MIN;
    }
    void add(int x) {
        int i = 0, j = N - 2;
        while (i < N && x <= arr[i]) ++i;
        if (i == N) return;
        while (j >= i) arr[j + 1] = arr[j], --j;
        arr[i] = x;
        if (cnt < N) ++cnt;
    }
};

3、二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 不要使用C++的类 存在虚函数指针 可能会被卡常
// 根据情况流式处理数据减少数据拷贝
// https://leetcode.cn/problems/range-sum-query-2d-immutable/description/
void makePresum(vector<vector<int>>& arr) {
	int n = arr.size(), m = arr[0].size();
	for (int i = 1; i < m; ++i) arr[0][i] += arr[0][i - 1];
	for (int i = 1; i < n; ++i) {
		arr[i][0] += arr[i - 1][0];
		for (int j = 1; j < m; ++j)
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
	}
}
int _getVal(vector<vector<int>>& arr, int a, int b) {
	if (a < 0 || b < 0) return 0;
	return arr[a][b];
}
int sumRegion(vector<vector<int>>& arr, int a, int b, int c, int d) {
	return _getVal(arr, c, d) - _getVal(arr, c, b - 1) - _getVal(arr, a - 1, d)
		+ _getVal(arr, a - 1, b - 1);
}
int main() 
{
	return 0;
}

3、快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
// https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/description/
const int M = 1e9 + 7;
int fp(int x, int y){
    using ll = long long int;
    ll ans = 1;
    ll b = x;
    while(y){
        if(y & 1) ans = ans * b % M;
        b = b * b % M;
        y >>= 1;
    }
    return ans;
}

4、Dijkstra

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

const int maxn = 100010;
struct Edge {
    int next, to, w;
} edges[maxn * 2];
int heads[maxn], pos = 0;

void addEdge(int a, int b, int w) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    edges[pos].w = w;
    heads[a] = pos;
}
// 从0开始
bool vis[maxn];
int dist[maxn];
void dijkstra(int s, int n) {
    memset(vis, 0, sizeof(vis));
    memset(dist, 63, sizeof(dist));
    dist[s] = 0;
    using pi = pair<int, int>;
    priority_queue<pi, vector<pi>, greater<>> q;
    q.emplace(0, s);
    while (!q.empty()) {
        pi t = q.top(); q.pop();
        if (vis[t.second]) continue;
        vis[t.second] = true;
        for (int i = heads[t.second]; ~i; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].w;
            if (!vis[v] && w + t.first < dist[v]) q.emplace(dist[v] = w + t.first, v);
        }
    }
}