单调栈
单调栈的定义是：栈内元素一定是单调的。这个性质有助于排除更劣的选择，来优化时间和空间。
单调栈经典例题就是往后看看到的最高元素。如果一个元素要入栈，比前面的元素都要大，那么前面的元素一定看不到栈内元素而是那个最高的元素，就可以把末尾的元素弹出了。
例题
考虑 $dp_i$ 表示当前扫到第 $i$ 个位置，最少的分割次数，此外，维护两个单调栈 $stk1$ 和 $stk2$ 表示单调递增的数和单调递减的数，很明显，当 $i$ 是一个序列的开头且仅当 $i$ 在里面是最小的。往后看没有比它小的数。如果有更小的，那就再前面找最大的。很明显，维护的两个东西就有用了，由于是单调的，所以可以二分。
dp[i]=dp[*lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1]+1;
#include<bits/stdc++.h>
#define MAXN 300003
using namespace std;
int n,top1,top2,a[MAXN],stk1[MAXN],stk2[MAXN],dp[MAXN];
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}for(int i=1;i<=n;++i){while(top1&&a[stk1[top1]]<=a[i]){--top1;}stk1[++top1]=i;while(top2&&a[stk2[top2]]>a[i]){--top2;}stk2[++top2]=i;dp[i]=dp[*lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1]+1;}printf("%d",dp[n]);return 0;
}
单调队列
单调队列和单调栈类似，队列内的元素一定是单调的，不同点是队头如果到了一定时间就会弹出。像一个窗口，单调栈就是将窗口扩宽，而单调队列就是在滑动窗口。
单调队列的元素遵循一条规则：如果一个 OIer 比你小，还比你强，那你就可以退役了。如果一个后于你的元素比你大，那么你一定在剩余的区间里面不可能是最大的了，就可以弹出队尾。而你是因为年龄退役的，那就弹出对头。这个需要用到 std::deque 来实现。
例题
套用单调队列模板即可。
#include<bits/stdc++.h>
#define MAXN 1000001
using namespace std;
int a[MAXN],ans[MAXN];
int main(){int n,m;scanf("%d %d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}deque<pair<int,int> > q;for(int i=1;i<m;++i){while(!q.empty()&&q.back().second>=a[i]){q.pop_back();}q.push_back(make_pair(i,a[i]));}for(int i=m;i<=n;++i){while(!q.empty()&&q.back().second>=a[i]){q.pop_back();} q.push_back(make_pair(i,a[i]));while(!q.empty()&&i-q.front().first>=m){q.pop_front();}ans[i]=q.front().second;}for(int i=m;i<=n;++i){printf("%d ",ans[i]);}putchar('\n');q.clear(); for(int i=1;i<m;++i){while(!q.empty()&&q.back().second<=a[i]){q.pop_back();}q.push_back(make_pair(i,a[i]));}for(int i=m;i<=n;++i){while(!q.empty()&&q.back().second<=a[i]){q.pop_back();}q.push_back(make_pair(i,a[i]));while(!q.empty()&&i-q.front().first>=m){q.pop_front();}ans[i]=q.front().second;}for(int i=m;i<=n;++i){printf("%d ",ans[i]);}
}
此外，单调队列还可以优化形如 $\max_{i=1}^k(dp_i)$ 之类的 dp 转移式。
并查集
并查集是用来维护连通性一类题目的数据结构，思想是合并两个状态就相当于把两棵树合并起来，结构类似于森林。
并查集初始化是将所有节点的父亲赋予成不同的值，通常赋值为自己。然后每一次查询自己的最大祖先，就不断地向上递归，如果查询到了一个父亲是自己的点，就说明这是祖先。合并两个点就是将一个点的父亲赋予成另一个点。
int fa[MAXN];//表示父亲
inline void prework(){for(int i=1;i<MAXN;++i){fa[i]=i;//赋予节点 }
}
int find(int x){if(fa[x]==x){//祖先 return x;}return find(fa[x]);//向上递归
}
inline void merge(int x,int y){fa[x]=y;//改变父亲
}
路径压缩
不妨改变一下 $fa$ 的定义，变成最早的祖先，那么其实可以在 $find$ 的过程中间就把路上所有的点的祖先节点赋予成最早的祖先，这样压缩可以把原来很不稳定的复杂度优化到 $\log$ 级别的。
int find(int x){if(fa[x]==x){//祖先 return x;}return fa[x]=find(fa[x]);//向上递归，路径压缩
}
按秩合并
和上面的思想一样，都是在 $fa$ 数组有改变的情况下使用：直接合并两个点的祖先节点。虽然对于 $merge$ 函数不会比以前的更优，但是对于后面的查询有很大的增益。
inline void merge(int x,int y){fa[find(x)]=find(y);//改变祖先，按秩合并
}
例题
考虑对每一个洞进行编号，$fa$ 维护的是两个洞能不能够互相到达。如果相邻的两个洞能够互相到达，那么就合并两个洞。最后看最底下能不能和最上面的伪洞连通即可。
#include<bits/stdc++.h>
#define MAXN 1002
using namespace std;
int x[MAXN],y[MAXN],z[MAXN],fa[MAXN];
int get(int x){if(fa[x]==x){return x;}return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){fa[get(x)]=get(y);
}
int main(){int t;scanf("%d",&t);while(t--){int n,h,r;scanf("%d %d %d",&n,&h,&r);for(int i=0;i<MAXN;++i){fa[i]=i;}for(int i=1;i<=n;++i){scanf("%d %d %d",&x[i],&y[i],&z[i]);if(z[i]-r<=0){merge(0,i);}if(z[i]+r>=h){merge(i,min(MAXN-1,h));}}for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){if(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2)+pow((z[i]-z[j]),2)<=4ll*r*r){merge(i,j);}}}if(get(0)==get(min(MAXN-1,h))){puts("Yes");}else{puts("No");}}return 0;
}
种类并查集
有的时候，并查集要维护多种信息。比如对于有向图，要维护 $u$ 节点能不能到达 $v$ 节点的 $fa_u$ 和 $fa_v$，还有 $u$ 节点往后能不能到达 $v$ 的 $fa_v$ 和 $fa_u$，这时候就需要用到种类并查集来回鹘不同的信息。
例题
考虑用并查集维护 $x$ 和 $y$，维护下面三种关系：
- $x$ 和 $y$ 是同类。
- $x$ 吃 $y$。
- $y$ 吃 $x$。
每一对 ${x,y}$ 只有以上三种情况的一种，所以需要用到种类并查集。
#include<bits/stdc++.h>
#define MAXN 50005
using namespace std;
int fa[MAXN*3];
int find(int x){if(fa[x]==x){return fa[x];}return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){fa[find(y)]=find(x);
}
int main(){int n,m,ans=0;scanf("%d %d",&n,&m);for(int i=1;i<=n*3;++i){fa[i]=i;}while(m--){int opt,x,y;scanf("%d %d %d",&opt,&x,&y);if(x>n||y>n){++ans;continue;}if(opt==1){if(find(x+n)==find(y)||find(y+n)==find(x)){++ans;}else{merge(x,y);merge(x+n,y+n);merge(x+n+n,y+n+n);}}else{if(find(x)==find(y)||find(x)==find(y+n)){++ans;}else{merge(x+n,y);merge(x+n+n,y+n);merge(x,y+n+n);}}}printf("%d",ans);return 0;
}
带权并查集
可以对并查集里面每一个元素定义一种权值 $val$，然后再规定 $find$ 和 $merge$ 怎么转移。对于一些题目就能够在维护并查集的同时维护权值了。
例题
这一道题目要求合并两个元素并查询两个元素的距离。考虑用 $front$ 来维护它与根节点的距离，用 $front_r-front_{l-1}$ 可以实现。再维护一个 $size$，表示这个集体有多少个元素了，这样可以便于 $front$ 的传递。
#include<bits/stdc++.h>
#define MAXN 300003
using namespace std;
int fa[MAXN],front[MAXN],size[MAXN];
inline int get(int x){if(fa[x]==x){return x;}int f=get(fa[x]);front[x]+=front[fa[x]];return fa[x]=f;
}
int main(){int t;scanf("%d",&t);for(int i=1;i<MAXN;++i){fa[i]=i;front[i]=0;size[i]=1;}while(t--){char c;int x,y;scanf("\n%c %d %d",&c,&x,&y);int fx=get(x);int fy=get(y);if(c=='M'){front[fx]+=size[fy];fa[fx]=fy;size[fy]+=size[fx];}else{if(fx!=fy){puts("-1");}else{printf("%d\n",abs(front[x]-front[y])-1);}}}return 0;
}
ST 表
ST 表是用于维护 RMQ(Range Min/Max Query) 类型的问题，结合倍增的思想，可以用 $\operatorname{O}(n\log n)$ 的时间预处理，$\operatorname{O}(1)$ 的复杂度查询，可以维护区间 $\max$，$\min$，$\gcd$，$\operatorname{lcm}$ 等函数值。
ST 表用 $st_{i,j}$ 表示，$st_{i,j}(1\le i+2^j\le n)$ 表示 $i$ 往后跳 $j$ 步的值，也就是 $f(a_{i+1},a_{i+2},a_{i+3}\dots a_{i+2^j})$。很明显，上述的函数对于 $f(a_1,a_2,a_2,a_3)$ 等同于 $f(a_1,a_2,a_3)$，所以可以选定最大的 $log$ 来合并答案，即 $f(st_{i,i+2{log}},st_{j-2,j})$。
int st[MAXN][MAXM],logn[MAXN];//st 表、log 预处理数组，st[i][0] 表示原数
inline void prework(){for(int i=2;i<MAXN;++i){logn[i]=logn[i>>1]+1;//预处理 }for(int i=1;i<MAXM;++i){for(int j=1;j<MAXN-(1<<i)+1;++j){st[j][i]=f(st[j][i-1],st[j+(1<<(i-1))][i-1]);//st 表预处理 }}
}
inline int query(int l,int r){int k=logn[r-l+1];return f(st[l][k],st[r-(1<<(k-1))+1][k]);//合并答案
}
例题
首先，需要使用前缀和来维护区间和。然后，可以考虑创建三元组 $(l,r,pos)$ 表示这一段区间左端点为 $pos$，右端点在 $l$ 和 $r$ 之间，和为 $pre_{best}-pre_{pos-1}$。$pos-1$ 是固定的，我们要找出最大的 $pre_{best}$，这可以用 ST 表来维护。之后，把答案存入堆中，每次加最大的答案，每一个答案还可以扩展成子区间，因为子区间的和一定等于这个优秀的答案，所以这是贪心。
#include<bits/stdc++.h>
#define MAXN 500005
#define MAXM 25
using namespace std;
typedef long long ll;
int st[MAXN][MAXM],logn[MAXN];
int n,m,l,r,a[MAXN],pre[MAXN];
inline void prework(int n){logn[0]=-1;for(int i=1;i<=n;++i){logn[i]=logn[i>>1]+1;st[i][0]=i;}logn[0]=0;for(int i=1;(1<<i)<=n;++i){for(int j=1;j<=n-(1<<i)+1;++j){int x=st[j][i-1],y=st[j+(1<<(i-1))][i-1];if(pre[x]>pre[y]){st[j][i]=x;}else{st[j][i]=y;}}}
}
inline int query(int l,int r){int k=logn[r-l+1];int x=st[l][k],y=st[r-(1<<k)+1][k];if(pre[x]>pre[y]){return x;}return y;
}
struct node{int l,r,pos,best;inline int val(){return pre[best]-pre[pos-1];}
};
inline bool operator<(node x,node y){return x.val()<y.val();
}
int main(){scanf("%d %d %d %d",&n,&m,&l,&r);for(int i=1;i<=n;++i){scanf("%d",&a[i]);pre[i]=pre[i-1]+a[i];}prework(n);priority_queue<node> q;for(int i=1;i<=n;++i){if(i+l-1<=n){int pl=i+l-1,pr=min(i+r-1,n);q.push((node){pl,pr,i,query(pl,pr)});}}ll ans=0;while(!q.empty()&&m--){node top=q.top();q.pop();ans+=top.val();if(top.l!=top.best){q.push((node){top.l,top.best-1,top.pos,query(top.l,top.best-1)});}if(top.r!=top.best){q.push((node){top.best+1,top.r,top.pos,query(top.best+1,top.r)});}}printf("%lld",ans);return 0;
}
线段树
线段树是基于分治的思想的一种树据结构，思想是把全部区间分成 $\log n$ 层，每一个大区间可以用两个小区间合并，并且每一个数在不超过 $\log n$ 个区间里面出现。
线段树是一个优秀的树据结构，除了空间 $4$ 倍常数和时间 $9$ 倍常数之外，能够维护动态区间值，复杂度在 $\log n$ 以内，是一个很优秀的结构。
首先，我们要确定节点编号顺序。通常来讲，我们定 $tree_1$ 为根节点，$tree_{x\times 2}$ 是 $x$ 的左子节点，$tree_{x\times 2+1}$ 是 $x$ 的右子节点。$tree_1$ 对应的区间是 $[1,n]$，$tree_2$ 对应的区间是 $[1,\lfloor\frac{n}{2}\rfloor]$，$tree_3$ 对应的区间是 $[\lfloor\frac{n}{2}\rfloor+1,n]$，以此类推……给出 RMQ 线段树的建树代码：
struct node{int l,r,maxi,mini;
}tree[MAXN<<2];//稍后解释为什么一定要开 4 倍
inline void push_up(int root);//稍后讲解
void build(int root,int l,int r){//l 和 r 表示到了那个区间 tree[root].l=l;tree[root].r=r;if(l==r){//形如 [1,1] 和 [2,2]，直接维护 tree[root].maxi=tree[root].mini=a[l];return;}int mid=(l+r)>>1;//分治build(root<<1,l,mid);//左子树build(root<<1|1,mid+1,r);//右子树push_up(root);
}
如果知道了 $[l1,r1]$ 和 $[l2,r2]$ 的维护信息并且有维护 $[l1,r2]$ 的区间，那么就可以向上推。这个过程叫做 $push_up$。给出维护 RMQ 线段树的 $push_up$ 代码：
inline void push_up(int root){tree[root].mini=min(tree[root<<1].mini,tree[root<<1|1].mini);//Range Min Querytree[root].maxi=max(tree[root<<1].maxi,tree[root<<1|1].maxi);//Range Max Query
}
如何查询？设 $query(root,l,r)$ 为当时查询到了下标为 $root$ 的线段树，要查询的为 $[l,r]$，分情况讨论。
首先，如果当前区间的右端点比查询的左端点还要更靠左，那么这个区间整体偏左，所以只能够向右查询，即 $query(root\times 2+1,l,r)$。
如果当前区间的左端点比查询的右端点还要更靠右，那么这个区间整体偏右，所以只能够向左查询，即 $query(root\times 2,l,r)$。
如果当前区间被包含在查询的区间，那么这整个区间都对答案有贡献，为 $tree_{root}$。
否则，两个子区间可能都有交集，所以两边都要查找。设 $merge(x,y)$ 为合并两个区间的答案的函数，那么为 $merge(query(root\times 2,l,r),query(root\times 2+1,l,r))$。
下面，给出 RMQ 的 $query$ 代码。
inline node merge(node x,node y){//有时候不用写得那么复杂 node res;res.maxi=max(x.maxi,y.maxi);//合并 1res.mini=min(x.mini,y.mini);//合并 2return res;
}
node query(int root,int l,int r){if(l<=tree[root].l&&tree[root].r<=r){return tree[root];//包含 }if(tree[root].r<l){return query(root<<1|1,l,r);//偏左 }if(r<tree[root].l){return query(root<<1,l,r)l//偏右 }return merge(query(root<<1,l,r),query(root<<1|1,l,r));//交集
}
$change$ 可以使用懒标记优化，即当时修改可以不用立即下传，当要查询的时候再下传。这可以保证 $change$ 不可能是 $n\log n$，而是 $\log n$ 的。因为如果修改 $[1,n]$，要修改所有区间，即 $n\log n$。而 $[1,n]$ 的情况是懒标记优化的最优情况，为 $\operatorname{O}(1)$。
inline void push_down(int root){if(tree[root].tag){tree[root<<1].tag=tree[root<<1|1].tag=tree[root].tag;//下传 }
}
void change(int root,int l,int r,int k){//将 [l,r] 修改成 k if(l<=tree[root].l&&tree[root].r<=r){tree[root].tag=k;return;} if(tree[root].r<l){change(root<<1|1,l,r);//偏左 }else if(r<tree[root].l){change(root<<1,l,r);//偏右 }else{change(root<<1,l,r);change(root<<1|1,l,r);//交集 }push_up(root);//上传
}
注意，再进行查询操作时，需要先 $push_down$，以免懒标记还未来得及下传。
例题
要求区间最大和，和 ST 表的那道题目如出一辙。考虑维护 $sum,maxl,maxr,maxi$ 表示区间和，左开始最大和，右开始最大和，全部最大和。
考虑怎么 $merge$：
- $sum$ 就对两个子区间加和。
- $maxl$ 可以为左区间的 $maxl$，也可以为左区间的 $sum$ 加上右区间的 $maxl$。
- $maxr$ 可以为左区间的 $maxr$ 加上右区间的 $sum$，也可以为右区间的 $maxr$。
- $maxi$ 可以为左区间的 $maxi$、右区间的 $maxi$ 或者左区间的 $maxr$ 加上右区间的 $maxl$。
这样就可以了，接下来用线段树维护即可。
#include<bits/stdc++.h>
#define MAXN 500005
#define INF INT_MIN
using namespace std;
struct node{int l,r,sum,maxl,maxr,maxi;inline int maxp(){return max(maxi,max(maxl,maxr));}
}tree[MAXN<<2];
inline void merge(node &res,node x,node y){res.sum=x.sum+y.sum;res.maxl=max(x.maxl,x.sum+y.maxl);res.maxr=max(x.maxr+y.sum,y.maxr);
// if(x.maxr<0&&y.maxl<0){
// res.maxi=max(x.maxr,y.maxl);
// }else{
// if(x.maxr<0){
// res.maxi+=x.maxr;
// }
// if(y.maxl<0){
// res.maxi+=y.maxl;
// }
// }
// res.maxi=max(res.maxi,max(x.maxi,y.maxi));res.maxi=max(x.maxr+y.maxl,max(x.maxi,y.maxi));
}
inline void pushup(int root){merge(tree[root],tree[root<<1],tree[root<<1|1]);
}
void build(int root,int l,int r){tree[root]=(node){l,r,0,INF,INF,INF};if(l==r){int val;scanf("%d",&val);tree[root]=(node){l,r,val,val,val,val};return;}int mid=(l+r)>>1;build(root<<1,l,mid);build(root<<1|1,mid+1,r);pushup(root);
}
void change(int root,int pos,int val){if(tree[root].l==tree[root].r){tree[root]=(node){tree[root].l,tree[root].r,val,val,val,val};return;}int mid=(tree[root].l+tree[root].r)>>1;if(pos<=mid){change(root<<1,pos,val);}else{change(root<<1|1,pos,val);}pushup(root);
}
node query(int root,int l,int r){if(l<=tree[root].l&&tree[root].r<=r){return tree[root];}int mid=(tree[root].l+tree[root].r)>>1;if(r<=mid){return query(root<<1,l,r);}else if(mid<l){return query(root<<1|1,l,r);}else{node res;merge(res,query(root<<1,l,r),query(root<<1|1,l,r));return res;}
}
int main(){int n,m;scanf("%d %d",&n,&m);build(1,1,n);while(m--){int opt;scanf("%d",&opt);if(opt==1){int l,r;scanf("%d %d",&l,&r);if(l>r){swap(l,r);}printf("%d\n",query(1,l,r).maxp());}else{int pos,k;scanf("%d %d",&pos,&k);change(1,pos,k);}}return 0;
}
