栈
特性：Stack，先进先出的数据结构，一般采用数组模拟。
应用：普通栈的模拟（表达式计算、模拟）、单调栈（优化DP、模拟）、dfs模拟栈（虚树的构建）等。
表达式括号匹配，luogu1739
题解： 每出现一个左括号+1，每出现一个右括号且该变量大于0时-1.最后整个字符串判断完之后如果这个变量值为0则原表达式是匹配的
#include<cstdio> #include<queue> using namespace std; queue<char>a; int left,right,t; inline void read(){ char ch=getchar(); while(ch!='@')a.push(ch),ch=getchar(); } int main(){ read(); while(!a.empty()){ if(a.front()=='('){ ++left; ++t; } if(a.front()==')'){ ++right; if(t)--t; } a.pop(); } if(left==right&&t==0)printf("YES"); else printf("NO"); return 0; }
队列
特性：Queue，先进后出的数据结构，一般采用数组模拟。
应用：普通队列的模拟（模拟、广搜）、单调队列（优化DP、模拟）等。
Ps：优先队列挺好用的
滑动窗口，luogu1886
题解：单调队列模板
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; int n,m; int q1[1000001],q2[1000001]; int a[1000001]; int min_deque() { int h=1,t=0; for(int i=1;i<=n;i++) { while(h<=t&&q1[h]+m<=i) h++; while(h<=t&&a[i]<a[q1[t]]) t--; q1[++t]=i; if(i>=m) printf("%d ",a[q1[h]]); } cout<<endl; } int max_deque() { int h=1,t=0; for(int i=1;i<=n;i++) { while(h<=t&&q2[h]+m<=i) h++; while(h<=t&&a[i]>a[q2[t]]) t--; q2[++t]=i; if(i>=m) printf("%d ",a[q2[h]]); } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); min_deque(); max_deque(); return 0; }
链表与邻接表
特性：储存位置不连续，可在任意位置删除或插入元素的数据结构，但只能按顺序访问；一般采用数组模拟。对于邻接表，实质上也是链表，相当于就是把多个链表接到一个数组head上，从head[i]开始可以依次遍历挂在head[i]上的元素。
应用：普通链表的模拟（模拟）、树与图的存储方式等。
队列安排，luogu1160
题解：因为n还是比较大的(n<=100000),又因为要不停的插入和删除，所以我们可以用链表。读入每一个同学时，都把他左边和右边的同学更新；删除同学时，先把这个同学赋为0，再把他左边的同学连上右边的同学；最后找到排在最左边的同学，挨个输出
#include<cstdio> #include<cstring> int a[100010][3],n,m; int main() { scanf("%d",&n); int j=1; memset(a,0,sizeof(a)); a[1][1]=1; for(int i=2;i<=n;i++) { int x,y; scanf("%d %d",&x,&y); a[i][1]=i; if(y==0) { a[a[x][3]][2]=i; a[i][2]=x; a[i][3]=a[x][3]; a[x][3]=i; if(x==j) j=i; } else { a[i][2]=a[x][2]; a[a[x][2]][3]=i; a[x][2]=i; a[i][3]=x; } } scanf("%d",&m); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); if(a[x][1]!=0) { a[x][1]=0; a[a[x][3]][2]=a[x][2]; a[a[x][2]][3]=a[x][3]; n--; if(x==j) j=a[x][3]; } } int i=1,x=j; while(i<=n) { printf("%d ",a[x][1]); x=a[x][2]; i++; } return 0; }
后缀数组
定义：对于一个字符串S，把它的所有后缀按字典序排列后，排名为i的后缀记为SA[i]，排名i与i−1的最长公共前缀的长度记为Height[i]
实现：这里只讨论O(nlong2n)的实现
在之前求字符串S的Hash时我们已经知道了它所有前缀的Hash值，所以在sort中我们可以二分出第一个不相同的位置，然后进行比较。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define BASE 133 #define ll long long #define ull unsigned long long const int N = 300000 + 7; using std :: sort; inline int read() { int res = 0; bool f = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); } while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); } return f ? (~ res + 1) : res; } char s[N]; int n, sa[N]; ull p[N], f[N]; inline int min(int a, int b) { return a < b ? a : b; } inline bool check(int l1, int r1, int l2, int r2) { ull t1 = f[r1] - f[l1] * p[r1 - l1]; ull t2 = f[r2] - f[l2] * p[r2 - l2]; return t1 == t2; } inline int get(int a, int b) { int l = 0, r = min(n - a, n - b), mid; while (l < r) { mid = (l + r + 1) >> 1; if (check(a, a + mid, b, b + mid)) l = mid; else r = mid - 1; } return l; } inline bool cmp(int rk1, int rk2) { int l = get(rk1, rk2); return s[rk1 + l] < s[rk2 + l]; } int main(){ scanf("%s", s); n = strlen(s); p[0] = 1; for (int i = 1;i <= n; ++i) { f[i] = f[i - 1] * BASE + s[i - 1] - 'a' + 1; p[i] = p[i - 1] * BASE; sa[i] = i - 1; } sort(sa + 1, sa + 1 + n, cmp); for (int i = 1;i <= n; ++i) printf("%d ", sa[i]); puts(""); printf("0 "); for (int i = 2;i <= n; ++i) printf("%d ", get(sa[i - 1], sa[i])); return 0; }
KMP算法
问题： 字符串匹配
inline void KMP() { ans[1] = 1; memset(f, 0, sizeof f); for (int i = 2, j = 0;i <= m; ++i) { while (j && p[j + 1] != p[i]) j = f[j]; if (p[j + 1] == p[i]) ++j; f[i] = j, ans[i] = ans[j] + 1; } res = 1; for (int i = 2, j = 0;i <= m; ++i) { while (j && p[j + 1] != p[i]) j = f[j]; if (p[j + 1] == p[i]) ++j; while ((j << 1) > i) j = f[j]; res = (res * (ll)(ans[j] + 1) % P) % P; } }
并查集
特性：“名副其实”。维护不相交集合的信息，快速判断连通性，有两个基本操作，find，确定元素属于哪个集合，merge，合并子集。
理解：并查集实际上是维护了一个森林，同一棵树上的节点处于同一个集合。
小进阶：带权并查集、按秩合并、路径压缩。。。
应用：
在Kruskal最小生成树算法中，用于快速判断一条边的两个端点是否属于一个联通块。
维护区间关系。
并查集模板，luogu3367
#include<bits/stdc++.h> using namespace std; int i,j,k,n,m,s,ans,f[10010],p1,p2,p3; int find(int k){ if(f[k]==k)return k; return f[k]=find(f[k]); } int main() { cin>>n>>m; for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++){ cin>>p1>>p2>>p3; if(p1==1) f[find(p2)]=find(p3); else if(find(p2)==find(p3)) printf("Y "); else printf("N "); } return 0; }
树状数组
模板luogu3374
特性：运用了二进制思想，lowbit(x)表示十进制数xx在二进制下最后一位1所在的位置的十进制数表示，能够快速维护所有满足前缀可加性的运算。其实也可以用类似于二分的思想让树状数组维护其他一些奇奇怪怪的东西。。。
应用：
求逆序对。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; int n,m,tree[2000010]; int lowbit(int k) { return k & -k; } void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x); } } int sum(int x) { int ans=0; while(x!=0) { ans+=tree[x]; x-=lowbit(x); } return ans; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { int a; scanf("%d",&a); add(i,a); } for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a==1) add(b,c); if(a==2) cout<<sum(c)-sum(b-1)<<endl; } }
线段树
线段树模板，luogu3372
#include "bits/stdc++.h" using namespace std; typedef long long LL; const int MAXN = 100010; struct Node { int l, r; LL lazy; LL sum; } segTree[MAXN * 4]; void build(int i, int l, int r) { segTree[i].l = l; segTree[i].r = r; if (l == r) { scanf("%lld", &segTree[i].sum); return; } int mid = l + r >> 1; build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r); segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum; } void push_up(int i, LL v) { segTree[i].sum += (segTree[i].r - segTree[i].l + 1) * v; segTree[i].lazy += v; } void push_down(int i) { if (segTree[i].l == segTree[i].r) return; push_up(i << 1, segTree[i].lazy); push_up(i << 1 | 1, segTree[i].lazy); segTree[i].lazy = 0; } void add(int i, int l, int r, LL v) { if (segTree[i].l >= l && segTree[i].r <= r) { push_up(i, v); return; } push_down(i); int mid = segTree[i].l + segTree[i].r >> 1; if (mid >= l) add(i << 1, l, r, v); if (mid < r) add(i << 1 | 1, l, r, v); segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum; } LL query(int i, int l, int r) { if (segTree[i].l == l && segTree[i].r == r) return segTree[i].sum; push_down(i); int mid = segTree[i].l + segTree[i].r >> 1; if (r <= mid) return query(i << 1, l, r); else if (l > mid) return query(i << 1 | 1, l, r); else return query(i << 1, l, mid) + query(i << 1 | 1, mid + 1, r); } int main() { int n, m, op; scanf("%d%d", &n, &m); build(1, 1, n); int l, r; LL v; while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d%d%lld", &l, &r, &v); add(1, l, r, v); } else { scanf("%d%d", &l, &r); printf("%lld ", query(1, l, r)); } } return 0; }
LCA
最近公共祖先 一棵有根树上两个结点 u,v 的 LCA(u,v) 指的是同为 uu 和 vv 的祖先中深度最大的那个结点。
一般用三种方法解决
倍增
这个算法应该是最容易想到的，因为它本质上属于暴力算法的优化版本，只是把暴力算法的一次只跳一步变为了一次跳 2^k步
const int MAXN=5e4+10; const int DEG=20; struct Edge{ int to,next; }edge[MAXN<<1]; int head[MAXN],tot; void addedge(int u,int v){ edge[tot]=(Edge){v,head[u]}; head[u]=tot++; edge[tot]=(Edge){u,head[v]}; head[v]=tot++; } void init(){ tot=0; memset(head,-1,sizeof(head)); } int fa[MAXN][DEG]; int dep[MAXN]; void bfs(int r){ dep[r]=0; fa[r][0]=r; queue<int> Q; Q.push(r); while(!Q.empty()){ int u=Q.front();Q.pop(); for (int i=1;i<DEG;++i) fa[u][i]=fa[fa[u][i-1]][i-1]; for (int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if (v==fa[u][0]) continue; dep[v]=dep[u]+1; fa[v][0]=u; Q.push(v); } } } int LCA(int u,int v){ if (dep[u]>dep[v]) swap(u,v); int hu=dep[u],hv=dep[v]; int uu=u,vv=v; for (int det=hv-hu,i=0;det;det>>=1,++i) if(det&1) vv=fa[vv][i]; if (uu==vv) return uu; for (int i=DEG-1;i>=0;--i){ if (fa[uu][i]==fa[vv][i]) continue; uu=fa[uu][i]; vv=fa[vv][i]; } return fa[uu][0]; }
dfs+st
该算法的思想为，按照欧拉序存储结点的深度，则 LCA(u,v) 就是欧拉序上 u 所在位置到 v 所在位置区间上的最小值。
Tarjan
该算法的思想为，对于任意一个结点 r，处于 r 的不同子树上的两个结点
u,v ，一定有 LCA(u,v)=r
因此，我们可以暂时忽略询问中 u 和 v 的具体位置，而只是关心它们是否在某结点的不同子树中。
树链剖分
顾名思义，树链剖分就是指将一颗树分成若干条链，使得可以使用数据结构（例如线段树，主席树）来进行维护
它的特点很明显，我们可以非常便捷的处理同一条链上的若干点和边
首先我们要对每个节点进行编号，保证在链上的节点编号是连续的，这样子树的编号也是连续的
那么我们每次对x，y两个点进行询问
若两点在同一条链上，则直接在线段树上进行询问
若不在一条链上，则每次选择链头深度更大的一个往上跳，直到两点在同一条链上