数据结构--算法篇
1 单调栈
1.1 什么是单调栈
单调栈，顾名思义，就是具有单调性的栈。它依旧是⼀个栈结构，只不过⾥⾯存储的数据是递增或者
递减的。这种结构是很容易实现的（如下⾯的代码），但重点是维护⼀个单调栈的意义是什么？
单调栈解决的问题
单调栈能帮助我们解决以下四个问题：
• 寻找当前元素左侧，离它最近，并且⽐它⼤的元素在哪；
• 寻找当前元素左侧，离它最近，并且⽐它⼩的元素在哪；
• 寻找当前元素右侧，离它最近，并且⽐它⼤的元素在哪；
• 寻找当前元素右侧，离它最近，并且⽐它⼩的元素在哪。
虽然是四个问题，但是原理是⼀致的。因此，只要解决⼀个，举⼀反三就可以解决剩下的⼏个。
1.2 发射站
https://www.luogu.com.cn/problem/P1901
1.3 代码
2.单调队列
单调队列，顾名思义，就是存储的元素要么单调递增要么单调递减的队列。注意，这⾥的队列和普通的队列不⼀样，是⼀个双端队列。
⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题，以及优化动态规划。
2.1 滑动窗口 /【模板】单调队列
2.2 代码
2.3 质量检测
https://www.luogu.com.cn/problem/P2251
2.4 代码
3、并查集
3.1 双亲表⽰法
接下来要学习到的并查集，本质上就是⽤双亲表⽰法实现的森林。因此，我们先认识⼀下双亲表⽰
法。
在学习树这个数据结构的时，讲到树的存储⽅式有很多种：孩⼦表⽰法，双亲表⽰法、孩⼦双亲表⽰
法以及孩⼦兄弟表⽰法等。对⼀棵树⽽⾔，除了根节点外，其余每个结点⼀定有且仅有⼀个双亲，双
亲表⽰法就是根据这个特点存储树的，也就是把每个结点的双亲存下来。因此，我们可以采⽤数组来
存储每个结点的⽗亲结点的编号，这就实现了双亲表⽰法(so easy)。
但是，在实现并查集的时，我们⼀般让根节点⾃⼰指向⾃⼰。因此，上述存储就变成：
3.2 并查集的概念
在有些问题中，我们需要维护若⼲个集合，并且基于这些集合要频繁执⾏下⾯的操作：
• 查询操作：查找元素 x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表，查询的是
这个集合中的代表元素；
• 合并操作：将元素 x 所在的集合与元素 y 所在的集合合并成⼀个集合；（注意，合并的是元素所
在的集合，不是这两个元素！）
• 判断操作：判断元素 x 和 y 是否在同⼀个集合。
并查集（Union Find）：是⼀种⽤于维护元素所属集合的数据结构，实现为⼀个森林，其中每棵树表
⽰⼀个集合，树中的节点表⽰对应集合中的元素，根节点来代表整个集合。
3.3 并查集的实现
#include<iostream>
using namespace std;
const int N=2e5+10;
int n,k;
int f[N];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) f[i]=i;
while(k--)
{
int z,x,y;
cin>>z>>x>>y;
if(z==1)
{
int xx=find(x),yy=find(y);
f[xx]=yy;
}
else
{
if(find(x)==find(y))
cout<<'Y'<<endl;
else
cout<<'N'<<endl;
}
}
return 0;
}
3.4 亲戚
https://www.luogu.com.cn/problem/P1551
代码
#include<iostream>
using namespace std;
int n,m,p;
const int N=5010;
int f[N];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++) f[i]=i;
while(m--)
{
int x,y; cin>>x>>y;
int xx=find(x),yy=find(y);
f[yy]=xx;
}
while(p--)
{
int x,y; cin>>x>>y;
if(find(x)==find(y))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
4. 扩展域并查集
4.1 团伙
https://www.luogu.com.cn/problem/P1892
代码
#include<iostream>
using namespace std;
int n,m;
const int N=1e3+10;
int f[N*2];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void uni(int x,int y)
{
int xx=find(x),yy=find(y);
f[yy]=xx;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=2*n;i++) f[i]=i;
while(m--)
{
char ch;
int x,y;
cin>>ch>>x>>y;
if(ch=='E')
{
uni(x,y+n);
uni(y,x+n);
}
else
{
uni(x,y);
}
}
int ret=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i) ret++;
}
cout<<ret;
return 0;
}
5、带权并查集
5.1 食物链
代码
#include <iostream>
using namespace std;
int n,k;
const int N=5e4+10;
int f[N],d[N];
int find(int x)
{
if(f[x]==x) return x;
int t=find(f[x]);
d[x]+=d[f[x]];
return f[x]=t;
}
void uni(int x,int y,int w)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
f[fx]=fy;
d[fx]=d[y]+w-d[x];
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) f[i]=i;
int ret=0;
while(k--)
{
int op,x,y; cin>>op>>x>>y;
int fx=find(x),fy=find(y);
if(x>n||y>n) ret++;
else if(op==1)
{
if(fx==fy&&((d[y]-d[x])%3+3)%3!=0) ret++;
else uni(x,y,0);
}
else
{
if(fx==fy&&((d[y]-d[x])%3+3)%3!=1) ret++;
else uni(x,y,2);
}
}
cout<<ret;
return 0;
}
5.2 银河英雄传说
https://www.luogu.com.cn/problem/P1196
代码
#include<iostream>
#include<cmath>
using namespace std;
const int N=3e4+10;
int f[N],d[N],cnt[N];
int t;
int find(int x)
{
if(f[x]==x) return x;
int t=find(f[x]);
d[x]+=d[f[x]];
return f[x]=t;
}
void uni(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
f[fx]=fy;
d[fx]=cnt[fy];
cnt[fy]+=cnt[fx];
}
}
void quary(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy) cout<<-1<<endl;
else
{
cout<<abs(d[x]-d[y])-1<<endl;
}
}
int main()
{
for(int i=1;i<=N;i++)
{
f[i]=i;
cnt[i]=1;
}
cin>>t;
while(t--)
{
char op; int x,y;
cin>>op>>x>>y;
if(op=='M')
{
uni(x,y);
}
else
{
quary(x,y);
}
}
return 0;
}
6 字符串哈希
6.1 字符串哈希（模版）
代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N=1e4+10;
int n;
ULL p[N];
int k=131;
ULL gethash(string &s)
{
ULL ret=0;
for(int i=1;i<=s.size();i++)
{
ret=ret*k+s[i-1];
}
return ret;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s; cin>>s;
p[i]=gethash(s);
}
sort(p+1,p+1+n);
int ret=1;
for(int i=2;i<=n;i++)
if(p[i]!=p[i-1]) ret++;
cout<<ret;
return 0;
}
6.2 兔子与兔子
https://www.luogu.com.cn/problem/P10468
代码
#include<iostream>
using namespace std;
const int N=1e6+10;
typedef unsigned long long ULL;
ULL f[N],p[N];
int m,n;
int k=131;
string s;
void init_hash()
{
p[0]=1;
for(int i=1;i<=n;i++)
{
f[i]=f[i-1]*k+s[i];
p[i]=p[i-1]*k;
}
}
ULL gethash(int l,int r)
{
return f[r]-f[l-1]*p[(r-l+1)];
}
int main()
{
cin>>s;
cin>>m;
n=s.size();
s=" "+s;
init_hash();
while(m--)
{
int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;
ULL x=gethash(l1,r1),y=gethash(l2,r2);
if(x==y) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
7.trie树
7.1 字典树（模版）
https://www.luogu.com.cn/problem/P8306
代码
#include<iostream>
using namespace std;
const int N=3e6+10;
int tree[N][62];
int p[N];
int n,q,indx;
int get_num(char ch)
{
if(ch>='a'&&ch<='z') return ch-'a';
else if(ch>='A'&&ch<='Z') return ch-'A'+26;
else return ch-'0'+52;
}
void insert(string &s)
{
int cur=0;
p[cur]++;
for(auto &c: s)
{
int path=get_num(c);
if(tree[cur][path]==0) tree[cur][path]=++indx;
cur=tree[cur][path];
p[cur]++;
}
}
int find(string &s)
{
int cur=0;
for(auto &c: s)
{
int path=get_num(c);
if(tree[cur][path]==0) return 0;
cur=tree[cur][path];
}
return p[cur];
}
int main()
{
int T; cin>>T;
while(T--)
{
for(int i=0;i<=indx;i++)
for(int j=0;j<62;j++)
tree[i][j]=0;
for(int i=0;i<=indx;i++) p[i]=0;
indx=0;
cin>>n>>q;
while(n--)
{
string s; cin>>s;
insert(s);
}
while(q--)
{
string s; cin>>s;
cout<<find(s)<<endl;
}
}
return 0;
}