欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 科技 > 能源 > 二、数据结构

二、数据结构

2025/4/20 14:23:51 来源：https://blog.csdn.net/2301_80901581/article/details/145355622  浏览:  次   关键词：二、数据结构

欢迎各位大佬们来到Tubishu的博客🌟
Tubishu是一名计算机本科生，不定期发送一些在学校的成果供佬们消遣~希望能为佬的编程之路添砖加瓦⭐🔥
求各位大佬们垂怜🔥点赞评论一下呗🔥🔥
本文专栏 ➡️ 蓝桥杯
请添加图片描述

二、数据结构

单链表

用两个数组模拟链表，一个记录值，另一个记录next指针

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点，也就是节点编号
int head, e[N], ne[N], idx;// 初始化
void init()
{head = -1;idx = 0;
}// 在链表头插入一个数a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}// 将头结点删除，需要保证头结点存在
void remove()
{head = ne[head];
}

双链表

用两个数组记录左右指针 0位置为头，1位置为尾

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;// 初始化
void init()
{//0是左端点，1是右端点r[0] = 1, l[1] = 0;idx = 2;
}// 在节点a的右边插入一个数x
void insert(int a, int x)
{e[idx] = x;l[idx] = a, r[idx] = r[a];l[r[a]] = idx, r[a] = idx ++ ;
}// 删除节点a
void remove(int a)
{l[r[a]] = l[a];r[l[a]] = r[a];
}

栈和队列

// tt表示栈顶
int stk[N], tt = 0;// 向栈顶插入一个数
stk[ ++ tt] = x;// 从栈顶弹出一个数
tt -- ;// 栈顶的值
stk[tt];// 判断栈是否为空
if (tt > 0)
{}
//普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;// 向队尾插入一个数
q[ ++ tt] = x;// 从队头弹出一个数
hh ++ ;// 队头的值
q[hh];// 判断队列是否为空
if (hh <= tt)
{}

单调队列和单调栈

保持队列或栈中元素单调

单调栈：常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i;
}
单调队列 ：常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口while (hh <= tt && check(q[tt], i)) tt -- ;q[ ++ tt] = i;
}

kmp

  • 性质 n − n e [ n ] n - ne[n] n−ne[n] 就是把 1 1 1到 n n n覆盖的最小循环节长度， 如果 n n n整除 n − n e [ n ] n - ne[n] n−ne[n], 那么其就是最小完全循环节长度
// s是长文本，p是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ ){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;
}// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的逻辑}
}

Trie树

用途：快速的存储和查找字符串

节点数为通常为每个串的最大长度乘以串的个数

son[N][M] N为节点个数，M为每个节点最多有多少个后代idx当前操作的是总共的第几个节点，s[n][m]中记录的是第n个节点的m（通常是把可能的字符情况映射到数字）字符是否存在，若存在为第几个节点若是记录串出现次数，cnt[N]数组记录每个节点结尾的串的个数int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
void insert(char *str)
{int p = 0;//（当前字符位置）for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';//(找出当前字符)if (!son[p][u]) son[p][u] = ++ idx;//（判断树中是否存在，不存在则新建）p = son[p][u];//（p移动到下一个字符位置）}cnt[p] ++ ;
}// 查询字符串出现的次数
int query(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

可持久化trie树

可持久化的含义的就是记录trie树更新的每个版本，

核心思想就是记录每个版本与上个版本不一样的即可

代码思路大致如下
p为上一版本的根节点， q为新版本的根节点
p = root[i - 1], q = ++ idx;
if(p) tr[q] = tr[p];//所当前节点信息上一版本中有，复制过来即可tr[p][si] = ++ idx;//si为要插入的节点，新插入的节点总结总要从新建立，哪怕老版本中有，因为在新版本中要用到因此要从新建立，p = tr[p][si];		//在新版本中用不到的老版本信息，使用老版本即可q = tr[q][si];   	//这两行的意义为，先把老版本的信息完全复制过来，如果新版本中要用到老版本的，再从新建立//老版本没有的也从新建立

并查集

  • 将两个集合合并

  • 询问两个元素是否在同一个集合中

  • 基本原理：每个集合用一颗树表示，树根的编号就是整个集合的编号，每个节点存储它的父节点， p [ x ] p[x] p[x]表示 x x x的父节点

(1)朴素并查集：int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点 同时路径压缩int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b);(2)维护size的并查集：int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点 同时路径压缩int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;size[i] = 1;}// 合并a和b所在的两个集合：size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)维护到祖宗节点距离的并查集：int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合：p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

两种并查集：

  • 带边权的并查集

所有可以相互推出关系的元素在一个集合内，通常关系是一个循环，以到根节点的距离表示与根节点的关系，再由与根节点的关系推出各个点之间的关系，通常要维护一个表示距离的数组d[], d[i]表示i到其父节点的距离，路径压缩过程中可同时更新d[]，

  • 带扩展域的并查集

每个集合内存的是元素关系，一个关系成立，则集合内的其他关系必然成立，每次合并的复杂度是O(k)的，对于关系较多的问题可能运行较为缓慢，各种关系的表示要确定好表示方式，避免一种表示，表示两种关系

树状数组

  • 作用：求前缀和，修改某一个数后的前缀和

​ 单点加法， 和区间和

​ 因此要求的值必须能通过前缀和求出

  • 时间复杂度：求前缀和 O ( l o g n ) O(logn) O(logn), 修改某一个数 O ( l o g n ) O(logn) O(logn)
int lowbit(int x)
{return x & -x;
}
//修改
void add(int x, int c)
{for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
//求值
int sum(int x)
{int res = 0;for(int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}

线段树

  • 把区间分成线段，叶子节点只有单个元素，通常每个节点为一个s结构体，结构体中维护各种所需要的信息，用数组模拟线段树，空间要开 4 ∗ N 4 * N 4∗N

​ 空间需要开 4 4 4倍因为 节点编号可能达到 4 n 4n 4n这个量级，比 4 n 4n 4n要小，中间很多点没用到，实际上只用到 2 ∗ n − 1 2*n - 1 2∗n−1个点

​ 查询和修改复杂度均是 O ( l o g n ) O(logn) O(logn)

/*
区间加询问区间和
*/
#include <bits/stdc++.h>using namespace std;
using LL = long long;const int N = 100010;
struct node{int l, r;LL sum;int add;
}tr[N << 2];
int a[N];
int n, m;void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(node &rt, node &l, node &r)
{l.sum += 1ll * (l.r - l.l + 1) * rt.add;l.add += rt.add;r.sum += 1ll * (r.r - r.l + 1) * rt.add;r.add += rt.add;rt.add = 0; 
}void pushdown(int u)
{pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r)
{if(l == r){tr[u] = {l, r, a[l], 0};return;}tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}void modify(int u, int l, int r, int d)
{if(l <= tr[u].l && tr[u].r <= r){tr[u].add += d;tr[u].sum += 1ll * (tr[u].r - tr[u].l + 1) * d;return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, d);if(r > mid) modify(u << 1 | 1, l, r, d);pushup(u);
}LL query(int u, int l, int r)
{if(l <= tr[u].l && tr[u].r <= r)return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = 0;if(l <= mid) res += query(u << 1, l, r);if(r > mid) res += query(u << 1 | 1, l, r);return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];build(1, 1, n);char op[2];int l, r, d;while(m --){cin >> op;if(op[0] == 'Q'){cin >> l >> r;cout << query(1, l, r) << "\n";}else{cin >> l >> r >> d;modify(1, l, r, d);}}return 0;
}

  • 势能线段树

    这种线段树要维护的信息，难以对整个区间计算，比如对一个区间内的数开根号，取模等
    但其有一种奇妙的性质，就是修改超过一定次数后，再修改区间内的数不变
    势能线段树就是利用这种性质：对区间修改直接暴力递归到叶子节点修改，但在递归的过程中，若发现这个区间内的数修改后不变的话，就不用递归下去
    时间复杂度 假设每个叶子节点最多修改k次后不变， 则修改的复杂度就是 O ( n l o g n ∗ k ) O(nlogn*k) O(nlogn∗k) 最坏情况下每个点修改k次
    查询复杂度就是正常的线段树复杂度 ( n l o g n ) (nlogn) (nlogn)

  • 线段树合并

    • 动态开点，只把使用的点开出来
    • 线段树合并的复杂度大致是 O ( l o g n ) O(logn) O(logn)的，空间开 4 ∗ n ∗ l o g n 4 * n * logn 4∗n∗logn
/*
有 n 个点，形成一个树状结构。有 m 次发放操作，每次选择两个点 x,y，对 x 到 y 的路径上（包括 x,y）的每个点发放一袋 z 类型的物品。求完成所有发放操作后，每个点存放最多的是哪种类型的物品。
n,z<=1e5
*/#include <bits/stdc++.h>using namespace std;
using LL = long long;
constexpr int N = 100007;
constexpr int M = N << 1;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][19];//16
int q[N];
int n, m;
vector<array<int, 3>> a(N);
vector<int> hs;
int root[N];//每个节点的对应线段树的根节点
int cnt;//已使用的节点
int ans[N];struct node{int lc, rc, mx, id;
}tr[N * 80];void add(int u, int v)
{e[idx] = v, ne[idx] = h[u], h[u] = idx ++;e[idx] = u, ne[idx] = h[v], h[v] = idx ++;
}int find(int x)
{return lower_bound(hs.begin(), hs.end(), x) - hs.begin() + 1;
}void bfs()
{memset(depth, 0x3f, sizeof(depth));depth[0] = 0, depth[1] = 1;int hh = 0, tt = 0;q[0] = 1;while(hh <= tt){auto t = q[hh ++];for(int i = h[t]; ~i; i = ne[i]){int ver = e[i];if(depth[ver] > depth[t] + 1){depth[ver] = depth[t] + 1;fa[ver][0] = t;for(int k = 1; k <= 16; k ++){fa[ver][k] = fa[fa[ver][k - 1]][k - 1];}q[++ tt] = ver;}}}
}int lca(int u, int v)
{if(depth[u] < depth[v]) swap(u, v);for(int k = 16; k >= 0; k --)if(depth[fa[u][k]] >= depth[v])u = fa[u][k];if(u == v) return u;for(int k = 16; k >= 0; k --)if(fa[u][k] != fa[v][k]){u = fa[u][k];v = fa[v][k];}return fa[u][0];
}//线段树
void pushup(int u)
{if(tr[tr[u].lc].mx >= tr[tr[u].rc].mx){tr[u].mx = tr[tr[u].lc].mx;tr[u].id = tr[tr[u].lc].id;}else{tr[u].mx = tr[tr[u].rc].mx;tr[u].id = tr[tr[u].rc].id;}
}void modify(int &u, int l, int r, int x, int k)
{if(u == 0) u = ++ cnt;if(l == r){tr[u].mx += k, tr[u].id = l;return;}int mid = l + r >> 1;if(x <= mid) modify(tr[u].lc, l, mid, x, k);else modify(tr[u].rc, mid + 1, r, x, k);pushup(u);
}//合并线段树
int merge(int r1, int r2, int l, int r)
{if(!r1) return r2;if(!r2) return r1;if(l == r){tr[r1].mx += tr[r2].mx;return r1;}int mid = l + r >> 1;tr[r1].lc = merge(tr[r1].lc, tr[r2].lc, l, mid);tr[r1].rc = merge(tr[r1].rc, tr[r2].rc, mid + 1, r);pushup(r1);return r1;
}void dfs(int u)
{for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == fa[u][0]) continue;dfs(ver);root[u] = merge(root[u], root[ver], 1, hs.size());}//要在这里求答案,因为合并父节点时可能会改变子节点的root信息if(tr[root[u]].mx != 0) ans[u] = hs[tr[root[u]].id - 1];
}void sovle()
{   cin >> n >> m;memset(h, -1, sizeof(h));for(int i = 1; i < n; i ++){int u, v;cin >> u >> v;add(u, v);}bfs();for(int i = 1; i <= m; i ++){cin >> a[i][0] >> a[i][1] >> a[i][2];hs.push_back(a[i][2]);}sort(hs.begin(), hs.end());hs.erase(unique(hs.begin(), hs.end()), hs.end());for(int i = 1; i <= m; i ++){auto [x, y, z] = a[i];int p = lca(x, y);z = find(z);modify(root[x], 1, hs.size(), z, 1);modify(root[y], 1, hs.size(), z, 1);modify(root[p], 1, hs.size(), z, -1);modify(root[fa[p][0]], 1, hs.size(), z, -1);}dfs(1);for(int i = 1; i <= n; i ++)cout << ans[i] << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout << setiosflags(ios::fixed) << setprecision(2);int T = 1;//cin >> T;while(T --){sovle();}return 0;
}

可持久化线段树（主席树）

区间修改操作较为困难，

记录了线段树每次修改的情况，一共有m + 1个版本，m为操作次数，空树也为一个版本

空间要开N * 4 + M * logN, 空间要特别注意，很容易开小

每次修改就是把信息改变的节点从新生成即可，每次修改的节点大概是logN级别

主席树的存储方式不再沿用堆的存储方式，因为每个版本要开新的节点，用数组存储，每个元素是个节点，每个节点存在左右儿子，

节点中不在存储，左右边界，因此，插入、询问时要传入左右边界 ，经典的例子有acwing 257题 第k小数

可持久化线段树与可持久化trie不同，每一个版本节点数量相同，只是信息改变，因此，先复制上一版本的所有信息，信息改变的节点从新创建

平衡树（treap）

平衡树可快速插入和查找 O ( l o g n ) O(logn) O(logn)

维护搜索树的性质的同时维护堆的性质，这两个性质的就可以使得树的形状确定，同时堆的性质使得树的高度不至于退化成一条链，平均树高 l o g n logn logn

int root, idx;
struct Node{int lc, rc;int key, val;int cnt, size;
}tr[N];void pushup(int p)
{tr[p].size = tr[tr[p].lc].size + tr[tr[p].rc].size + tr[p].cnt;
}int get_node(int key)
{tr[++ idx].key = key;tr[idx].val = rand();tr[idx].cnt = tr[idx].size = 1;return idx;
}void zag(int &p);
void build()
{get_node(-INF);get_node(INF);root = 1, tr[1].rc = 2;pushup(root);if(tr[1].val < tr[2].val) zag(root);
}void zig(int &p)//右旋
{int q = tr[p].lc;tr[p].lc = tr[q].rc;tr[q].rc = p;p = q;pushup(tr[p].rc); pushup(p);
}void zag(int &p)//左旋
{int q = tr[p].rc;tr[p].rc = tr[q].lc;tr[q].lc = p;p = q;pushup(tr[p].lc); pushup(p);
}void insert(int &p, int key)//插入
{if(!p) p = get_node(key);else if(tr[p].key == key) tr[p].cnt ++;else if(key < tr[p].key){insert(tr[p].lc, key);if(tr[tr[p].lc].val > tr[p].val) zig(p);}else{insert(tr[p].rc, key);if(tr[tr[p].rc].val > tr[p].val) zag(p);}pushup(p);
}void remove(int &p, int key)//删除
{if(!p) return;if(tr[p].key == key){if(tr[p].cnt > 1) tr[p].cnt --;else{if(tr[p].lc || tr[p].rc){if(!tr[p].rc || tr[tr[p].lc].val > tr[tr[p].rc].val){zig(p);remove(tr[p].rc, key);}else{zag(p);remove(tr[p].lc, key);}}else p = 0;}}else if(key < tr[p].key) remove(tr[p].lc, key);else remove(tr[p].rc, key);pushup(p);
}int get_rank_by_key(int p, int key)//通过数值找排名
{if(!p) return 0;if(tr[p].key == key) return tr[tr[p].lc].size + 1;if(key < tr[p].key) return get_rank_by_key(tr[p].lc, key);else return tr[tr[p].lc].size + tr[p].cnt + get_rank_by_key(tr[p].rc, key);
}int get_key_by_rank(int p, int rank)//通过排名找数值
{if(!p) return INF;if(rank <= tr[tr[p].lc].size) return get_key_by_rank(tr[p].lc, rank);if(rank <= tr[tr[p].lc].size + tr[p].cnt) return tr[p].key;else return get_key_by_rank(tr[p].rc, rank - tr[tr[p].lc].size - tr[p].cnt);
}//这两段找前驱后继，很精简巧妙
int get_prec(int p, int key)//找前驱（严格小于）
{if(!p) return -INF;if(key <= tr[p].key) return get_prec(tr[p].lc, key);//若找小于等于 去掉等号else return max(tr[p].key, get_prec(tr[p].rc, key));
}int get_succ(int p, int key)//找后继（严格大于）
{if(!p) return INF;if(key >= tr[p].key) return get_succ(tr[p].rc, key);//若找大于等于 去掉等号else return min(tr[p].key, get_succ(tr[p].lc, key));
}

Splay

  • s p l a y splay splay 能够 O ( l o g n ) O(logn) O(logn)的原因是，在旋转时，对一条链的路径进行了折叠

  • 核心只有 s p l a y splay splay和 r o t a t e rotate rotate两个函数，其他函数，依据需要添加即可。

​ s p l a y splay splay函数的作用是把 x x x节点调整到 k k k节点的面， k k k为0，即让 x x x作为根节点。

​ 切记 如果将x调整到k的下面，一定先将k调整到根节点，不然会死循环。

​ 处处 s p l a y splay splay!!!

/*AcWing 253.普通平衡树
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1.插入数值 x。2.删除数值 x(若有多个相同的数，应只删除一个)。3.查询数值 x 的排名(若有多个相同的数，应输出最小的排名)。4.查询排名为 x 的数值。5.求数值 x 的前驱(前驱定义为小于 x 的最大的数)。6.求数值 x 的后继(后继定义为大于 x 的最小的数)。
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 1000010, INF = 0x3f3f3f3f;
struct node{int s[2], v, p;int sz, cnt;void init(int _v, int _p){v = _v, p = _p;sz = cnt = 1;}
}tr[N];
int n;
int root, idx;
int tag;void pushup(int u)
{tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + tr[u].cnt;
}void rotate(int x)
{int y = tr[x].p, z = tr[y].p;int k = x == tr[y].s[1];tr[x].p = z, tr[z].s[y == tr[z].s[1]] = x;tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;tr[y].p = x, tr[x].s[k ^ 1] = y;pushup(y), pushup(x);
}void splay(int x, int k)
{while(tr[x].p != k){int y = tr[x].p, z = tr[y].p;if(z != k)if((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);else rotate(y);rotate(x);}if(!k) root = x;
}void insert(int v)
{	int u = root, p = 0;while(u){if(v == tr[u].v){tr[u].cnt ++;tr[u].sz ++;splay(u, 0);break;}p = u, u = tr[u].s[v > tr[u].v];}if(!u){u = ++ idx;if(p) tr[p].s[v > tr[p].v] = u;tr[u].init(v, p);splay(u, 0);}
}int get_pre(int v)//找前驱
{int u = root, res = 0;while(u){if(tr[u].v >= v) u = tr[u].s[0];else res = u, u = tr[u].s[1];}return res;
}int get_suc(int v)//找后继
{int u = root, res = 0;while(u){if(tr[u].v <= v) u = tr[u].s[1];else res = u, u = tr[u].s[0];}return res;
}int get_rank(int u, int v)//通过数值找排名
{if(!u) return -1;if(tr[u].v == v){tag = u;return tr[tr[u].s[0]].sz + 1;}if(v < tr[u].v) return get_rank(tr[u].s[0], v);else return tr[tr[u].s[0]].sz + tr[u].cnt + get_rank(tr[u].s[1], v);
}int get_k(int k)//通过排名找数值
{int u = root;while(u){if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];else if(tr[tr[u].s[0]].sz < k && tr[tr[u].s[0]].sz + tr[u].cnt >= k) return u;else k -= tr[tr[u].s[0]].sz + tr[u].cnt, u = tr[u].s[1];}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;insert(-INF);insert(INF);while(n --){int op, x;cin >> op >> x;if(op == 1){insert(x);}else if(op == 2){int l = get_pre(x), r = get_suc(x);splay(l, 0), splay(r, l);tr[tr[r].s[0]].sz --;if(-- tr[tr[r].s[0]].cnt == 0)tr[r].s[0] = 0;pushup(r), pushup(l);if(tr[r].s[0]) splay(tr[r].s[0], 0);}else if(op == 3){cout << get_rank(root, x) - 1 << endl;splay(tag, 0);}else if(op == 4){int u = get_k(x + 1);cout << tr[u].v << endl;splay(u, 0);}else if(op == 5){int u = get_pre(x);cout << tr[u].v << endl;splay(u, 0);}else{int u = get_suc(x);cout << tr[u].v << endl;splay(u, 0);}}return 0;
}

树套树

  • 线段树套multiset

    /*
AcWing 2488.树套树简单版
请你写出一种数据结构，来维护一个长度为 n 的序列，其中需要提供以下操作：1 pos x，将 pos 位置的数修改为 x。
2 l r x，查询整数 x 在区间 [l,r] 内的前驱(前驱定义为小于 x，且最大的数)。
数列中的位置从左到右依次标号为 1∼n。区间 [l,r] 表示从位置 l 到位置 r 之间（包括两端点）的所有数字。区间内排名为 k 的值指区间内从小到大排在第 k 位的数值。（位次从 1 开始）
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 50010, INF = 0x3f3f3f3f;
struct node{int l, r;multiset<int> ms;
}tr[N << 2];
int a[N];
int n, m;void build(int u, int l, int r)
{tr[u] = {l, r};tr[u].ms.insert(-INF), tr[u].ms.insert(INF);for(int i = l; i <= r; i ++)tr[u].ms.insert(a[i]);if(l == r) return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}void modify(int u, int pos, int x)
{tr[u].ms.erase(tr[u].ms.find(a[pos]));tr[u].ms.insert(x);if(tr[u].l == tr[u].r) return;int mid = tr[u].l + tr[u].r >> 1;if(pos <= mid) modify(u << 1, pos, x);else modify(u << 1 | 1, pos, x); 
}int query(int u, int l, int r, int x)
{if(l <= tr[u].l && tr[u].r <= r){auto it = tr[u].ms.lower_bound(x);it --;return *it;}int mid = tr[u].l + tr[u].r >> 1;int res = -INF;if(l <= mid) res = max(res, query(u << 1, l, r, x));if(r > mid) res = max(res, query(u << 1 | 1, l, r, x));return res;
}int main()
{   ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];build(1, 1, n);while(m --){int op, l, r, x;cin >> op;if(op == 1){cin >> l >> x;modify(1, l, x);a[l] = x;}else{cin >> l >> r >> x;cout << query(1, l, r, x) << endl;}}return 0;
}

  • 线段树套splay

    /*
AcWing 2476.树套树
请你写出一种数据结构，来维护一个长度为 n 的数列，其中需要提供以下操作：1 l r x，查询整数 x 在区间 [l,r] 内的排名。
2 l r k，查询区间 [l,r] 内排名为 k 的值。
3 pos x，将 pos 位置的数修改为 x。
4 l r x，查询整数 x 在区间 [l,r] 内的前驱(前驱定义为小于 x，且最大的数)。
5 l r x，查询整数 x 在区间 [l,r] 内的后继(后继定义为大于 x，且最小的数)。
数列中的位置从左到右依次标号为 1∼n。区间 [l,r] 表示从位置 l 到位置 r 之间（包括两端点）的所有数字。区间内排名为 k 的值指区间内从小到大排在第 k 位的数值。（位次从 1 开始）
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 15000010, INF = 0x3f3f3f3f;
struct node{int s[2], v, p;int sz;void init(int _v, int _p){v = _v, p = _p;sz = 1;}
}tr[N];
int L[N], R[N], T[N], idx;
int n, m;
int a[N];//splay
void pushup(int u)
{tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;
}void rotate(int x)
{int y = tr[x].p, z = tr[y].p;int k = x == tr[y].s[1];tr[x].p = z, tr[z].s[y == tr[z].s[1]] = x;tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;tr[y].p = x, tr[x].s[k ^ 1] = y;pushup(y), pushup(x);
}void splay(int &root, int x, int k)
{while(tr[x].p != k){int y = tr[x].p, z = tr[y].p;if(z != k)if((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);else rotate(y);rotate(x);}if(!k) root = x;
}void insert(int &root, int v)
{int u = root, p = 0;while(u) p = u, u = tr[u].s[v > tr[u].v];u = ++ idx;if(p) tr[p].s[v > tr[p].v] = u;tr[u].init(v, p);splay(root, u, 0);
}int get_pre(int root, int v)//找数值前驱
{int u = root, res = 0;while(u){if(tr[u].v >= v) u = tr[u].s[0];else res = u, u = tr[u].s[1]; }return res;
}int get_suc(int root, int v)//找数值后继
{int u = root, res = 0;while(u){if(tr[u].v <= v) u = tr[u].s[1];else res = u, u = tr[u].s[0];}return res;
}int get_k(int root, int v)//小于v的数值个数
{int u = root, res = 0;while(u){if(tr[u].v < v) res += tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];else u = tr[u].s[0];}return res;
}//线段树
void build(int u, int l, int r)
{L[u] = l, R[u] = r;insert(T[u], -INF), insert(T[u], INF);for(int i = l; i <= r; i ++)insert(T[u], a[i]);if(l == r) return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}void update(int &root, int x, int y)//每个树中区间更新
{   int u = root;while(u){if(tr[u].v == x) break;else if(tr[u].v < x) u = tr[u].s[1];else u = tr[u].s[0];}splay(root, u, 0);int l = tr[u].s[0];while(tr[l].s[1]) l = tr[l].s[1];int r = tr[u].s[1];while(tr[r].s[0]) r = tr[r].s[0];splay(root, l, 0), splay(root, r, l);tr[r].s[0] = 0;pushup(r), pushup(l);insert(root, y);
}void modify(int u, int pos, int x)//线段树修改
{update(T[u], a[pos], x);if(L[u] == R[u]) return;int mid = L[u] + R[u] >> 1;if(pos <= mid) modify(u << 1, pos, x);else modify(u << 1 | 1, pos, x);
}int query_rk(int u, int l, int r, int x)//查询共有多少个小于给定数值的，排名要+1
{if(l <= L[u] && R[u] <= r) return get_k(T[u], x) - 1;int mid = L[u] + R[u] >> 1;int res = 0;if(l <= mid) res += query_rk(u << 1, l, r, x);if(r > mid) res += query_rk(u << 1 | 1, l, r, x);return res;
}int query_pre(int u, int l, int r, int x)//找数值前驱
{if(l <= L[u] && R[u] <= r){int res = get_pre(T[u], x);return tr[res].v;}int mid = L[u] + R[u] >> 1;int res = -INF;if(l <= mid) res = max(res, query_pre(u << 1, l, r, x));if(r > mid) res = max(res, query_pre(u << 1 | 1, l, r, x));return res;
}int query_suc(int u, int l, int r, int x)//找数值后继
{if(l <= L[u] && R[u] <= r){int res = get_suc(T[u], x);return tr[res].v;}int mid = L[u] + R[u] >> 1;int res = INF;if(l <= mid) res = min(res, query_suc(u << 1, l, r, x));if(r > mid) res = min(res, query_suc(u << 1 | 1, l, r, x));return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];build(1, 1, n);while(m --){int op, pos, l, r, x;cin >> op;if(op == 1){cin >> l >> r >> x;cout << query_rk(1, l, r, x) + 1 << endl;}else if(op == 2){cin >> l >> r >> x;int ls = 0, rs = 1e8;while(ls < rs){int mid = ls + rs + 1 >> 1;if(query_rk(1, l, r, mid) + 1 <= x) ls = mid;else rs = mid - 1;}cout << rs << endl;}else if(op == 3){cin >> pos >> x;modify(1, pos, x);a[pos] = x;}else if(op == 4){cin >> l >> r >> x;cout << query_pre(1, l, r, x) << endl;}else if(op == 5){cin >> l >> r >> x;cout << query_suc(1, l, r, x) << endl;}}return 0;
}

  • 线段树套线段树(外层权值线段树，内层动态开点)

    /*
AcWing 2306.K大数查询
有 N 个位置，M 个操作。每个位置可以同时存储多个数。操作有两种，每次操作:如果是 1 a b c 的形式，表示在第 a 个位置到第 b 个位置，每个位置加入一个数 c。
如果是 2 a b c 的形式，表示询问从第 a 个位置到第 b 个位置，第 c 大的数是多少。
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 50010, M = N * 400;
struct node{int lc, rc;int sum, add;
}tr[M];
int L[N << 2], R[N << 2], T[N << 2], idx;
int n, m;
struct query{int op, a, b, c;
}q[N];
vector<int> hs;int get(int x)
{return lower_bound(hs.begin(), hs.end(), x) - hs.begin();
}int mixed(int l1, int r1, int l2, int r2)
{return min(r2, r1) - max(l2, l1) + 1;
}//内层线段树，动态开点，只开用到的点, 标记可持久化
void update(int u, int l, int r, int ml, int mr)//更新内层线段树
{tr[u].sum += mixed(l, r, ml, mr);if(ml <= l && r <= mr){tr[u].add ++;return;}int mid = l + r >> 1;if(ml <= mid){ if(!tr[u].lc) tr[u].lc = ++ idx;update(tr[u].lc, l, mid, ml, mr);}if(mr > mid){if(!tr[u].rc) tr[u].rc = ++ idx;update(tr[u].rc, mid + 1, r, ml, mr);}
}int get_sum(int u, int l, int r, int ml, int mr, int add)
{if(ml <= l && r <= mr) return tr[u].sum + (r - l + 1) * add;int mid = l + r >> 1;add += tr[u].add;int res = 0;if(ml <= mid){if(tr[u].lc) res += get_sum(tr[u].lc, l, mid, ml, mr, add);else res += mixed(l, mid, ml, mr) * add;}if(mr > mid){ if(tr[u].rc) res += get_sum(tr[u].rc, mid + 1, r, ml, mr, add);else res += mixed(mid + 1, r, ml, mr) * add;}return res;
}//外层线段树， 权值线段树
void build(int u, int l, int r)
{L[u] = l, R[u] = r, T[u] = ++ idx;if(l == r) return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}void modify(int u, int l, int r, int c)
{update(T[u], 1, n, l, r);if(L[u] == R[u]) return;int mid = L[u] + R[u] >> 1;if(c <= mid) modify(u << 1, l, r, c);else modify(u << 1 | 1, l, r, c);
}int query(int u, int l, int r, int c)
{if(L[u] == R[u]) return R[u];int mid = L[u] + R[u] >> 1;int k = get_sum(T[u << 1 | 1], 1, n, l, r, 0);//右子树里有多少在l,r内的权值if(k >= c) return query(u << 1 | 1, l, r, c);else return query(u << 1, l, r, c - k);
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 0; i < m; i ++){int op, a, b, c;cin >> op >> a >> b >> c;q[i] = {op, a, b, c};if(op == 1) hs.push_back(c);}//数值离散化sort(hs.begin(), hs.end());hs.erase(unique(hs.begin(), hs.end()), hs.end());build(1, 0, (int)hs.size() - 1);for(int i = 0; i < m; i ++){int op = q[i].op, a = q[i].a, b = q[i].b, c = q[i].c;if(op == 1){modify(1, a, b, get(c));}else{cout << hs[query(1, a, b, c)] << endl;}}return 0;
}

分块

思想把整个区间分成 s q r t ( n ) sqrt(n) sqrt(n)个小区间，对于整个包含于查询或修改的小区间，标记或直接询问，对于部分包含于查询或修改区间的小区间直接暴力

整个包含的小区间不超过 s q r t ( n ) sqrt(n) sqrt(n)个， 暴力修改或查询的点也是 s q r t ( n ) sqrt(n) sqrt(n) 级别，这样单次总复杂度就是 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n)).

/*
AcWing 243.一个简单的整数问题2
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;
using LL = long long;const int N = 100010, M = 350;
LL add[M], sum[M];
int a[N];
int n, m, len;int get(int x)
{return (x - 1) / len;
}void change(int l, int r, int d)
{if(get(l) == get(r)){for(int i = l; i <= r; i ++) a[i] += d, sum[get(i)] += d;}else{int i = l, j = r;while(get(i) == get(l)) a[i] += d, sum[get(i)] += d, i ++;while(get(j) == get(r)) a[j] += d, sum[get(j)] += d, j --;for(int k = get(i); k <= get(j); k ++) add[k] += d, sum[k] += 1ll * len * d;}
}LL query(int l, int r)
{LL res = 0;if(get(l) == get(r)){for(int i = l; i <= r; i ++) res += a[i] + add[get(i)];}else{int i = l, j = r;while(get(i) == get(l)) res += a[i] + add[get(i)], i ++;while(get(j) == get(r)) res += a[j] + add[get(j)], j --;for(int k = get(i); k <= get(j); k ++) res += sum[k];}return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;len = sqrt(n);for(int i = 1; i <= n; i ++){cin >> a[i];sum[get(i)] += a[i];}char op[2];int l, r, d;while(m --){cin >> op;if(op[0] == 'Q'){cin >> l >> r;cout << query(l, r) << endl;}else{cin >> l >> r >> d;change(l, r, d);}}return 0;
}

莫队

  • 基础莫队

    /*
AcWing.2492.HH的项链
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答，因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 50010, M = 200010;
int a[N];
int cnt[1000010];
struct query{int id, l, r;
}qr[M];
int ans[M];
int n, m, len;int get(int x)
{return x / len;
}//在同一块内，右端点递增排序，不同块内，块递增排序
bool cmp(const query &a, const query &b)
{int i = get(a.l), j = get(b.l);if(i != j) return i < j;return a.r < b.r;
}int add(int x, int &res)
{if(++ cnt[x] == 1) res ++;
}int sub(int x, int &res)
{if(-- cnt[x] == 0) res --;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;len = sqrt(n);for(int i = 1; i <= n; i ++)cin >> a[i];cin >> m;for(int i = 1; i <= m; i ++){int l, r;cin >> l >> r;qr[i] = {i, l, r};}sort(qr + 1, qr + 1 + m, cmp);int i = 0, j = 1, res = 0;for(int k = 1; k <= m; k ++){int id = qr[k].id, l = qr[k].l, r = qr[k].r;//注意先加减还是后加减while(i < r) add(a[++ i], res);while(i > r) sub(a[i --], res);while(j > l) add(a[-- j], res);while(j < l) sub(a[j ++], res);ans[id] = res;}for(int i = 1; i <= m; i ++)cout << ans[i] << endl;return 0;
}

  • 带修莫队

    分块的大小为 n ∗ t 3 \sqrt[3]{n*t} 3n∗t ​, 可以达到最块理论复杂度 O ( n 4 ∗ t 3 ) O(\sqrt[3]{n^4*t}) O(3n4∗t ​) , t 为修改次数

    /*
AcWing 2521. 数颜色
墨墨购买了一套 N 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：Q L R 代表询问你从第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。
R P Col 把第 P 支画笔替换为颜色 Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 10010, M = 1000010;
int cnt[M];
int a[N], ans[N];
struct query{int id, l, r, t;
}qr[N];
struct change{int p, x;
}cg[N];
int n, m, mq, mc, len;int get(int x)
{return x / len;
}//按照左端点所在块编号，右端点所在块编号，第几个修改版本三关键字排序
bool cmp(const query &a, const query &b)
{int al = get(a.l), ar = get(a.r);int bl = get(b.l), br = get(b.r);if(al != bl) return al < bl;if(ar != br) return ar < br;return a.t < b.t;
}void add(int x, int &res)
{if(++ cnt[x] == 1) res ++;
}void sub(int x, int &res)
{if(-- cnt[x] == 0) res --;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= m; i ++){char op[2];int l, r;cin >> op >> l >> r;if(op[0] == 'Q'){mq ++, qr[mq] = {mq, l, r, mc};}else{cg[++ mc] = {l, r};}}len = cbrt(1.0 * n * max(1, mc)) + 1;sort(qr + 1, qr + 1 + mq, cmp);int i = 0, j = 1, t = 0, res = 0;for(int k = 1; k <= mq; k ++){int id = qr[k].id, l = qr[k].l, r = qr[k].r, tq = qr[k].t;while(i < r) add(a[++ i], res);while(i > r) sub(a[i --], res);while(j > l) add(a[-- j], res);while(j < l) sub(a[j ++], res);while(t < tq){t ++;int p = cg[t].p, &x = cg[t].x;if(j <= p && p <= i){sub(a[p], res);add(x, res);}swap(x, a[p]);}while(t > tq){int p = cg[t].p, &x = cg[t].x;if(j <= p && p <= i){sub(a[p], res);add(x, res);}swap(x, a[p]);t --;}ans[id] = res;}for(int i = 1; i <= mq; i ++)cout << ans[i] << endl;return 0;
}

  • 回滚莫队
    对于每个分块，在块内的查询暴力做，块间的按照右端点排序，依次查询，每次查询要把前一次查询在块内的部分回滚掉

    /*
AcWing 2523.历史研究
IOI 国历史研究的第一人——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。日记中记录了连续 N 天发生的时间，大约每天发生一件。事件有种类之分。第 i 天 (1≤i≤N) 发生的事件的种类用一个整数 Xi 表示，Xi 越大，事件的规模就越大。JOI 教授决定用如下的方法分析这些日记：选择日记中连续的一些天作为分析的时间段
事件种类 t 的重要度为 t× (这段时间内重要度为 t 的事件数)
计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
数据范围1e5
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;
using LL = long long;const int N = 100010;
int a[N], cnt[N];
LL ans[N];
struct query{int id, l, r;
}qr[N];
int n, m, len;
vector<int> hs;int get(int x)
{return x / len;
}bool cmp(const query &a, const query &b)
{int i = get(a.l), j = get(b.l);if(i != j) return i < j;return a.r < b.r;
}void add(int x, LL &res)
{cnt[x] ++;res = max(res, 1ll * cnt[x] * hs[x]);
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;len = sqrt(n);for(int i = 1; i <= n; i ++){cin >> a[i];hs.push_back(a[i]);}sort(hs.begin(), hs.end());hs.erase(unique(hs.begin(), hs.end()), hs.end());for(int i = 1; i <= n; i ++)a[i] = lower_bound(hs.begin(), hs.end(), a[i]) - hs.begin();for(int i = 1; i <= m; i ++){int l, r;cin >> l >> r;qr[i] = {i, l, r};}sort(qr + 1, qr + 1 + m, cmp);for(int x = 1; x <= m;){int y = x;while(y <= m && get(qr[y].l) == get(qr[x].l)) y ++;int right = get(qr[x].l) * len + len - 1;//处理块内询问while(x < y && qr[x].r <= right){LL res = 0;int id = qr[x].id, l = qr[x].l, r = qr[x].r;for(int k = l; k <= r; k ++) add(a[k], res);ans[id] = res;for(int k = l; k <= r; k ++) cnt[a[k]] --;x ++;}//处理块间询问LL res = 0;int i = right, j = right + 1;while(x < y){int id = qr[x].id, l = qr[x].l, r = qr[x].r;while(i < r) add(a[++ i], res);LL backup = res;while(j > l) add(a[-- j], res);ans[id] = res;while(j < right + 1) cnt[a[j ++]] --;res = backup;x ++;}memset(cnt, 0, sizeof(cnt));}for(int i = 1; i <= m; i ++)cout << ans[i] << endl;return 0;
}

  • 树上莫队

    • 核心：把树上路径转化为序列，通常转化为欧拉序列
    • 欧拉序列：dfs遍历一个树，第一次遍历到一个点时，把其加入序列，回溯时再把其加入序列，得到就是欧拉序列
    • 性质：对于a, b两个点 f i r s t [ a ] < f i r s t [ b ] first[a] < first[b] first[a]<first[b]
      • 若 l c a ( a , b ) = a lca(a, b) = a lca(a,b)=a 则对应的序列中的区间为 f i r s t [ a ] ≈ f i s r t [ b ] first[a] \approx fisrt[b] first[a]≈fisrt[b]
      • 若 l c a ( a , b ) ≠ a lca(a, b) \neq a lca(a,b)=a 则对应的序列中的区间为 l a s t [ a ] ≈ f i r a t [ b ] + l c a ( a , b ) last[a] \approx firat[b] + lca(a, b) last[a]≈firat[b]+lca(a,b)
/*
AcWing 2534.树上计数2
给定一棵 N 个节点的树，节点编号从 1 到 N，每个节点都有一个整数权值。现在，我们要进行 M 次询问，格式为 u v，对于每个询问你需要回答从 u 到 v 的路径上（包括两端点）共有多少种不同的点权值。
1≤N≤40000,
1≤M≤105,
1≤x,y,u,v≤N,
各点权值均在 int 范围内。
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 100010;
int h[N], e[N], ne[N], idx;
int seq[N], top;
int first[N], last[N];
int depth[N], f[N][16];
struct query{int id, l, r, p;
}qr[N];
int a[N], ans[N], cnt[N];
bool st[N];
int n, m, len;
vector<int> hs;void add(int a, int b, int edge)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;e[idx] = a, ne[idx] = h[b], h[b] = idx ++;
}void dfs(int u, int fa)
{seq[++ top] = u;first[u] = top;for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == fa) continue;dfs(ver, u);}seq[++ top] = u;last[u] = top;
}void bfs()
{int q[N] = {0};int hh = 0, tt = 0;q[0] = {1};memset(depth, 0x3f, sizeof(depth));depth[0] = 0, depth[1] = 1;while(hh <= tt){int t = q[hh ++];for(int i = h[t]; ~i; i = ne[i]){int ver = e[i];if(depth[ver] > depth[t] + 1){depth[ver] = depth[t] + 1;f[ver][0] = t;for(int k = 1; k <= 15; k ++)f[ver][k] = f[f[ver][k - 1]][k - 1];q[++ tt] = ver;}}}
}int lca(int a, int b)
{if(depth[a] < depth[b]) swap(a, b);for(int k = 15; k >= 0; k --)if(depth[f[a][k]] >= depth[b])a = f[a][k];if(a == b) return a;for(int k = 15; k >= 0; k --)if(f[a][k] != f[b][k]){a = f[a][k];b = f[b][k];}return f[a][0];
}int get(int x)
{return x / len;
}bool cmp(const query &a, const query &b)
{int i = get(a.l), j = get(b.l);if(i != j) return i < j;return a.r < b.r;
}void add(int x, int &res)
{st[x] ^= 1;if(st[x]){if(++ cnt[a[x]] == 1) res ++;}else{if(-- cnt[a[x]] == 0) res --;}
}int main()
{	ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> a[i];hs.push_back(a[i]);}sort(hs.begin(), hs.end());hs.erase(unique(hs.begin(), hs.end()), hs.end());for(int i = 1; i <= n; i ++)a[i] = lower_bound(hs.begin(), hs.end(), a[i]) - hs.begin();memset(h, -1, sizeof(h));for(int i = 0; i < n - 1; i ++){int x, y;cin >> x >> y;add(x, y, 1);}//预处理欧拉序、 lcadfs(1, -1);bfs();len = sqrt(top);for(int i = 1; i <= m; i ++){int a, b;cin >> a >> b;if(first[a] > first[b]) swap(a, b);int p = lca(a, b);if(a == p) qr[i] = {i, first[a], first[b]};else qr[i] = {i, last[a], first[b], p};}sort(qr + 1, qr + 1 + m, cmp);//莫队int i = 0, j = 1, res = 0;for(int k = 1; k <= m; k ++){int id = qr[k].id, l = qr[k].l, r = qr[k].r, p = qr[k].p;while(i < r) add(seq[++ i], res);while(i > r) add(seq[i --], res);while(j > l) add(seq[-- j], res);while(j < l) add(seq[j ++], res);if(p) add(p, res);ans[id] = res;if(p) add(p, res); }for(int i = 1; i <= m; i ++)cout << ans[i] << endl;return 0;
}

树链剖分

  • 概念
    • 重儿子：一个节点的儿子所在子树中节点个数最多的儿子
    • 轻儿子：除了重儿子外的其他儿子
    • 重边：连接父节点和重儿子的边
    • 轻边：连接父节点和轻儿子的边
    • 重链：由所有重边组成的边，每个点一定在一个重链中，单个节点也可构成重链
  • 如何解决树上问题
    • 将一颗树转化为序列，采用优先遍历重儿子的方式dfs, 保证重链在序列中连续
    • 树中路径转化为 l o g n logn logn个的连续区间（重链），采用线段树等数据结构维护信息即可
  • 性质
    • 定理：树中任意一条路径都可以转化为 l o g n logn logn个连续区间（重链）
    • 证明：考虑极端情况，从根节点走到任意叶节点，走过的重链数量等于走过的轻边数量，每走过一个轻边，子树大小至少减小二分之一，因此从根节点走到叶子节点最多都 l o g n logn logn条轻边，即最多走过 l o g n logn logn个重链，即走过 l o g n logn logn个连续区间
  • tips
    • 点权转边权：把边权转到子节点上即可，除了根节点，其他节点上都是权值，此时修改和查询不能计算路径上最高的节点。
  • 时间复杂度
    • 最坏的操作为用线段树每个维护 l o g n logn logn个连续区间，因此时间复杂度为 O ( n ∗ ( l o g n ) 2 ) O(n*(logn)^2) O(n∗(logn)2)
/*
AcWing2568.树链剖分
给定一棵树，树中包含 n 个节点（编号 1∼n），其中第 i 个节点的权值为 ai。初始时，1 号节点为树的根节点。现在要对该树进行 m 次操作，操作分为以下 4 种类型：1 u v k，修改路径上节点权值，将节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值增加 k。
2 u k，修改子树上节点权值，将以节点 u 为根的子树上的所有节点的权值增加 k。
3 u v，询问路径，询问节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值和。
4 u，询问子树，询问以节点 u 为根的子树上的所有节点的权值和。
数据范围
1≤n,m≤10^5,
0≤ai,k≤10^5,
1≤u,v,x,y≤n
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;
using LL = long long;const int N = 100010, M = N << 1;
int a[N], id[N], na[N];
int h[N], e[M], ne[M], idx;
int depth[N], top[N], sz[N], fa[N], son[N], cnt;
int n, m;
struct node{int l, r;LL add, sum;
}tr[N << 2];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;e[idx] = a, ne[idx] = h[b], h[b] = idx ++;
}void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(node &rt, node &l, node &r)
{if(rt.add){l.add += rt.add, l.sum += (l.r - l.l + 1) * rt.add;r.add += rt.add, r.sum += (r.r - r.l + 1) * rt.add;rt.add = 0;}
}void pushdown(int u)
{pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r)
{if(l == r){tr[u] = {l, r, 0, na[l]};return;}tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}void modify(int u, int l, int r, int k)
{if(l <= tr[u].l && tr[u].r <= r){tr[u].add += k;tr[u].sum += (tr[u].r - tr[u].l + 1) * k;return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, k);if(r > mid) modify(u << 1 | 1, l, r, k);pushup(u);
}LL query(int u, int l, int r)
{if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = 0;if(l <= mid) res += query(u << 1, l, r);if(r > mid) res += query(u << 1 | 1, l, r);return res;
}void dfs1(int u, int father, int dep)
{sz[u] = 1, depth[u] = dep, fa[u] = father ;for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == father) continue;dfs1(ver, u, dep + 1);sz[u] += sz[ver];if(sz[son[u]] < sz[ver]) son[u] = ver;}
}void dfs2(int u, int t)
{id[u] = ++ cnt, na[cnt] = a[u], top[u] = t;if(!son[u]) return;dfs2(son[u], t);for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == son[u] || ver == fa[u]) continue;dfs2(ver, ver);}
}void modify_path(int u, int v, int k)
{while(top[u] != top[v]){if(depth[top[u]] < depth[top[v]]) swap(u, v);modify(1, id[top[u]], id[u], k);u = fa[top[u]];}if(depth[u] < depth[v]) swap(u, v);modify(1, id[v], id[u], k);
}LL query_path(int u, int v)
{LL res = 0;while(top[u] != top[v]){if(depth[top[u]] < depth[top[v]]) swap(u, v);res += query(1, id[top[u]], id[u]);u = fa[top[u]];}if(depth[u] < depth[v]) swap(u, v);res += query(1, id[v], id[u]);return res;
}void modify_tree(int u, int k)
{modify(1, id[u], id[u] + sz[u] - 1, k);
}LL query_tree(int u)
{return query(1, id[u], id[u] + sz[u] - 1);
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];memset(h, -1, sizeof(h));for(int i = 0; i < n - 1; i ++){int a, b;cin >> a >> b;add(a, b);}dfs1(1, -1, 1);//确定重边dfs2(1, 1);//确定dfs序build(1, 1, n);cin >> m;while(m --){int op, u, v, k;cin >> op;if(op == 1){cin >> u >> v >> k;modify_path(u, v, k);}else if(op == 2){cin >> u >> k;modify_tree(u, k);}else if(op == 3){cin >> u >> v;cout << query_path(u, v) << endl;}else{cin >> u;cout << query_tree(u) << endl;}}return 0;
}

动态树

  • 思想：按照实边和虚边划分边，每个点一定在实边组成的链中，单个点自成链，每条实边链用一颗splay维护

  • tips:

    • 边权变点权技巧
      • 在两点之间插入一个点，并把边权赋在这个点上即可。

  • LCT七大操作

/*
AcWing2539.动态树
给定 n 个点，编号从 1 到 n，其中第 i 个点的初始权值为 ai。现在要对这些点进行 m 次操作，操作共分为以下 4 种：0 x y，表示询问点 x 到点 y 之间的路径上的所有点（包括两端点）的权值的异或和。保证 x 和 y 之间存在连通路径。
1 x y，表示在点 x 和点 y 之间增加一条边 (x,y)。注意：如果两点已经处于连通状态，则无视该操作。
2 x y，表示删除边 (x,y)。注意：如果该边不存在，则无视该操作。
3 x w，表示将点 x 的权值修改为 w。
数据范围
1≤n≤10^5,
1≤m≤3×10^5,
1≤x,y≤n,
x≠y,
1≤ai,w≤10^9
*/#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 100010;
struct node{int s[2], v, p;int rev, sum;
}tr[N];
int stk[N];
int n, m;void pushrev(int x)
{tr[x].rev ^= 1;swap(tr[x].s[0], tr[x].s[1]);
}void pushup(int x)
{tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}void pushdown(int x)
{if(tr[x].rev){pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);tr[x].rev = 0;}
}bool is_root(int x)
{return x != tr[tr[x].p].s[0] && x != tr[tr[x].p].s[1];
}//splay函数
void rotate(int x)
{int y = tr[x].p, z = tr[y].p;int k = x == tr[y].s[1];if(!is_root(y)) tr[z].s[y == tr[z].s[1]] = x;tr[x].p = z;tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;tr[y].p = x, tr[x].s[k ^ 1] = y;pushup(y), pushup(x);
}void splay(int x)
{//这里splay的时候，可能根到x路径上的懒标记没有传下来//要先传懒标记int top = 0, r = x;stk[++ top] = x;while(!is_root(r)) stk[++ top] = r = tr[r].p;while(top) pushdown(stk[top --]);while(!is_root(x)){int y = tr[x].p, z = tr[y].p;if(!is_root(y))if((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);else rotate(y);rotate(x);}
}//LCT函数
void access(int x)//建立一条x到根的实边路径， 同时把x旋转到splay的根节点
{   int z = x;for(int y = 0; x; y = x, x = tr[x].p){splay(x);tr[x].s[1] = y, pushup(x);}splay(z);
}void make_root(int x)//将x变为整棵树的根节点, 同时把x旋转到splay的根节点
{access(x);pushrev(x);
}int find_root(int x)//找到x所在树的根节点，并把根节点旋转到spaly的根节点
{access(x);while(tr[x].s[0]) pushdown(x), x = tr[x].s[0];splay(x);return x;
}void split(int x, int y)//建立x到y的实边路径，并且y是splay的根节点
{make_root(x);access(y);
}void link(int x, int y)//如果x,y之间没有边，就加一条x到y的虚边
{make_root(x);if(find_root(y) != x) tr[x].p = y;
}void cut(int x, int y)//切掉x,y之间的边
{make_root(x);access(y);if(find_root(y) == x && tr[x].s[1] == y && !tr[y].s[0])tr[x].s[1] = tr[y].p = 0, pushup(x);
}int main()
{   ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> tr[i].v;while(m --){int op, x, y;cin >> op >> x >> y;if(op == 0){split(x, y);cout << tr[y].sum << endl;}else if(op == 1) link(x, y);else if(op == 2) cut(x, y);else{splay(x);tr[x].v = y;pushup(x);}}return 0;
}

点分治

  • 思想
    • 按照树的重心进行划分，对重心连接的每个子树进行处理
    • 性质：按照重心划分出来的子树大小不会超过总点数的一半
  • 时间复杂度
    • 一共 l o g n logn logn层，总复杂度为 l o g n logn logn * 每一层的复杂度
/*
AcWing 252.树
给定一个有 N 个点（编号 0,1,…,N−1）的树，每条边都有一个权值（不超过 1000）。树上两个节点 x 与 y 之间的路径长度就是路径上各条边的权值之和。求长度不超过 K 的路径有多少条。
数据范围
1≤N≤10^4,
1≤K≤5×10^6,
0≤l≤10^3
*/#include <bits/stdc++.h>using namespace std;const int N = 10010, M = N << 1;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int n, k;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++;
}int get_size(int u, int fa)
{if(st[u]) return 0;int sum = 1;for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == fa) continue;sum += get_size(ver, u);}return sum;
}int get_wc(int u, int fa, int tot, int &wc)//找到u为根的子树的重心
{if(st[u]) return 0;int sum = 1, mx = 0;for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == fa) continue;int t = get_wc(ver, u, tot, wc);sum += t;mx = max(mx, t);}mx = max(mx, tot - sum);if(mx <= tot / 2) wc = u;return sum;
}void get_dist(int u, int fa, int dist, vector<int> &vec)
{if(st[u]) return;vec.push_back(dist);for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];if(ver == fa) continue;get_dist(ver, u, dist + w[i], vec);}
}int get_ans(vector<int> &vec)
{sort(vec.begin(), vec.end());int res = 0;for(int i = vec.size() - 1, j = -1; i >= 0; i --){while(j + 1 < i && vec[j + 1] + vec[i] <= k) j ++;j = min(j, i - 1);res += j + 1;}return res;
}int calc(int u)//计算以u为根的子树内符合条件的线段数量
{if(st[u]) return 0;get_wc(u, -1, get_size(u, -1), u);st[u] = true;//u此时就是重心int res = 0;vector<int> p;//所有节点到重心的距离for(int i = h[u]; ~i; i = ne[i]){int ver = e[i];vector<int> q;//当前子树到重心的距离get_dist(ver, u, w[i], q);for(auto c : q){if(c <= k) res ++;p.push_back(c);}res -= get_ans(q);}res += get_ans(p);for(int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);return res;
}void solve()
{idx = 0;memset(h, -1, sizeof(h));memset(st, 0, sizeof(st));for(int i = 0; i < n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << calc(1) << "\n";
}	int main()
{	ios::sync_with_stdio(false);cin.tie(nullptr);while(cin >> n >> k, n || k) solve();return 0;
}

CDQ分治

  • 解决问题：解决三维偏序问题

  • 思想

    • 按照三关键字排序，这样对于每一个数符合条件的一定在其前面
    • 每一个递归例程是求解这一例程对应对应区间内所有元素满足要求的对应的元素数量
    • 对于一个区间，一分为二，左右分别递归，各自区间得到求解，但对于右半区间，左边区间对其产生的贡献还未统计，此时归并求解
    • 归并方法：左半区间第一关键字一定已满足要求，且两区间内元素都按第二关键字排序(递归的副作用)，双指针统计右半边区间内每个元素在左区间内第二关键字满足的最大元素位置，两指针都往右走不会回头，同时用树状数组记录左半区间第三关键字的情况，对于右半区间每个元素，左区间内元素都到相应位置时(意味着，第一、第二关键字都已满足)，在树状数组中查询第三关键字满足要求的元素数量即可

  • 时间复杂度： O ( n ∗ l o g ( n ) 2 ) O(n * log(n)^2) O(n∗log(n)2)

    /*
给定 n 个元素（编号 1∼n），其中第 i 个元素具有 ai,bi,ci 三种属性。
设 f(i) 表示满足以下 4 个条件：
aj≤ai
bj≤bi
cj≤ci
j≠i
的 j 的数量。
对于 d∈[0,n)，求满足 f(i)=d 的 i 的数量。数据范围
1≤n≤10^5,
1≤ai,bi,ci≤k≤2×10^5
*/#include <bits/stdc++.h>using namespace std;const int N = 100010, M = N << 1;
struct data{int a, b, c, s, res;bool operator< (const data &t) const{if(a != t.a) return a < t.a;if(b != t.b) return b < t.b;return c < t.c;}bool operator== (const data &t) const{return a == t.a && b == t.b && c == t.c;}
}q[N], tmp[N];
int tr[M], ans[N];
int n, m;int lowbit(int x)
{return x & -x;
}void add(int x, int c)
{for(int i = x; i <= m; i += lowbit(i)) tr[i] += c;
}int sum(int x)
{int res = 0;for(int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}void merge_sort(int l, int r)
{if(l >= r) return;int mid = l + r >> 1;merge_sort(l, mid), merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 1;while(i <= mid && j <= r)if(q[i].b <= q[j].b) add(q[i].c, q[i].s), tmp[k ++] = q[i ++];else q[j].res += sum(q[j].c), tmp[k ++] = q[j ++];while(i <= mid) add(q[i].c, q[i].s), tmp[k ++] = q[i ++];while(j <= r) q[j].res += sum(q[j].c), tmp[k ++] = q[j ++];//清空树状数组for(int i = l; i <= mid; i ++) add(q[i].c, -q[i].s);for(int i = l, j = 1; i <= r;) q[i ++] = tmp[j ++];
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1; i <= n; i ++){int a, b, c;cin >> a >> b >> c;q[i] = {a, b, c, 1};}sort(q + 1, q + 1 + n);//去重、统计数量int k = 2;for(int i = 2; i <= n; i ++)if(q[i] == q[k - 1]) q[k - 1].s ++;else q[k ++] = q[i];merge_sort(1, k - 1);	for(int i = 1; i < k; i ++)ans[q[i].res += q[i].s - 1] += q[i].s;for(int i = 0; i < n; i ++)cout << ans[i] << "\n";return 0;
}

AC自动机

用于解决多模式匹配问题，例如 很多个单词在一篇文章中出现了多少个

时间复杂度 O ( n ) O(n) O(n), n为文章长度

ne[]存储每个节点最大后缀相匹配的最大前缀

// acwing 1282题
#include <cstdio>
#include <cstring>using namespace std;const int N = 10010, M = 1000010, S = 51;
int tr[N * S][26], cnt[N * S], idx;
int q[N * S], ne[M];void insert(char str[])
{int p = 0;for(int i = 0; str[i]; i ++){int t = str[i] - 'a';if(!tr[p][t]) tr[p][t] = ++ idx;p = tr[p][t];}cnt[p] ++;
}
//按照层来算， 已知i - 1层信息，算第i层信息，bfs
void build()
{int hh = 0, tt = -1;for(int i = 0; i < 26; i ++)if(tr[0][i])q[++ tt] = tr[0][i];while(hh <= tt){int t = q[hh ++];for(int i = 0; i < 26; i ++){//int c = tr[t][i];//if(!c) continue;//int j = ne[t];//while(j && !tr[j][i]) j = ne[j];//找到有孩子i的节点//if(tr[j][i]) j = tr[j][i];//上面这一步可以优化，这段的核心是找到带有i的并且父节点是t的//需要反复向上跳，优化的手段就是如果没有i这个孩子，就让它等于tr[ne[t]][i]//这相当于记录了最终要跳的位置//可优化成如下,这一步优化了，下面查找也要优化// 可以理解为：本来要去找应该跳到哪，不存在才需要找，直接利用这空间存储应该跳到哪int p = tr[t][i];if(!p) tr[t][i] = tr[ne[t]][i];else{ne[p] = tr[ne[t]][i];q[++ tt] = p;}ne[c] = j;q[++ tt] = c;}}
}int main()
{int T;scanf("%d", &T);while(T --){memset(tr, 0, sizeof tr);memset(cnt, 0, sizeof cnt);memset(q, 0 ,sizeof q);int n;scanf("%d", &n);char str[M];for(int i = 0; i < n; i ++){scanf("%s", str);insert(str);}build();int res = 0;scanf("%s", str);//匹配，j记录当前文本串中以str[i - 1]结尾的最大匹配for(int i = 0, j = 0; str[i]; i ++){int t = str[i] - 'a';//while(j && !tr[j][t]) j = ne[j];//if(tr[j][t]) j = tr[j][t];//建立优化以后，这里可以优化成j = tr[j][t];int p = j;while(p){res += cnt[p];cnt[p] = 0;p = ne[p];}}printf("%d\n", res);}return 0;
}

堆

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]);
}void down(int u)
{int t = u;if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;//注意这里只能写成h[t],t一直记录的最小值if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希表

按存储结构分：拉链法， 开放寻址法


(1) 拉链法//h[N]表示哈希数组，其中每一个值都是一个小链表头//e[N]用来存储所有的值int h[N], e[N], ne[N], idx;// 向哈希表中插入一个数void insert(int x){int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx ++ ;}// 在哈希表中查询某个数是否存在bool query(int x){int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;}
(2) 开放寻址法int h[N];//通常开题目数据的两到三倍//初始要对h数组中数字的标记memset(h, 0x3f, sizeof(h));// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置int find(int x){int k = (x % N + N) % N;while (h[k] != null && h[k] != x)//null为标记数字{k ++ ;if (k == N) k = 0;}return k;}

字符串哈希

思想：通过求每一段字符串的前缀数字表示，进而得出每一段字符串的数字表示

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果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];//str[i]转化成数字不能等于0p[i] = p[i - 1] * P;
}// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}

字符串的最小表示

对于一个长度为 n n n字符串，把其看成一个环, 从任意一个字符开始的长度为 n n n的所有字符串的，字典序最小的就是其最小表示

O ( n ) O(n) O(n)

string getMin(string str)
{int n = str.size();str = str + str;int i = 0, j = 1;while(i < n && j < n){int k = 0;while(str[i + k] == str[j + k]) k ++;if(k == n) break;//循环节，且以循环一轮if(str[i + k] > str[j + k]) i += k + 1;else j += k + 1;if(i == j) j ++;}int k = min(i, j);string res = str.substr(k, n);return res;
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词