基础算法篇(4)(蓝桥杯常考点)—数据结构（进阶）
前言
这期将会讲到基础算法篇里面的数据结构（进阶），主要包括单调栈，单调队列，并查集，扩展域并查集，带权并查集，字符串哈希，Trie树。
数据结构(进阶）正文
单调栈
里面存储的单增或者单减的栈
应用:
1.寻找当前元素左侧，离它最近，并且比它大的元素在哪
2.寻找当前元素左侧，离它最近，并且比它小的元素在哪
3.寻找当前元素右侧，离它最近，并且比它大的元素在哪
4.寻找当前元素右侧，离它最近，并且比它小的元素在哪
寻找当前元素左侧，离它最近，并且比它大的元素在哪 int a[N]里面存数（已存好） ret里面存的答案 stack<int>st;//维护一个单调递减的栈,里面存的是下标 for(int i = 1;i<=n;i++) { //栈里面小于等于a[i]的元素全部出栈 while(st.size()&&a[st.top()]<=a[i]) st.pop(); //此时栈顶元素存在，栈顶元素就是所求结果 if(st.size()) ret[i]=st.top(); st.push(i); } 寻找当前元素右侧，离它最近，并且比它大的元素在哪 改成for(int i = n;i>=1;i--) 寻找当前元素左侧，离它最近，并且比它小的元素在哪 int a[N]里面存数（已存好） ret里面存的答案 stack<int>st;//维护一个单调递增的栈，里面存的是下标 for(i=1;i<=n;i++) { //栈里面大于等于a[i]的元素全部出栈 while(st.size()&&a[st.top()]>=a[i])st.pop();//这里的符号是跟上面的唯一区别 //此时栈顶元素存在，栈顶元素就是所求结果 if(st.size()) ret[i]=st.top(); st.push(i); } 寻找当前元素右侧，离它最近，并且比它小的元素在哪 把上面改为for(int i=n;i>=1;i--)即可//n次逆遍历可以记一下是这个 总结: 找左侧，正遍历；找右侧，逆遍历； 比它大，单调减；比它小，单调增。//构造___栈 例题: 洛谷 P1901 发射站 单调队列
是一个存单调元素的双端队列
应用:解决滑动窗口内的最大值最小值问题
(前面基础算法的滑动窗口不是用来求其中的最值的)
例题：洛谷 P1886 滑动窗⼝ /【模板】单调队列 int a[N]里面存的元素(已存好) 窗口内最大值: 从左往右遍历元素，维护一个单调递减的双端队列 当前元素进队之后，注意维护队列内的元素在大小为k的窗口内 此时队头元素就是最大值 代码： deque<int>q;//存下标 for(int i = 1;i<=n;i++) { while(q.size()&&a[q.back()]<=a[i])q.pop_back(); q.push_back(i); if(q.back()-q.front()+1>k) q.pop_front(); if(i>=k)cout<<a[q.front()]<<" "; } 窗口内最小值: 从左往右遍历元素，维护一个单调递增的双端队列 当前元素进队之后，注意维护队列的元素在大小为k的窗口内 此时队头元素就是最小值 并查集
并查集是一种用于维护元素所属集合的数据结构，用双亲表示法来实现
应用eg:维护连通块的信息
相关的一些概念:
查询操作:查找元素x属于哪一个集合，一般会在每个集合中选取一个元素作为代码,查询的是这个集合中的代表元素
合并操作:将元素x所在的集合与元素y所在的集合合并成一个元素
(注意:合并的是元素所属的集合，而并非单单两个元素)
判断操作:判断元素x和y是否在同一个集合
并查集的实现: 例题：洛谷 P1551 亲戚 1.初始化:让元素自己指向自己即可 int fa[N];一般并查集用fa来表示 for(int i=1;i<=n;i++) fa[i] = i; 2.查询操作:就是一直向上"找爸爸"(这个find可以多次使用) int find(int x)//查询x所在集合的代表元素是谁 return fa[x] == x?x:find(fa[x]);//是x就返回x，不是就find(fa[x]) 3.合并操作:(重复合并不会出错) 让元素x所在集合的代表元素指向元素y所在集合的代表元素 void un(int x,int y) { int fx = find(x); int fy = find(y); fa[fx] = fy; } 4.判断操作 看看两者所在集合的总代表元素是否相同 bool issame(int x,int y) { return find(x) == find(y); } 扩展域并查集
元素之间存在多种关系比如:朋友和敌人 而不像上面只存在:亲戚这样一种关系的话，就要用扩展域并查集
和普通并查集的区别:将每个元素拆分成多个域，每个域代表⼀种状态或者关系
例题:洛谷 P1892 [BOI2003] 团伙 这里只写不同点: find和un与上面的写法一模一样 //两种关系，所以N*2：x的母敌人是x+n int fa[N*2]; //初始化: for(int i=1;i<=n*2;i++) fa[i]=i; while(m--)//m是题目中的"m个关系" { if(op == 'F') un(x,y); else//敌人，读取的是y和x是敌人关系 {//存法:这俩都得写，少一个都不行 un(x,y+n);//这两是朋友关系 un(y,x+n);//这两是朋友关系 } } 带权并查集
概念:就是在普通并查集的基础上，为每个结点增加一个权值。这个权值可以表示当前结点与父结点之间的信息(因为find那我们用的路径压缩，因为最终这个权值是当前结点相对于根节点的信息)
带权并查集的一些操作:(这里的d[N]以到父结点的距离为例) 例题:洛谷 P1196 [NOI2002] 银河英雄传说 新加了一个d[N] 1.初始化: 多初始化个d[i]即可 2.查询操作:(对这种代码来说，一个结点只能进行一次这种find操作!) int find(int x) { if(fa[x]==x) return x; int t = find(fa[x]);//这一步要先搞 d[x]+=d[fa[x]];//不为距离时可能会变为其他 return fa[x] = t;//完成路径压缩 } 3.合并操作://x所在集合与y所在集合合并，x与y之间的权值是w void un (int x,int y, int w) { int fx = find(x),fy = find(y); if(fx!=fy) { fa[fx] = fy; d[fx]= d[y]+w-d[x]; //可能会变，这里是拿距离举例的 } } 4.查询操作://查询y与x之间的距离 int query(int x,int y) { int fx = find(x),fy = find(y); //如果不在同一个集合中，说明距离未知(具体返回什么要看题意） if(fx!=fy)return 0x3f3f3f3f; return d[y]-d[x]; } 字符串哈希
一般利用前缀和思想去预处理字符串汇总每个前缀的哈希值
（使用前提:需要多次询问一个字符串的子串的哈希值）
核心思想:把字符串映射成P进制数字
P一般选择13331或者131
字符串哈希的作用:
字符串哈希一般用于判断两个字符串及其各子串是否相等
(和字典树的区别是这个字符串哈希侧重于判断功能)
例题:洛谷 P10468 兔⼦与兔⼦ 前缀字符串哈希模板: typedef unsigned lon long ULL; P = 13331; int len; string s;//一般都要搞一下s = ' '+s;来让i从1开始搞 ULL f[N];//前缀哈希数组 ULL p[N];//记录P的i次方－>p[i]为P的i次方 //处理前缀哈希数组以及P的i次方数组 void init_hash() { f[0] = 0;p[0] = 1; for(int i = 1;i<=len;i++) { f[i]=f[i-1]*P+s[i]; p[i]=p[i-1]*P; } } //快速求得任意区间的哈希值 ULL get_hash(int l,int r) { return f[r]-f[l-1]*p[r-l+1]; } 如果题目只是简单的求单个字符串的哈希值: ULL gethash() { ULL ret = 0; for(int i =1;i<=len;i++) { ret = ret*p+s[i]; } return ret; } Trie树（又叫字典树或前缀树）
是一种能够快速插入和查询字符串的数据结构
理解:我们可以把字典树想象成一颗多叉树，每一条边代表一个字符，从根节点到某个节点的路径就代表了一个字符串
作用:
1.查询某个单词是否出现过，并且出现几次
2.查询有多少个单词是以某个字符串为前缀
3.查询所有以某个前缀开头的单词
字典树的实现: 默认需要存的全是小写字母 1.准备工作 int tree[N][26],p[N],e[N];//N一般令为所有字符串中一共有多少个字符 // p[i]表示第i个被开辟的点被经过了多少次， //e[i]表示以第i个被开辟的点为结尾的有多少个 int idx; 2.插入字符串 void insert(string&s) { int cur = 0;//从根节点开始 p[cur]++;//这个格子经过一次 for(auto ch:s) { //这个path的表达式常改!!!依据题意改 int path = ch - 'a'; //如果没有路 if(tree[cur][path] == 0) tree[cur][path]= ++idx; cur = tree[cur][path]; p[cur]++ } e[cur]++; } 3.查询字符串出现的次数: int find(string&s) { int cur = 0; for(auto ch:s) { int path = ch - 'a'; if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return e[cur]; } 4.查询有多少个单词以字符串s为前缀: int find_pre(string&s) { int cur = 0; for(auto ch:s) { int path = ch-'a'; if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return p[cur]; } 例题:洛谷 P2580 于是他错误的点名开始了 
