2.1 链表
2.1.1 单链表
概念：
- 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
- 链表由一系列结点组成，每个结点中分为存储数据元素的数据域和存储下一个结点的指针域
操作思想
- 插入：新建一个结点，改变前一个结点的指针指向新建的结点
- 删除：将删除结点的前一个结点的指针指向该节点的后一个结点的指针
模板
/* 可使用数组、结构体等模拟链表，malloc和new模拟动态链表较慢，而结构体模拟代码繁琐，故采用静态数组模拟链表 */
const int N=1e6+10; //根据需要开辟链表大小
int e[N],ne[N],head=-1,idx=0; //e[N]存储值，ne[N]存储下一个结点，初始化head头结点，idx充当指针作用
void head_add(int x){ //在头部插入x
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void add(int k,int x){ //在下标k后面插入x
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k){ //删除下标k后面的结点
ne[k]=ne[ne[k]];
}例题 826.单链表
描述
实现一个单链表，链表初始为空，支持三种操作：
1.向链表头插入一个数；
2.删除第 k 个插入的数后面的数；
3.在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6输出样例：
6 4 6 5代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N],ne[N],head=-1,idx=0;
void head_add(int x){ //在头部插入x
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void add(int k,int x){ //在下标k后面插入x
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k){ //删除下标为k的结点
ne[k]=ne[ne[k]];
}
int main(){
int m;
cin>>m; //读入操作次数
while(m--){
string s;
cin>>s; //读入操作
if(s=="H"){ //头部插入
int x;
cin>>x;
head_add(x);
}
else if(s=="D"){ //删除操作
int k;
cin>>k;
if(k==0){
head=ne[head];
}
else{
remove(k-1); //idx从0开始，下标为k-1
}
}
else if(s=="I"){ //插入操作
int k,x;
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i]){ //遍历输出
cout<<e[i]<<" ";
}
return 0;
}2.1.2 双链表
概念：
- 在单链表的基础上，取消头结点，换为左端点和右端点，每个结点的指针域存储其左边结点的指针和右边结点的指针
操作思想
- 插入：思想同单链表，新建结点后，依次更改左右结点的左右指针的指向
- 删除：思想同单链表，将删除结点的左右结点的左右指针改向，跳过该节点
模板
const int N=1e6+10; //根据需要开辟链表大小
int e[N],r[N],l[N],idx; //e[N]存储值，r[N]存储右结点，l[N]存储左结点，idx用于计数
void init(){ //初始化链表
r[0]=1; //初始化左端点右边为右端点
l[1]=0; //初始化右端点左边为左端点
idx=2; //已经用掉了左端点和右端点，下标从2开始
}
void add(int k,int x){ //在下标k右边插入x
e[idx]=x; //存储新结点的值
l[idx]=k; //新结点的左边指针为k
r[idx]=r[k]; //新结点的右边指针为左结点的右指针r[k]
l[r[k]]=idx; //修改新结点右边结点的左指针为新结点下标idx
r[k]=idx++; //修改新结点左边结点的右指针为新结点下标idx
}
//调用时，若在第k个数的右边插入x则为 add(k+1,x) idx从2开始，故为k+1
//调用时，若在第k个数的左边插入x则为 add(l[k+1],x) 相当于在k左边的点的右边插入x
void remove(int k){ //删除下标为k的点
r[l[k]]=r[k];
l[r[k]]=l[k];
}例题 827. 双链表
描述
实现一个双链表，双链表初始为空，支持 5 种操作：
1.在最左侧插入一个数；
2.在最右侧插入一个数；
3.将第 k 个插入的数删除；
4.在第 k 个插入的数左侧插入一个数；
5.在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
1.L x，表示在链表的最左端插入数 x。
2.R x，表示在链表的最右端插入数 x。
3.D k，表示将第 k 个插入的数删除。
4.IL k x，表示在第 k 个插入的数左侧插入一个数。
5.IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2输出样例：
8 7 7 3 2 9代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N],r[N],l[N],idx=2;
void add(int k,int x){
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx++;
}
void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
r[0]=1,l[1]=0; //初始化链表
int m;
cin>>m; //读入操作次数
while(m--){
string s;
cin>>s; //读入操作
if(s=="L"){ //最左端插入x
int x;
cin>>x;
add(0,x); //最左端的端点下标为0
}
else if(s=="R"){ //最右端插入x
int x;
cin>>x;
add(l[1],x); //最右端的端点下标为下标为1的左边，即l[1]
}
else if(s=="D"){ //删除操作
int k;
cin>>k;
remove(k+1); //idx从2开始，下标为k+1
}
else if(s=="IL"){ //在第k个数左边插入x
int k,x;
cin>>k>>x;
add(l[k+1],x); //即在第k个数左边的数的右边插入x
}
else if(s=="IR"){ //在第k个数右边插入x
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){ //遍历输出
cout<<e[i]<<" ";
}
return 0;
}2.2 栈
2.1.1 模拟栈
概念：
- 栈是一种先进后出的数据结构
- 只允许对栈顶元素操作，不允许遍历
操作思想
- 利用静态数组模拟栈
- 实现进栈，出栈等操作
模板
const int N=1e6+10;
int stk[N],tt=0; //stk[N]用于模拟栈，类型可自定义，tt表示栈顶
void add(int x){ //栈顶插入x
stk[++tt]=x;
}
int top(){ //返回栈顶元素
return stk[tt];
}
void pop(){ //弹出栈顶元素
tt--;
}
bool empty(){ //判断是否为空
return tt==0; //若为空则返回true
}例题 828.模拟栈
描述
实现一个栈，栈初始为空，支持四种操作：
push x– 向栈顶插入一个数 x；pop– 从栈顶弹出一个数；empty– 判断栈是否为空；query– 查询栈顶元素。
现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。
数据范围
1≤M≤100000,
1≤x≤109
所有操作保证合法。
输入样例：
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty输出样例：
5
5
YES
4
NO代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0;
void add(int x){
stk[++tt]=x;
}
void pop(){
tt--;
}
bool empty(){ //判断是否为空
return tt==0; //若为空则返回true
}
int top(){
return stk[tt];
}
int main()
{
int n;
cin>>n;
while(n--){
string s;
cin>>s;
if(s=="push"){
int x;
cin>>x;
add(x);
}
else if(s=="pop"){
pop();
}
else if(s=="empty"){
if(empty()){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
else if(s=="query"){
cout<<top()<<endl;
}
}
return 0;
}2.1.2 单调栈
概念
- 栈中的元素满足某种单调性质
应用
- 常见模型：找出每个数左边离它最近的比它大/小的数
例题 830. 单调栈
描述
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：
5
3 4 2 7 5输出样例：
-1 3 -1 2 2代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
while(tt>0&&x<=stk[tt]) tt--; //当栈不为空时，判断x与栈顶元素关系，若构成逆序，则删除栈顶元素
if(tt>0) cout<<stk[tt]<<" ";
else cout<<-1<<" ";
stk[++tt]=x;
}
return 0;
}2.3 队列
2.3.1 模拟队列
概念
- 是一种先进先出的数据结构，它有两个出口
- 队列容器允许从尾端新增元素，从头端移除元素
- 队列中只有队头和队尾才可以被外界使用，故队列不允许遍历
操作思想
- 利用静态数组模拟队列
- 实现入队，出队等操作
模板
const int N=1e6+10;
int que[N],hh=0,tt=-1; //que[N]用于模拟队列，类型可自定义，hh为队头，tt为队尾
void add(int x){ //队尾插入x
que[++tt];
}
int top(){ //返回队头元素
return que[hh];
}
int back(){ //返回队尾元素
return que[tt];
}
void pop(){ //弹出队头元素
hh++;
}
bool empty(){ //判断是否为空
return tt<hh; //若为空则返回true
}例题 829. 模拟队列
描述
实现一个队列，队列初始为空，支持四种操作：
- push x – 向队尾插入一个数 x；
- pop – 从队头弹出一个数；
- empty – 判断队列是否为空；
- query – 查询队头元素。
现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000,
1≤x≤109,
所有操作保证合法。
输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6输出样例：
NO
6
YES
4代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int que[N],hh=0,tt=-1;
void add(int x){
que[++tt]=x;
}
void pop(){
hh++;
}
bool empty(){
return tt<hh;
}
int top(){
return que[hh];
}
int main()
{
int m;
cin>>m;
while(m--){
string s;
cin>>s;
if(s=="push"){
int x;
cin>>x;
add(x);
}
else if(s=="pop"){
pop();
}
else if(s=="empty"){
if(empty()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else if(s=="query"){
cout<<top()<<endl;
}
}
return 0;
}2.3.2 单调队列
概念
- 队列中的元素满足某种单调性质
应用
- 常见模型：找出滑动窗口中的最大值/最小值
例题 154. 滑动窗口
描述
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 kk 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N],hh,tt;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%d",&a[i]); //读入数组元素
hh=0,tt=-1; //初始化窗口队列，该队列存储a的下标
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-m+1>q[hh]) hh++; //当i-m+1大于当前队头下标时，队头出队
while(hh<=tt&&a[q[tt]]>=a[i]) tt--; //当窗口内队尾下标对应的数值大于当前进入窗口的值且hh<=tt时，则队尾更新为前一个元素下标，维护队头为最小值
q[++tt]=i; //当前值入队
if(i>=m-1) printf("%d ",a[q[hh]]); //输出队头
}
cout<<endl;
hh=0,tt=-1; //再次初始化窗口队列，该队列存储a的下标
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-m+1>q[hh]) hh++; //当i-m+1大于当前队头下标时，队头出队
while(hh<=tt&&a[q[tt]]<=a[i]) tt--; //当窗口内队尾下标对应的数值小于当前进入窗口的值且hh<=tt时，则队尾更新为前一个元素下标，维护队头为最大值
q[++tt]=i; //当前值入队
if(i>=m-1) printf("%d ",a[q[hh]]); //输出队头
}
return 0;
}2.4 堆
概念
- 本质为一颗完全二叉树
- 以小根堆为例，其每个结点的值，均小于等于左右子节点，即根节点为整棵树的最小值
操作思想
-
存储方式：用一维数组存储，设根节点的下标是
i,则左儿子是2*i，右儿子是2*i+1-
//对无序的一维数组进行建堆(小根堆) for(int i=n/2;i;i--) down(i); //n表示数组大小，利用down操作对堆进行排序
-
-
排序：若某结点的值发生改变，则判断其与父节点和左右两个子结点的大小关系，再进行上移或下移，递归处理直至满足当前堆的性质。
-
以小根堆为例：若某一结点的值增大，则需要将其向下移动，直到不能下移为止。
-
删除和修改元素：将最后插入的元素覆盖掉需要修改的元素，之后从修改元素的位置重新对堆进行排序
2.4.1 堆排序
思想
- 将数据以堆的形式进行存储
- 仅实现堆的上移或下移操作对堆中的数据进行排序
- 不考虑对堆中的数据进行修改
模板
////以小根堆为例
const int N=1e6+10; //堆的大小
int h[N]; //h[N]为堆
int idx; //idx表示当前的结点在数组中的下标
void down(int u){ //完成下移操作，u表示父节点
int t=u; //t用于比较
int p=u*2; //p表示左儿子节点的下标 p+1表示右儿子
if(p<=idx&&h[p]<h[t]) t=p; //在树的大小范围内，若左儿子小于父节点，则记录t
if(p+1<=idx&&h[p+1]<h[t]) t=p+1; //在树的大小范围内，若右儿子小于父节点，则记录t
if(u!=t){ //若t与原来的u不相等，说明u需要下移
swap(h[t],h[u]);
down(t); //递归处理，直到不能下移
}
}
void up(int u){ //完成上移操作，u表示子结点
int t=u>>1; //t表示u的父结点的下标，t=u/2
if(t&&h[u]<h[t]){ //当t>0并且子结点的值小于父结点的值，说明u要上移
swap(h[u],h[t]);
up(t); //递归处理，直到不能上移
}
}例题 838. 堆排序
描述
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输出样例：
5 3
4 5 1 3 2输出样例：
1 2 3代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int h[N];
int idx;
void down(int u){
int p=u*2;
int t=u;
if(p<=idx&&h[p]<h[t]) t=p;
if(p+1<=idx&&h[p+1]<h[t]) t=p+1;
if(u!=t){
swap(h[t],h[u]);
down(t);
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>h[++idx]; //建堆的操作
for(int i=n/2;i;i--) down(i);
while(m--){
cout<<h[1]<<" "; //将堆顶元素输出
h[1]=h[idx--]; //将堆最后的值覆盖堆顶的值，idx--使得删除堆最后的元素
down(1); //将堆顶的元素执行下移操作，进行排序
}
return 0;
}2.4.2 可操作的堆
支持的操作
- 插入一个数
- 求集合中的最小值
- 删除最小值
- 删除任意一个元素
- 修改任意一个元素
模板(注释解析版)
//以小根堆为例
const int N=1e6+10; //堆的大小
int idx,m; //idx表示当前的结点在数组中的下标，m表示插入的第m个数
int h[N],ph[N],hp[N];
//h[N]为堆
//ph[N]存储 第m个数 在h[N]中的下标 为idx 即ph[m]=idx
//hp[N]存储 在h[N]中 下标为idx的数 为插入第m个数 即hp[idx]=m
//由于我们在涉及到操作第m个元素时需要知道该元素是插入的第m个数，故需要p[h]和hp[N]的映射关系来确定
void h_swap(int a,int b){ //完成交换操作
swap(ph[hp[a]],ph[hp[b]]);
//通过hp[a]找到idx=a是插入的第m_i个数 ph[hp[a]]就可以得到其在h[N]中的下标
//通过hp[b]找到idx=a是插入的第m_j个数 ph[hp[b]]就可以得到其在h[N]中的下标
//交换idx的映射关系
swap(hp[a],hp[b]);
//交换m的映射关系
swap(h[a],h[b]);
//交换值
}
void down(int u){ //完成下移操作
//u表示父结点
int t=u; //t用于比较
int p=u*2; //p表示左儿子节点的下标 p+1表示右儿子
if(p<=idx&&h[p]<h[t]) t=p;
//p表示左儿子的下标，要在树的大小范围内，若左儿子小于父节点，则暂时记录t，最后与父节点u交换
if(p+1<=idx&&h[p+1]<h[t]) t=p+1;
//p+1表示右儿子的下标，要在树的大小范围内，若右儿子小于父节点，则暂时记录t，最后与父节点u交换
if(t!=u){ //若t与原来的u不相等，说明u需要下移
h_swap(t,u); //交换
down(t); //递归处理，直到不能下移
}
}
void up(int u){ //完成上移操作
//u表示子结点
int t=u>>1; //t表示u的父结点的下标
if(t&&h[u]<h[t]){ //当t>0并且子结点的值小于父结点的值，说明u要上移
h_swap(t,u); //交换
up(t); //递归处理，直到不能上移
}
}
模板(简注释)
//以小根堆为例
const int N=1e6+10; //堆的大小
int idx,m; //idx表示当前的结点在数组中的下标，m表示插入的第m个数
int h[N],ph[N],hp[N];
void h_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]); //交换idx的映射关系
swap(hp[a],hp[b]); //交换m的映射关系
swap(h[a],h[b]); //交换值
}
void down(int u){
int t=u;
int p=u*2; //p表示左儿子节点的下标 p+1表示右儿子
if(p<=idx&&h[p]<h[t]) t=p;
if(p+1<=idx&&h[p+1]<h[t]) t=p+1;
if(t!=u){
h_swap(t,u);
down(t); //递归处理，直到不能下移
}
}
void up(int u){
int t=u>>1;
if(t&&h[u]<h[t]){
h_swap(t,u);
up(t); //递归处理，直到不能上移
}
}
例题 839. 模拟堆
描述
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM输出样例：
-10
6代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10; //堆的大小
int idx,m; //idx表示当前的结点在数组中的下标，m表示插入的第m个数
int h[N],ph[N],hp[N];
void h_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]); //交换idx的映射关系
swap(hp[a],hp[b]); //交换m的映射关系
swap(h[a],h[b]); //交换值
}
void down(int u){
int t=u;
int p=u*2; //p表示左儿子节点的下标 p+1表示右儿子
if(p<=idx&&h[p]<h[t]) t=p;
if(p+1<=idx&&h[p+1]<h[t]) t=p+1;
if(t!=u){
h_swap(t,u);
down(t); //递归处理，直到不能下移
}
}
void up(int u){
int t=u>>1;
if(t&&h[u]<h[t]){
h_swap(t,u);
up(t); //递归处理，直到不能上移
}
}
int main(){
cin>>n;
while(n--){
string op;
int k,x;
cin>>op;
if(op=="I"){
cin>>x;
idx++,m++;
ph[m]=idx,hp[idx]=m; //记录映射关系
h[idx]=x; //在末尾插入x
up(idx); //上移x
}
else if(op=="PM"){
cout<<h[1]<<endl;
}
else if(op=="DM"){
h_swap(1,idx); //将最后插入的数覆盖h[1]
idx--;
down(1); //将改变后的h[1]下移
}
else if(op=="D"){
cin>>k;
k=ph[k]; //找到第k个数对应的idx
h_swap(k,idx); //将最后插入的数覆盖h[k]
idx--;
down(k); //将改变后的h[1]下移或上移动，down(k)和up(k)只会执行其一
up(k);
}
else{
cin>>k>>x;
k=ph[k],h[k]=x; //找到第k个数对应的idx，并将h[k]改变为x
down(k); //将改变后的h[k]下移或上移动，down(k)和up(k)只会执行其一
up(k);
}
}
return 0;
}2.5 哈希表
概念
- 对于处理复杂大量的信息，我们将这些信息映射到一个容易操作的区间内，如将
-1e9~1e9范围的数映射到0~1e5的范围内，以便于我们对这些数据进行插入，查询，删除等操作。
2.5.1 模拟散列表存储
操作思想(拉链法)
- 取质数
N = 1e6+3作为映射的标准(一般来说，质数造成的冲突更小) - 对于一组数据，将映射作为一维数组的下标来存储
- 如果对于两个不同的数据，他们的映射相同，则在该映射下新建一个结点来存储，解决冲突
模板
const int N=1e6+3; //映射的标准
int h[N],e[N],ne[N]; //h[N]存储映射，初始化为-1 e[N]存储原值 ne[N]存储下一个结点的指针
int idx; //充当指针作用
void init(){ //初始化操作
for(int i=0;i<N;i++) h[i]=-1;
}
void insert(int x){ //插入操作
int k=(x%N+N)%N; //对N取模，保证结果为正整数
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x){ //查询操作
int k=(x%N+N)%N; //找到映射的下标
for(int i=h[k];i!=-1;i=ne[i]){ //遍历映射，查询是否存在原值
if(e[i]==x) return 1;
}
return 0;
}例题 840. 模拟散列表
描述
维护一个集合，支持如下几种操作：
I x，插入一个数 x；Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
输出样例：
Yes
No代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int h[N],e[N],ne[N];
int idx;
void insert(int x){
int k=(x%N+N)%N;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x){
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i]){
if(e[i]==x) return 1;
}
return 0;
}
int main(){
for(int i=0;i<N;i++) h[i]=-1;
int n;
cin>>n;
while(n--){
char op[10];
int x;
scanf("%s %d",op,&x);
if(*op=='I'){
insert(x);
}
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}2.5.2 字符串前缀哈希
操作思想
- 把字符串变成一个
P进制数字，实现不同的字符串映射到不同的数字 - 对形如
X1 X2 X3⋯Xn−1 Xn的字符串,采用字符的ASCII码乘上P的次方来计算哈希值 - 映射处理为该哈希值对
Q进行取模:(X1 * P^n−1 + X2 * P^n−2+⋯+ Xn−1 * P^1 + Xn * P^0)%Q
注意点
- 任意字符不可以映射成
0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0 - 冲突问题：
P = (131 或 13331),Q = 2 ^ 64，一般情况下不产生冲突。 - 对于
Q取模，我们用unsigned long long自然溢出来解决
模板
typedef unsigned long long ULL;
const ULL N=1e6+3,P=131;
ULL h[N],p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
string s;
cin>>s; //读入字符串s
// 初始化前i个字符的哈希值
p[0]=1;
for(int i=1;i<=s.size();i++){
h[i]=h[i-1]*P+s[i]; //前缀和求整个字符串的哈希值
p[i]=p[i-1]*P; //存储每一位的权值
}
// 计算子串str[l~r]的哈希值
ULL find(int l, int r){
return h[r]-h[l-1]*p[r-l+1]; //将h[l-1]的高位与h[r]的最高位置的权值相对齐
}例题 841. 字符串哈希
描述
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2输出样例：
Yes
No
Yes代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1e6+3,P=131;
ULL h[N],p[N];
ULL find(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
p[0]=1;
for(int i=0;i<s.size();i++){
p[i+1]=p[i]*P;
h[i+1]=h[i]*P+s[i];
}
while(m--){
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
if(find(l1,r1)==find(l2,r2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}