线性表

栈

STL中提供了栈的模板，这里总结一下相关的用法

#include<stack>

stack<type> s;

支持以下操作：

  • s.push()
  • s.pop()
  • s.top()
  • s.empty()
  • s.size()

当然STL很慢，比赛默认编译选项不会开优化

所以下面给出手写栈的方法，已经封装成结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct stack{
    int a[105],tot = 0;
    void push(int x){
        a[++tot] = x;
    }
    void pop(){
        tot--;
    }
    int top(){
        return a[tot];
    }
    int size(){
        return tot;
    }
    bool empty(){
        return tot == 0;
    }
};

单调栈

呜，我写的丑

P5788 【模板】单调栈

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
#include <cstdio>
#include <stack>
using namespace std;

const int maxn = 3e6 + 10;

stack<int> s;

int n, a[maxn], ans[maxn];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    s.push(n), ans[n] = 0;
    for (int i = n - 1; i >= 1;i--){
        while(!s.empty()&&a[i]>=a[s.top()])
            s.pop();
        ans[i] = s.empty() ? 0 : s.top();
        s.push(i);
    }
    for (int i = 1; i <= n;i++)
        printf("%d ", ans[i]);
    return 0;
}

另外，单调栈也可以用于离线解决 RMQ 问题。

队列

STL中需要 #include<queue>

同样给出封装后的结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct queue{
    int a[1005];
    int head = 1, tail = 0;

    void push(int x){
        a[++tail] = x;
    }

    void pop(){
        head++;
    }

    int front(){
        return a[head];
    }

    int size(){
        return tail - head + 1;
    }

    bool empty(){
        return head>tail;
    }
};

双端队列

STL太香啦

#include<deque>

deque<int> q;

支持的操作：

  • q[i]:返回队列中下标为i的元素的引用。
  • q.front(): 返回的一个元素的引用。
  • q.back() : 返回最后一个元素的引用。
  • q.pop_back(): 删除尾部的元素，不返回值。
  • q.pop_front(): 删除头部元素，不返回值。
  • q.push_back(e): 在队尾添加一个元素e。
  • q.push_front(e): 在对头添加一个元素e。

单调队列

单调队列中所说的“队列”和常规的队列含义不同，

其队首和队尾都支持插入删除操作

本质上是由双端队列实现的，

相当于使用双端队列维护单调序列

把模板题放在这里：

P1886 滑动窗口 /【模板】单调队列

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
void Max(){
    for (int i = 1; i <= n;i++){
        while(!q.empty()&&a[i].val>=q.back().val)
            q.pop_back();
        q.push_back(a[i]);
        while(q.front().num<=i-k)
            q.pop_front();
        if(i>=k)
            printf("%d ", q.front().val);
    }
    q.clear();
}

循环队列

其实很简单

1
2
3
4
while(1){
    q.push(q.front());
    q.pop();
}

然后就开始转圈圈了~~~

优先队列

STL中提供了std::priority_queue

实际上是采用二叉堆来实现的

定义方式：
priority_queue<Type, Container, Functional>

  • type是数据类型，可以是int，float等或自己写的结构体类型

  • Container是容器，只能是vector或deque，默认vector

  • Functional是优先度判断方式，包括less<int>（递减）和greater<int>（递增）,默认采用递减，支持自定义cmp函数，

比如定义递减的int型优先队列：priority_queue<int> q;

常用操作：

  • q.empty() 如果队列为空，则返回真

  • q.pop() 删除对顶元素，删除第一个元素

  • q.push() 加入一个元素

  • q.size() 返回优先队列中拥有的元素个数

  • q.top() 返回优先队列队首元素（有最高优先级的元素）

因为来不及仔细写堆了就只能靠STL救命了，

update：返校就学了堆，现在补一下代码，同样是封装好的结构体

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
struct heap{
    int heap_size = 0;
    int heap[maxn];

    int top(){
        return heap[1];
    }
    void insert(int x){
        heap[++heap_size] = x;
        int now = heap_size;
        while(now>1){
            int fa = now >> 1;
            if(heap[now]<heap[fa]){
                swap(heap[now], heap[fa]);
                now = fa;
                continue;
            }
            else
                break;
        }
    }
    void pop(){
        heap[1] = heap[heap_size--];
        int now = 1;
        while(now<=(heap_size>>1)){
            int ls = now << 1, rs = now << 1 | 1;
            int max_son = rs > heap_size ? ls : (heap[ls] < heap[rs] ? ls : rs);
            if(heap[now]>heap[max_son]){
                swap(heap[now], heap[max_son]);
                now = max_son;
                continue;
            }
            else
                break;
        }
    }
    int size(){
        return heap_size;
    }
    bool empty(){
        return heap_size == 0;
    }
} h;

链表

因为单向链表太废了，所以就不写了

直接给一个双向链表（其实并没有什么区别

另外：STL里面的链表更废（std::list

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
struct node{
    int pre, nxt;       //*记录前驱和后继
    int key;            //*记录节点的值
    node(int _key = 0,int _pre = 0,int _nxt = 0){
        pre = _pre;
        nxt = _nxt;
        key = _key;
    }
};
node s[1005];       //*结点池

int tot = 0;        //*记录已经使用了几个位置

int find(int x){    //*查找x的节点编号，遍历链表
    int now = 1;
    while(now&&s[now].key!=x)
        now = s[now].nxt;
    return now;
}

void ins_front(int x,int y){
    int now = find(x);
    s[++tot] = node(y, s[now].pre, now);
    s[s[now].pre].nxt = tot;
    s[now].pre = tot;
}

void ins_back(int x,int y){ //*把y插在x后面
    int now = find(x);      //*现在s[now].key = x
    s[++tot] = node(y, now, s[now].nxt);
    //*y的前驱为now，后继为s[now].nxt
    s[s[now].nxt].pre = tot;
    //*更新原先now的后继的pre
    s[now].nxt = tot;
}

int ask_front(int x){
    int now = find(x);
    return s[s[now].pre].key;
}

int ask_back(int x){
    int now = find(x);
    return s[s[now].nxt].key;
}

void del(int x){
    int now = find(x);
    int lf = s[now].pre, rt = s[now].nxt;
    s[lf].nxt = rt;
    s[rt].pre = lf;
}

树

二叉查找树（BST）

码量还是有点大的~~~

所以只放一个BST的结构体

P5076 【深基16.例7】普通二叉树（简化版）

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
struct Node{
    int left, right;
    int size, value, num;

    Node(int l=0,int r=0,int s=0,int v=0){
        left = l, right = r, size = s, value = v;
        num = 1;
    }

} t[maxn];

inline void update(int root){
    t[root].size = t[t[root].left].size + t[t[root].right].size + t[root].num;
}

int rank(int x,int root){
    if(root){
        if(x<t[root].value)
            return rank(x, t[root].left);
        else if(x>t[root].value)
            return rank(x, t[root].right) + t[t[root].left].size + t[root].num;
        else
            return t[t[root].left].size + 1;
    }
    return 1;
}

int kth(int x,int root){
    if(x==0)
        return -INF;
    if(x<=t[t[root].left].size)
        return kth(x, t[root].left);
    else if(x<=t[t[root].left].size+t[root].num)
        return t[root].value;
    else
        return kth(x - t[t[root].left].size - t[root].num, t[root].right);
}

void insert(int x,int &root){
    if(x<t[root].value)
        if(!t[root].left)
            t[t[root].left = ++cnt] = Node(0, 0, 1, x);
        else
            insert(x, t[root].left);
    else if(x==t[root].value)
        t[root].num++;
    else
        if(!t[root].right)
            t[t[root].right = ++cnt] = Node(0, 0, 1, x);
        else
            insert(x, t[root].right);
    update(root);
}

线段树

萌萌的数据结构肯定少不了线段树

数组储存记得四倍空间

P3372 【模板】线段树 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
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 <cstdio>
using namespace std;

const int  maxn = 100010
  
typedef long long LL;
LL n, m, op;
LL a[maxn], d[maxn<<2], b[maxn<<2];		//四倍空间
LL ans[maxn],k;

//?建树
void build(LL s, LL t, LL p) {
    //todo 对 [s,t] 区间建立线段树,当前根的编号为 p
    //*递归建树，边界条件为区间长度为1，此时 d[i]=a[s]=a[t]
    if(s==t){
        d[p] = a[s];
        return;
    }
    LL m = (s + t) >> 1;

    //todo 递归对左右区间建树
    //*左儿子序号为p*2，右儿子序号为p*2+1
    build(s, m, p << 1);
    build(m + 1, t, p << 1 | 1);

    //*根节点大小为左右儿子节点之和
    d[p] = d[p << 1] + d[p << 1 | 1];
}

//?区间查询
LL getsum(LL l, LL r, LL s, LL t, LL p) {
    //*[l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
    if(s>=l&&t<=r)
        return d[p];
    //*当前区间为询问区间的子集时直接返回当前区间的和
    
    LL m = (s + t) >> 1;

    LL sum = 0;

    //*如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    if (b[p]) {
        d[p << 1] += b[p] * (m - s + 1);
        d[p << 1 | 1] += b[p] * (t - m);
        b[p << 1] += b[p];            //*将标记下传给子节点
        b[p << 1 | 1] += b[p];                       
        b[p] = 0;                    //*清空当前节点的标记
    }
    //*如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
    if(l<=m)
        sum += getsum(l, r, s, m, p << 1);
    //*如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
    if(r>m)
        sum += getsum(l, r, m + 1, t, p << 1 | 1);

    return sum;
}

//?区间修改(增加)
void update(LL l, LL r, LL c, LL s, LL t, LL p) {
    //*[l,r] 为修改区间,c 为被修改的元素的变化量,
    //*[s,t] 为当前节点包含的区间,p为当前节点的编号

    //*当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    if(s>=l&&t<=r){
        d[p] += (t - s + 1) * c;
        b[p] += c;
        return;
    }

    LL m = (s + t) >> 1;

    //*如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    if(b[p]&&s!=t){
        d[p << 1] += (m - s + 1) * b[p];
        d[p << 1 | 1] += (t - m) * b[p];
        //*将标记下传给子节点
        b[p << 1] += b[p];
        b[p << 1 | 1] += b[p];
        //*清空当前节点的标记
        b[p] = 0;
    }
    if(l<=m)
        update(l, r, c, s, m, p << 1);
    if(m<r)
        update(l, r, c, m + 1, t, p << 1 | 1);
    d[p] = d[p << 1] + d[p << 1 | 1];
}

ST表

ST表对于RMQ等可重复贡献问题有十分优秀的表现

常数小于线段树，但只支持查询操作，不支持修改，删除。

ST表的实现采用了倍增的思想。

P3865 【模板】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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int maxn = 1e5+10;

int n,m;
int f[maxn][22], log2[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)){
        if (ch=='-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)){
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

void init(){
    log2[0] = -1;
    for (int i = 1; i <= n;i++)
        log2[i] = log2[i >> 1] + 1;
    for (int j = 1; j <= 21;j++)
        for (int i = 1; i + (1 << j) - 1 <= n;i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j-1))][j - 1]);
}

int query(int l,int r){
    int k = log2[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n;i++)
        f[i][0] = read();
    init();
    for (int i = 1; i <= m;i++){
        int l = read(), r = read();
        printf("%d\n", query(l, r));
    }
    return 0;
}

倍增求LCA

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
//*倍增求LCA
#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;

const int maxn = 5e5+10;

vector<int> T[maxn];

int n, m, root;
int parents[18][maxn], depth[maxn];
bool visited[maxn];

inline int read(){
    register int rslt = 0, b = 1, c = getchar();
    while(!isdigit(c)){
        b = c == '-' ? -1 : 1;
        c = getchar();
    }
    while(isdigit(c)){
        rslt = rslt * 10 + c - '0';
        c = getchar();
    }
    return b * rslt;
}

void init(){
    int u, v;
    n = read(), m = read(), root = read();
    for (int i = 1; i < n;i++){
        u = read(), v = read();
        T[u].push_back(v);
        T[v].push_back(u);
    }
    depth[root] = 1;
}

void getDepth_dfs(int u){
    visited[u] = true;
    for (int i = 0; i < T[u].size();i++){
        int v = T[u][i];
        if(!visited[v]){
            parents[0][v] = u;
            depth[v] = depth[u] + 1;
            getDepth_dfs(v);
        }
    }
}

void getParents(){
    for (int up = 1; (1 << up) <= n; up++)
        for (int i = 1; i <= n; i++)
            parents[up][i] = parents[up - 1][parents[up - 1][i]];
}

int LCA(int u,int v)
{
	if(depth[u] < depth[v]) // 使满足u深度更大, 便于后面操作
        swap(u, v);

    // i求的是最多能向上跳2的几次幂步 
    int i = -1;
    while((1<<(i+1)) <= depth[u])
        ++i;

    // 平衡深度
    for (int j = i; j >= 0;j--)
        if(depth[u]-(1<<j)>=depth[v])
            u = parents[j][u];

    //特判刚好跳到一起（u，v有直接的祖宗关系）
    if(u==v)
        return u;

    // u和v一起向上跳
    for (int j = i; j >= 0;j--)
        if(parents[j][u]!=parents[j][v]){
            u = parents[j][u];
            v = parents[j][v];
        }

    //此时u已经位于LCA的子结点
    return parents[0][u];
}

void query(){
    while(m--){
        int u, v, ans;
        u = read(), v = read();
        ans = LCA(u, v);
        printf("%d\n", ans);
    }
}

int main()
{

    init();
    getDepth_dfs(root);
    getParents();
    query();

    return 0;
}

Trie

P2580 于是他错误的点名开始了

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
#include <cstdio>
using namespace std;

const int maxn = 5e5+10;
const int maxa = 26;

struct trie{
    int node[maxn][maxa], cnt;
    int exist[maxn];

    void insert(char *s){
        int p = 0;
        for (int i = 1; s[i];i++){
            int c = s[i] - 'a';
            if(!node[p][c])
                node[p][c] = ++cnt;
            p = node[p][c];
        }
        exist[p] = 1;
    }

    int find(char *s){
        int p = 0;
        for (int i = 1; s[i];i++){
            int c = s[i] - 'a';
            if(!node[p][c])
                return 0;
            p = node[p][c];
        }
        return exist[p]++;		//不需要计数的话可以改成bool型
    }
} trie;

int n, m;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n;i++){
        char s[52];
        scanf("%s", s + 1);
        trie.insert(s + 1);
    }
    scanf("%d",&m);
    for (int i = 1; i <= m; i++){
        char s[52];
        scanf("%s", s + 1);
        int rslt = trie.find(s + 1);
        if(rslt==1)
            printf("OK\n");
        else if(rslt>1)
            printf("REPEAT\n");
        else
            printf("WRONG\n");
    }
    return 0;
}

集合

并查集

P1551 亲戚

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
#include <cstdio>
  
const int maxn = 5050;

struct set{
    int fa[maxn];

    int find(int x){
        if(x==fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }

    void join(int a, int b){
        int f1 = find(a);
        int f2 = find(b);
        if(f1!=f2)
            fa[f1] = f2;
    }
};
set s;

int n, m, p;
int x, y;

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n;i++)
        s.fa[i] = i;
    for (int i = 1; i <= m;i++){
        scanf("%d%d", &x, &y);
        s.join(x, y);
    }
    for (int i = 1; i <= p;i++){
        scanf("%d%d", &x, &y);
        if(s.find(x)==s.find(y))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

std::map

map是使用红黑树实现的映射表

头文件：#include<map>

定义方法：map<type_key,type_data> m;

  • m[key]: 可以访问下标为“key”的元素

  • m.end(): 返回映射表中最后元素的下一个元素的地址

  • m.find(): 查找，返回地址，不存在则返回m.end()

  • m.empty()

  • m.size()

例题：P5266 【深基17.例6】学籍管理

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
#include <iostream>
#include <cstring>
#include <map>
using namespace std;

map<string, int> m;

string name;
int n, opt, score, ans;

int main()
{
    cin>>n;
    while(n--){
        cin>>opt;
        if(opt==1){
            cin>>name>>score;
            if(!m[name])
                ans++;
            m[name] = score;
            cout<<"OK"<<endl;
        }
        else if(opt == 2){
            cin>>name;
            if(m[name])
                cout<<m[name]<<endl;
            else
                cout<<"Not found"<<endl;
        }
        else if(opt == 3){
            cin>>name;
            if(m[name]){
                m[name] = 0;
                ans--;
                cout<<"Deleted successfully"<<endl;
            }
            else
                cout<<"Not found"<<endl;
        }
        else
            cout<<ans<<endl;
    }
    return 0;
}