数据结构模板

包含了ACM里面常用的基本数据结构

链表

单链表

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
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
// MAXN表示最大点数
int head = 0, e[MAXN], ne[MAXN], idx;

void init() {
    //初始化链表
    idx = 0, head = 0;
}

void insert(int val) {
    // 在链表头部插入一个数val
    e[++ idx] = val, ne[idx] = head, head = idx;
}

void insert_after(int k, int val) {
    // 在下标为k的节点后插入一个数val
    e[++idx] = val;
    ne[idx] = ne[k];
    ne[k] = idx;
}

void remove_head() {
    //删除头结点
    head = ne[head];
}

void remove(int k) {
    //删除下标为k的节点的后一个节点
    ne[k] = ne[ne[k]];
}

//遍历链表
for (int i = head; i; i = ne[i]) {
    //do something
}

链式前向星加边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// MAXN表示最大点数，MAXM表示最大边数，无向边的最大边数要乘以2
int head[MAXN], idx; 

void init()  {
    memset(head, 0, sizeof head);
    idx = 0;
}

struct EDGE  {
    int to, val, next;
}edge[MAXM]; 

void add(int head[], int from, int to, int val) {
    //head表示表头，可能不止建一张图 
    edge[++ idx].to = to, edge[idx].val = val, edge[idx].next = head[from], head[from] = idx;
}

队列和栈

模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// tt表示栈顶
int stk[MAXN], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0) {

}

模拟队列

普通队列

1
2
3
4
5
6
7
8
9
10
11
12
13
int q[MAXN];//队列
int hh, tt = -1;//队头和队尾，队头删除队尾插入

q[++ tt] = x;//插入元素

hh ++;//删除元素

if (hh <= tt) not empty //判断是否为空
else empty;

q[hh];//取出队头元素

q[tt];//取出队尾元素

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// hh 表示队头，tt表示队尾的后一个位置
int q[MAXN], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt) {

}

单调栈

适用范围

给定一个序列，求序列中的每一个数左边或者右边第一个比他大或者比他小的数在什么地方。

维护

单调递增栈：在保持栈内元素单调递增的前提下，如果栈顶元素大于要入栈的元素，则将其弹出。将新元素入栈

单调递减栈：在保持栈内元素单调递减的前提下，如果栈顶元素小于要入栈的元素，则将其弹出。将新元素入栈。

时间复杂度为 O(n)O(n)

详细解释

image-20220717200924785

单调递增栈：对于将要入栈的元素来说，在对栈进行更新后（即弹出了所有比自己大的元素），此时栈顶元素就是数组中左侧第一个比自己小的元素；当栈内元素被弹出时，遇到的就是数组中右边第一个比自己小的元素。

image-20220717200937725

单调递减栈：对于将要入栈的元素来说，在对栈进行更新后（即弹出了所有比自己小的元素），此时栈顶元素就是数组中左侧第一个比自己大的元素；当栈内元素被弹出时，遇到的就是数组中右边第一个比自己大的元素。

代码模板

找出每个数左边第一个比自己小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int stk[MAXN], tt;
int n;

void solve() {
    n = read();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt --;
        if (!tt) cout << -1 << " "; //找不到比他更小的数
        else cout << stk[tt] << " "; //输出左边第一个比自己小的元素
        stk[++tt] = x;
    }
}

单调队列

定义

还是依旧类似于单调栈的思想，求离自己最近的比自己大/小的值，或者求一段区间内的最大值和最小值。队尾插入，队头弹出。

代码模板

滑动窗口，求区间最大值和最小值

设两个数 aia_i 和 aja_j 在某个队列中，现在要求的是区间最小值。如果 aia_i 比 aja_j 更靠近队头且 aia_i 大于 aja_j ，说明 aia_i 之后永远不可能作为最小值输出，所以要在之前的操作中把 aia_i 弹出即可。这样操作下来，每次队头保存的都是最小值，整个队列的值都是单调的。

每次从队尾加入元素后判断一下队头有没有被覆盖掉。

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
// 滑动窗口，求区间内的最大值和最小值
int q[MAXN], hh, tt, n, k, a[MAXN];
//队列存放的是下标
//一共有n个数，区间长度为k
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    hh = 1, tt = 0;

    //处理最小值
    for (int i = 1; i <= n; i ++) {
        while (hh <= tt && a[i] <= a[q[tt]]) tt--; //队尾不单调
        q[++tt] = i;
        if (i - k >= q[hh]) hh++; //队头已不在队列中
        if (i >= k) cout << a[q[hh]] << " ";
    }
    cout << endl;

    //处理最大值
    hh = 1, tt = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && a[i] >= a[q[tt]]) tt--; //队尾不单调
        q[++tt] = i;
        if (i - k >= q[hh]) hh++; //队头已不在队列中
        if (i >= k) cout << a[q[hh]] << " ";
    }
    cout << endl;
}

算前缀和时预先插入一个0.

题目是求 1≤len≤k1 \leq len \leq k 的最大连续子序列和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, k;
ll sum[MAXN], a[MAXN];
int q[MAXN];
int hh = 1, tt = 0;
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i]; 
    }
    ll ans = -INF;
    //枚举以i作为终点的，长度不超过k的最大子序和
    q[++tt] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && i - q[hh] > k) hh++;
        ans = max(ans, sum[i] - sum[q[hh]]);
        while (hh <= tt && sum[q[tt]] >= sum[i]) tt--;
        q[++tt] = i;
        
    }
    printf("%lld\n", ans);
}

trie树（前缀树，字典树，01trie）

字符串前缀树

定义

TrieTrie 树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。储存形式如下：

image-20220717200958872

其中，00 既代表根节点，也代表空节点。

根据上图的过程，我们模拟一下字典树的建立过程。

插入的时候，如果能在之前的点中找到与当前的值相匹配的，就跳到那个点上去，否则就自己开辟一个空间继续往下建树。建完树后，终点打上标记，用于统计方案数。

查询的时候，依旧是往下查找。如果无法查找到，说明之前未插入这个前缀，个数返回 00 。如果能够到达终点，说明能匹配上整个串，就返回之前打好的标记。

nownow 用于表示当前节点的编号，开辟的方法类似于链式前向星用 ++tot++tot 来表示。

一个小细节，trietrie 树的信息其实是保存在边上而不是节点上的，而节点只存了边的信息。只有当一条边存在时，才说明这条边表示的信息存在。所以实际上，存储的信息是在边上的。

字典树需要的空间开销往往较大，注意仔细计算。往往，MAXNMAXN 指的是字符串的长度乘以个数，树中儿子的个数是 2626

模板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
ll son[MAXN][30]; //字典树
ll cnt[MAXN], tot; //结尾处的标记
char s[MAXN];
int len;
char c[10];
void insert(char s[], int len)  {
    //往字典树中插入一个字符串
    int now = 0; //0为根节点,now表示节点编号
    for (int i = 1; i <= len; i++) {
        int u = s[i] - 'a';
        if (!son[now][u])
            son[now][u] = ++ tot; //如果没有这个字符就给他加上
        now = son[now][u];       //往下层继续寻找
    }
    cnt[now]++; //标记终点
}

int query(char s[], int len) {
    //统计某个字符串出现的次数 
    int now = 0;
    for (int i = 1; i <= len; i++) {
        int u = s[i] - 'a';
        if (!son[now][u])
            return 0;     //找不到了
        now = son[now][u]; //往下层继续寻找
    }
    return cnt[now];
}

void solve() {
    int n;
    n = read();
    while (n --) {
        scanf("%s", c);
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        if (c[0] == 'I')
            insert(s, len);
        else
            printf("%d\n", query(s, len));
    }
}

模板2， 统计前缀

不仅要统计有多少个字符串是给定字符串的前缀，也要求出给定字符串是多少个字符串的前缀并求出他们的和

类似的定义一个数组 sumsum ，表示节点编号为 ii 的点被 经过 的次数。判断有多少字符串是给定字符串的前缀依然照旧计算。迭代到最后时，在累加上 sum[now]sum[now] 即为给定字符串可匹配的前缀的个数

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
ll n, m;
int son[500005][15], tot, cnt[MAXN], sum[MAXN];
int s[MAXN];

void insert(int s[], int len) {
    int now = 0;
    for (int i = 1; i <= len; i++) {
        int u = s[i];
        if (!son[now][u])
            son[now][u] = ++ tot;
        now = son[now][u];
        sum[now] ++; //经过now
    }
    cnt[now]++; //以now结束
}

ll query(int s[], int len) {
    int now = 0;
    ll ans = 0;
    for (int i = 1; i <= len; i++) {
        int u = s[i];
        if (cnt[now])
            ans += cnt[now];
        if (!son[now][u])
            return ans;
        now = son[now][u];
        //if(cnt[now])
        //ans+=sum[now]应该这样写，但为了方便就换成这种写法，因为后面还要减去cnt[now]+sum[now]有点啰嗦
    }
    ans = ans + sum[now]; //给定字符串作为前缀的匹配数量
    return ans;
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) {
        //插入n个字符串 
        int len = read();
        for (int j = 1; j <= len; j ++) s[j] = read();
        insert(s, len); 
    }
    for (int i = 1; i <= m; i ++) {
        //统计前缀
        int len = read();
        for (int j = 1; j <= len; j++) s[j] = read();
        printf("%lld\n", query(s, len));
    }
}

01trie

定义

所谓 01trie01trie 即每个节点只有 0,10,1 两个儿子的 TrieTrie 树，比较经典的是贪心求异或最大值

tips： 有些题目需要cnt数组记录路径贡献（子树大小），这时从父亲节点往下走时一定要判断一下当前这条路径是否非空！！！或者把根节点和now改为1，这样就不用加上cnt的判断也能过（虽然不知道为什么）

模板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
ll n;
ll a[MAXN];
ll son[MAXM][2], tot;

void insert(ll x) {
    int now = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1; //第i位的数
        if (!son[now][u]) 
            son[now][u] = ++tot;
        now = son[now][u];
    }
}

ll query(ll x) {
    ll ans = 0;
    ll now = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (son[now][!u]) {
            ans = ans * 2 + !u;
            now = son[now][!u];
        }
        else {
            ans = ans * 2 + u;
            now = son[now][u];
        }
    }
    return ans;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        insert(a[i]);
        ll b = query(a[i]);
        ans = max(ans, a[i] ^ b);
    }
    printf("%lld\n", ans);
}

模板2，01trie的删除和维护

给定一个长度为 nn 的序列 sis_i ，求 max(si+sj)⨁sk∣i≠j,j≠k,i≠kmax{(s_i+s_j)\bigoplus s_k} | i\neq j,j\neq k,i\neq k

需要注意的是 i,j,ki,j,k 必须各不相同。

基本一致。枚举 i,ji,j ，由于必须保证不同，所以在查找前要先把 a[i],a[j]a[i],a[j] 的贡献去除掉，也就是将字典树中 a[i]a[i] 和 a[j]a[j] 的路径清空 ，然后再查询 a[i]+a[j]a[i]+a[j] 的最大异或值，最后再把 a[i]a[i] 和 a[j]a[j] 的贡献加上。

可以另开一个数组 cntcnt 记录节点访问次数，通过对访问次数的加减再写一个 updateupdate 函数进行删除和添加操作。

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
ll n, m;
ll son[MAXN][2], tot, cnt[MAXN * 10];
ll a[MAXN];

void update(ll x, ll y) {
    int now = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        now = son[now][u];
        cnt[now] += y;
    }
}

ll query(ll x) {
    int now = 0;
    ll ans = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (son[now][!u] && cnt[son[now][!u]]) {
            //如果这个节点存在并且没有被删除掉 
            ans = ans * 2 + !u;
            now = son[now][!u];
        }
        else {
            ans = ans * 2 + u;
            now = son[now][u];
        }
    }
    return ans;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read(), update(a[i], 1);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            update(a[i], -1), update(a[j], -1);
            ans = max(ans, (a[i] + a[j]) ^ (query(a[i] + a[j])));
            update(a[i], 1), update(a[j], 1);
        }
    }
    printf("%lld\n", ans);
}

模板3，区间最大异或和

给定一个包含 nn 个元素的数组，a1,a2,...,ana_1,a_2,...,a_n

计算 (al1⨁al1+1⨁...⨁ar1)+(al2⨁al2+1⨁...⨁ar2)(a_{l_1}\bigoplus a_{l_1+1}\bigoplus ...\bigoplus a_{r_1})+(a_{l_2}\bigoplus a_{l_2+1} \bigoplus ...\bigoplus a_{r_2}) 的最大值,l2>r1l_2 > r_1

异或运算有一个特别的性质就是 x⨁x=0x\bigoplus x=0

al1⨁al1+1⨁al1+2⨁...⨁ar1=(a1⨁a2⨁...⨁al−1)⨁(a1⨁a2⨁a3⨁...⨁ar)a_{l_1}\bigoplus a_{l_1+1} \bigoplus a_{l_1+2} \bigoplus ... \bigoplus a_{r_1} =(a_1 \bigoplus a_2 \bigoplus ... \bigoplus a_{l-1})\bigoplus(a_1\bigoplus a_2 \bigoplus a_3 \bigoplus ... \bigoplus a_r)

这样区间求异或最大值就转化成了最大异或对问题。一直维护一个前缀异或和，然后查找该值能匹配到的最大异或值，最后把当前的前缀异或和插入到字典树中。用类似 DPDP 的过程来表示区间[1,i][1,i] 中能取到的最大区间异或和为 l[i]l[i] ，定义前缀异或和为SUM, 转移方程为 l[i]=max(l[i−1],query(SUM)⨁SUM)l[i]=max(l[i-1],query(SUM)\bigoplus SUM)

因为要保证两个区间不相交，所以还要反着来一遍后缀异或和，推理过程类似。

r[i]r[i] 表示区间 [i,n][i,n] 中能取到的最大区间异或和为 r[i]r[i] 。

定义后缀异或和为SUF

转移方程为 r[i]=max(r[i],query(SUF)⨁(SUF))r[i]=max(r[i],query(SUF)\bigoplus(SUF))

**update: **说一下这类求最大异或区间通用的细节。若先查询后插入，那么需要提前插入一个 00 ;若先插入后查询，则需保证前缀的第一位和后缀的第一位一定为 00。 这题就是因为没保证后缀第一位为 00 导致疯狂 WAWA ，后来 insertinsert 了个 00 才过了，其实是画蛇添足。

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
ll son[MAXN][2], tot, tmp;
ll pre[400005], suf[400005];
ll n, a[400005];
void insert(ll x) {
    int now = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!son[now][u])
            son[now][u] = ++tot;
        now = son[now][u];
    }
}

ll query(ll x) {
    int now = 0;
    ll ans = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (son[now][!u]) {
            ans = ans * 2 + !u;
            now = now[son][!u];
        }
        else {
            ans = ans * 2 + u;
            now = now[son][u];
        }
    }
    return ans;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    tmp = 0;
    for (int i = 1; i <= n; i++) {
        tmp ^= a[i];
        insert(tmp);
        pre[i] = max(pre[i - 1], query(tmp) ^ tmp);
    }
    insert(0);
    for (int i = n; i >= 1; i--) {
        tmp ^= a[i];
        insert(tmp);
        suf[i] = max(suf[i + 1], query(tmp) ^ tmp);
    }
    ll ans = 0;
    for (int i = 1; i < n; i++) ans = max(ans, pre[i] + suf[i + 1]);
    printf("%lld\n", ans);
}

可持久化 trie

概述

可持久化是一个重要的思想。我对于可持久化的理解就是：支持回到一个历史版本怀旧服并能够在历史版本上进行询问。

既然要访问历史版本，那么最直观的想法就是开 mm 个数组来记录下每个版本的 trietrie 树。当需要插入一个新的节点时，先完全复制上一个历史版本，然后再进行操作。然而这样操作空间是很捉急的。要知道，trietrie 树的本质目的是为了进行空间优化，实现的方法是公用枝条。可以在可持久化 trietrie 中借鉴这种思想。

可以注意到，不是有必要把所有点都复制过来。可以这样操作，规定一个数组为rt[MAXN]rt[MAXN]作为各个版本的入口，每次插入新版本前都先更新这个入口的编号。与朴素 trietrie 节点不同的是，每次插入一个点都必须新建一个节点，然后去看看上个版本的信息。如果上个版本同等高度下具有相同的点，把这个点的儿子复制下来（除了当前要插入的点），在把要插入的边填到新节点下。插入完之后一起往下走递归操作直到抵达叶子节点。

image-20220717201012874

通过上图可以发现，从一个版本入口开始遍历树，一定只能获得该版本内的所有串，并且空间大大减少。

模板，可持久化01trie

给定一个长度为 nn 的非负整数序列 aa

有 mm 个操作，在末尾添加一个数，长度增加一；输入l,r,xl,r,x，找到一个位置 pp ，满足 l≤p≤rl \leq p \leq r ，使得：a[p]⨁a[p+1]⨁...⨁a[n]⨁xa[p] \bigoplus a[p+1] \bigoplus ... \bigoplus a[n] \bigoplus x 最大并输出这个最大值

a[p]⨁a[p+1]⨁...⨁a[n]⨁x=sum[p−1]⨁sum[n]⨁xa[p] \bigoplus a[p+1] \bigoplus ... \bigoplus a[n] \bigoplus x=sum[p-1] \bigoplus sum[n] \bigoplus x

这个式子很容易推出来。sum[n]⨁xsum[n] \bigoplus x 可以直接算出来，所以目标就是利用 trietrie 快速求出 sum[p−1]sum[p-1] 使得 l−1≤p−1≤r−1l-1 \leq p-1 \leq r-1 且异或上某个值最大。

利用可持久化的思想，满足 p−1≤r−1p-1 \leq r-1 很容易实现，只要从 r−1r-1 版本入口进入字典树查询即可。

考虑新建一个数组 mx[MAXM]mx[MAXM] 表示某位上的某个节点出现在串中的最新时间（版本）,如果了解 tarjantarjan 求强连通分量的算法，这个数组记录的就是时间戳。这样在查询的过程中，我们只要保证该点下的子节点中至少存在一个节点的 mx[i]mx[i] 大于等于 l−1l-1 ，就一定能够保证这条路径的出现时间是大于等于 l−1l-1 的。

有一个细节。00 号节点在 trietrie 中意义非凡，既表示不存在也表示为根节点，在朴素字典树中根节点是不能存储信息的。因为前缀和的存在，必须插入一个值为 00的点作为 00 号版本。可是 mx[0]mx[0] 初始值为 00 ，也就是 00 号节点最新出现在 00 号版本 。可显然 00 号节点是不能被访问到的，所以要把其初始化为任意负数。

一段一段分析插入和查询的代码吧。

插入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insert(int id, int last, int now)
//id表示当前插入的前缀和编号为i，last表示上个版本下和现在这个版本上和now同等意义的点
{
    mx[now] = id;                 //更新最新版本信息
    for (int i = 31; i >= 0; i --) //枚举每一位
    {
        int u = sum[id] >> i & 1; //取出当前位数
        //如果前一个节点存在当前节点没有的分支，就把当前这个节点的空的路径指过去，相当于复制
        if (last)
            son[now][!u] = son[last][!u];
        son[now][u] = ++ tot; //正常的插入操作

        //可以注意到此时只复制了!u这个点的信息，u方向的还没复制过
        //不是说不用复制了
        //而是因为now现在插入的数字是u，而last版本下这条路径也是u，所以暂时不需要复制
        //如果之后的某个位置与last版本出现了偏差，在从那里开始复制就好了
        last = son[last][u], now = son[now][u]; //同步往下走（递归）
        mx[son[now][u]] = id;                   //更新当前点的最新版本信息
    }
}

查询：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll query(int now, int l, ll x)
{
    ll ans = 0;
    for (int i = 31; i >= 0; i --)
    {
        int u = (x >> i) & 1;
        if (mx[son[now][!u]] >= l)
        //1.!u这个点要出现过
        //2.!u这个点的最新版本出现时间要大于等于l
        //2包含1，只要满足2那么1也一定满足
        {
            now = son[now][!u];
            ans = ans * 2 + !u;
        }
        else
        {
            now = son[now][u];
            ans = ans * 2 + u;
        }
    }
    return ans;
}

初始化：

1
2
3
4
5
6
mx[0] = -114514;
//看不懂翻上面，还看不懂建议注释掉这句话。
//然后看看输入111,1111,11111这种与0异或后是最大的情况，看看发生什么
rt[0] = ++ tot;
sum[0] = 0;
insert(0, 0, rt[0]);//前缀和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
int n, m;
int son[MAXM][2], sum[MAXN], mx[MAXM], tot;
int rt[MAXM]; 

void insert(int id, int last, int now) {
    mx[now] = id;                
    for (int i = 31; i >= 0; i--)  {
        int u = (sum[id] >> i) & 1;
        if (last)
            son[now][!u] = son[last][!u];
        son[now][u] = ++ tot; 
        last = son[last][u], now = son[now][u]; 
        mx[son[now][u]] = id;                   
    }
}

ll query(int now, int l, ll x) {
    ll ans = 0;
    for (int i = 31; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (mx[son[now][!u]] >= l) {
            now = son[now][!u];
            ans = ans * 2 + !u;
        }
        else {
            now = son[now][u];
            ans = ans * 2 + u;
        }
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    mx[0] = -114514;
    rt[0] = ++tot;
    sum[0] = 0;
    insert(0, 0, rt[0]);
    for (int i = 1; i <= n; i++) {
        ll tmp;
        tmp = read();
        sum[i] = sum[i - 1] ^ tmp;
        rt[i] = ++ tot;
        insert(i, rt[i - 1], rt[i]);
    }
    while (m--) {
        char s[10];
        scanf("%s", s);
        if (s[0] == 'A') {
            //插入一个数
            ll x;
            x = read();
            n ++;                     //多了一个数
            sum[n] = sum[n - 1] ^ x; //更新前缀和
            rt[n] = ++ tot;           //新增一个版本
            insert(n, rt[n - 1], rt[n]);
        }
        else {
            ll x, l, r;
            l = read(), r = read(), x = read();
            //query返回的是从r-1这个版本进去，最早版本为l-1，与sum[n]^x异或后最大的数
            printf("%lld\n", query(rt[r - 1], l - 1, sum[n] ^ x) ^ (sum[n] ^ x));
        }
    }
}

并查集

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int f[MAXN]; //祖先节点

void init() {
    //初始化 
    for (int i = 1; i <= n; i ++) f[i] = i;
}

int findx(int x) {
    //找根节点
    if (x == f[x]) return x;
    else return f[x] = findx(f[x]);
}

void merge(int x, int y) {
    //合并 
    int fx = findx(x);
    int fy = findx(y);
    if (fy != fx) f[fy] = fx;
}

维护size的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int f[MAXN]; //祖先节点
int size[MAXN]; //集团内部元素个数
void init() {
    for (int i = 1; i <= n; i ++) f[i] = i, size[i] = 1;
}

int findx(int x) {
    if (x == f[x]) return x;
    else return f[x] = findx(f[x]);
}

void merge(int x, int y) {
    int fx = findx(x);
    int fy = findx(y);
    if (fy != fx) size[fx] += size[fy], f[fy] = fx;
}

带权并查集（节点到根的权值）

概述

image-20220717201028039

这就是基于路径压缩的带权并查集的样子。可以看到，在普通并查集的基础上，带权并查集在边中添加了一些额外的信息可以更好的处理问题。在 边上记录额外的信息 的并查集就是 带权并查集 。

tips:tips: 要判断矛盾时可以想想带权并查集能不能做

带权并查集のfind

每一条边都记录了节点到根节点的一个权值。基于路径压缩就会产生两个问题：

  • 我们希望得到的是 节点与根节点 的权值。但是在路径压缩之前，每个节点都是与 父节点 连接的，这个权值自然也是和其 父节点 的权值。因此在路径压缩的过程中，权值也应当做出更新。
  • 在两个集团进行合并时，因为两个集团的根节点不同，需要把一个集团的根节点同时赋为另一个集团的根节点。自然也要进行权值的更新

先记录下原本父节点的编号，接着路径压缩后父节点就会变成根节点，此时父节点的权值，已经是父节点到根节点的权值了。再加上当前节点与其父节点的权值，就会得到当前节点到根节点的权值

带权并查集のmerge

第一张图是 mergemerge 前，第二张图是 mergemerge 后

image-20220717201037328

image-20220717201048627

我们需要求出 pxpx 和 pypy 这条边的权值为多少。显然 x→y→pyx\rightarrow y\rightarrow py 和 x→px→pyx\rightarrow px\rightarrow py 这两条边的权值之和应该相同。容易求出 value[px]=value[y]+temp−value[x]value[px]=value[y]+temp-value[x] （temp为题目给出的关系）。虽然思想一样，但实际上更新方法都是需要都是参考具体题目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int val[MAXN]; //表示节点x到根的权值
int f[MAXN];

int findx(int x) {
    if (x != f[x]) {
        int t = f[x];//记录父亲节点的编号
        f[x] = findx(f[x]);
        val[x] += val[t];//父节点已经完成更新了
    }
    return f[x];
}

void merge(int x, int y) {
    int fx=findx(x);
    int fy=findx(y)
	if(fx!=fy) {
    	f[fx]=fy;
    	val[fx]=val[y]+temp-val[x];
	}
}

哈希

字符串哈希

模板，使用 unsignedlonglongunsigned long long 自然取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i++) {
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 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
ull hash1[MAXN], ull hash2[MAXN], ull pre1[MAXN], ull pre2[MAXN];
ull p = 131; //指定质数
ll n;
int cnt = 0;
char s[MAXN];
pair<ull, ull> temp[MAXN];
map<pair<ull, ull>, ll> mp; //哈希表，key为双哈希组成的二元组，value为相同的个数
void init() {
    pre1[0] = 1;
    pre2[0] = 1;
    for (int i = 1; i <= 400000; i++) {
        pre1[i] = (pre1[i - 1]) * p % mod1;
        pre2[i] = (pre2[i - 1]) * p % mod2;
    }
}

ull hashing1() {
    int m = strlen(s + 1);
    for (int i = 1; i <= m; i++) {
        hash1[i] = (hash1[i - 1] * p % mod1 + (s[i] - 'a' + 1)) % mod1;
    }
    return hash1[m];
}

ull hashing2() {
    int m = strlen(s + 1);
    for (int i = 1; i <= m; i++) {
        hash2[i] = (hash2[i - 1] * p % mod2 + (s[i] - 'a' + 1)) % mod2;
    }
    return hash2[m];
}

ull query1(ll l, ll r) {
    return (hash1[r] - hash1[l - 1] * pre1[r - l + 1] % mod1 + mod1) % mod1;
}
ull query2(ll l, ll r) {
    return (hash2[r] - hash2[l - 1] * pre2[r - l + 1] % mod2 + mod2) % mod2;
}
pair<ull, ull> query(ll l, ll r) {
    return make_pair<ull, ull>(query1(l, r), query2(l, r));
}

STL常用

vector

变长数组，倍增的思想

1
2
3
4
5
6
7
8
9
size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序
    vector<int> a(n, x) n个x

pair

1
2
3
4
5
typedef pair<int, int> pii;
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
size()/length()  返回字符串长度
empty()
clear()
substr(起始下标，(子串长度))  返回子串
c_str()  返回字符串所在字符数组的起始地址、
int pos = s.find("abc"); //返回"abc"在做字符串s中的下标位置
int pos = s.find("b", 5); //从字符串s下标5开始，寻找字符串b

string s1 = "abcd", s2 = "abcdedg";
s1.find_first_not_of(s2); //查找s1中与s2第一个不匹配的位置

string str, s1;
int pos = str.rfind(s1); //返回s1在str中最后出现的位置
int pos = str.find_first_of(s1) //返回s1在str中第一次出现的位置

queue队列

1
2
3
4
5
6
size()
empty()
push()  向队尾插入一个元素
front()  返回队头元素
back()  返回队尾元素
pop()  弹出队头元素

priority_queue 优先队列（大根堆）

1
2
3
4
5
6
size()
empty()
push()  插入一个元素
top()  返回堆顶元素
pop()  弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack栈

1
2
3
4
5
size()
empty()
push()  向栈顶插入一个元素
top()  返回栈顶元素
pop()  弹出栈顶元素

deque双端队列

1
2
3
4
5
6
7
8
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set,map,基于红黑树动态维护有序序列

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
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)

重载运算符时要重载全
set/multiset
insert()  插入一个数
find()  查找一个数
count()  返回某一个数的个数
erase()
	(1) 输入是一个数x，删除所有x   O(k + logn)
	(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x)  返回大于等于x的最小的数的迭代器
upper_bound(x)  返回大于x的最小的数的迭代器
    
map/multimap
insert()  插入的数是一个pair
erase()  输入的参数是pair或者迭代器
find()
[]  注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset

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
bitset大概就是类似于bool数组一样的东西
但是它的每个位置只占1bit（特别特别小）
bitset的原理大概是将很多数压成一个，从而节省空间和时间（暴力出奇迹）
一般来说bitset会让你的算法复杂度 /32

定义方法：bitset<10000> s;

bitset类型可以用string和整数初始化（整数转化成对应的二进制）
bitset<23>bit (string("11101001"));
cout<<bit<<endl;
bit=233;
cout<<bit<<endl;
输出结果：
00000000000000011101001
00000000000000011101001

bitset支持所有位运算
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita^bitb)<<endl;
//输出00000000000000000000001 
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita|bitb)<<endl;
//输出00000000000000011101001
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita&bitb)<<endl;
//输出00000000000000011101000
bitset<23>bit(string("11101001"));
cout<<(bit<<5)<<endl;
//输出00000000001110100100000
bitset<23>bit(string("11101001"));
cout<<(bit>>5)<<endl;
//输出00000000000000000000111
~, &, |, ^
>>, <<
==, !=
[]

bitset方法
bit.size()       返回大小（位数）
bit.count()     返回1的个数
bit.any()       返回是否有1
bit.none()      返回是否没有1
bit.set()       全都变成1
bit.set(p)      将第p + 1位变成1（bitset是从第0位开始的！） 
bit.set(p, x)   将第p + 1位变成x
bit.reset()     全都变成0
bit.reset(p)    将第p + 1位变成0
bit.flip()      全都取反
bit.flip(p)     将第p + 1位取反
bit.to_ulong()  返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string() 返回它转换为string的结果

树状数组

概述

基于二进制

image-20220717201103223

图中 aa 表示原数组，cc 表示树状数组包含的区间

查询的时候根据图来理解就是 lowbitlowbit 一路减过去得到的各个区间的值的和

修改是因为每个单节点可能对多个区间有贡献，所以要 lowbitlowbit 一路加上去做出自己相对应的贡献

基础模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAXN 200005
int n;
int a[MAXN];//原数组
int c[MAXN];//树状数组，表示树状数组节点i节点覆盖的范围和

int lowbit(int x) {
    //返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
    return x & -x;
}

void add(int x, int k) {
    //将原序列中第x个数加上k
    for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}

int ask(int x) {
    //查询序列前x个数的和
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += c[i];
    return sum;
}

求逆序对

根据前缀和的的思想，比 valval 大的数量为 sum[n]−sum[val]sum[n]-sum[val] 。前缀和又可以用树状数组来维护。

先从左往右，每次枚举一个新的数时，先直接用树状数组查找当前比他大的数有几个，然后用类似桶的思想更新这个数的贡献。他对桶的贡献为 11 。

1
2
3
4
5
6
int c[MAXN];//这是一个类似桶的东西，记录每个数出现了几次
for(int i = 1; i <= n; i++) {
    int y = a[i];
    big[i] = ask(n) - ask(y);//当前该点逆序对数量
    add(y, 1);//加上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
int n, m;
int a[MAXN];
int c[MAXN];

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

int ask(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) sum += c[i];
    return sum;
}

void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) a[i] = c[i] - c[i - 1];
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; i++) add(i, a[i]);
    while (m--) {
        char c;
        cin >> c;
        if (c == 'Q') {
            int x;
            cin >> x;
            cout << ask(x) << endl;
        }
        else {
            int l, r, k;
            cin >> l >> r >> k;
            add(l, k), add(r + 1, -k);
        }
    }
}

树状数组求kth

二分出前缀和等于 kk 的位置

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
int n, q;
int c[MAXN];

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

int ask(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) {
        ans += c[i];
    }
    return ans;
}

int kth(int x) {
    int l = 1, r = n;
    int ans;
    while (l <= r) {
        int mid = l + r >> 1;
        if (ask(mid) >= x) {
            ans = mid;
            r = mid - 1;
        }
        else 
            l = mid + 1;
    }
    return ans;
}

void update(int x, int val) {
    for (int i = x; i <= n; i += lowbit(i)) 
        c[i] += val;
}

void solve() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) {
        int x = read();
        update(x, 1);
    }
    for (int i = 1; i <= q; i++) {
        int opt = read();
        if (opt > 0) {
            update(opt, 1);
        }
        else if (opt < 0) {
            opt = -opt;
            int num = kth(opt);
            update(num, -1);
        }
    }
    if (!ask(n)) {
        puts("0");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (ask(i) - ask(i - 1) > 0) {
            printf("%d\n", i);
            return;
        }
    }
}

二维树状数组求子矩阵

第一行两个整数，n（1 <= n <= 1000）和m（1 <= m <= 100000），分别代表正方形格子的边长和询问次数。
接下来n行，每一行有n个bool形数字（0或1），代表灯泡的状态。
接下来m行，每一行第一个数字f（1或2）代表操作的类型，如果f是1，那么接下来输入一个坐标（x, y）(1 <= x, y <= n)，对于当前位置的灯泡状态进行改变，如果是2，那么接下来输入两个坐标（x1, y1）(1 <= x1, y1 <= n)， （x2, y2）(1 <= x2, y2 <= 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
int c[MAXN][MAXN], a[MAXN][MAXN];
int n, m;

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

void update(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= n; j += lowbit(j))
            c[i][j] += val;
}

int ask(int x, int y) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            ans += c[i][j];
    return ans;
}


void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = read();
            if (a[i][j])
                update(i, j, 1);
        }
    }
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int x = read(), y = read();
            if (a[x][y] == 1) {
                a[x][y] = 0;
                update(x, y, -1);
            }
            else {
                a[x][y] = 1;
                update(x, y, 1);
            }
        }
        else if (opt == 2) {
            int x = read(), y = read(), xx = read(), yy = read();
            
            printf("%d\n", ask(xx, yy) - ask(xx, y - 1) - ask(x - 1, yy) + ask(x - 1, y - 1));
        }
    }
}