模板及讲解
运用st表实现区间询问区间最大/最小，初始化时间复杂度$O(nlogn)$, 查询$O(1)$
设$dp(i,j)$为从i开始长度为$2^j$的区间最小值，初始化合并结果即可，查询采用”两头补”方式
模板题：poj 3264
后缀数组 学习笔记
模板及讲解
性质
1、字符串中的子串可以表示为后缀的前缀，即后缀的LCP。
模板、代码
解决字符串的有力工具。
直接上代码，注释讲解(此题为uoj #35)
(注意：下标都是从0开始)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35"
using namespace std;
const int MAXN = 1000000 + 5;
char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串，a为处理后的整数原串
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
SA[i]: 排名第i的后缀的位置(下标是后缀排名)
rk[i]: 第i个后缀的排名
tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
tax[i]:基数排序的桶
height[i]: 排名为i, i-1后缀的最长公共前缀
*/
bool cmp(int *f, int i, int k) {return f[SA[i-1]]==f[SA[i]]&&f[SA[i-1]+k]==f[SA[i]+k];} //要判断两个字符串是否完全相等
void build() {//构造后缀数组
int i, p;
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
for (int i=0;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;//基数排序排第一轮
for (int k=1;k<=n;k*=2) {
p = 0;
for (int i=n-k;i<n;i++) tp[p++] = i;//(n-k)~(n-1)无第二关键字，所以排序应该排在前面
for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
//只有SA[i]>=k的SA[i]才是第二关键字的位置
//从图中可以看出第一关键字和第二关键字的位置相差k，故SA[i] - k
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];//保证了第一关键字的顺序再排第二关键字
//基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标)
swap(rk, tp);//此时tp没用，暂存上一轮rank的值
p = 0, rk[SA[0]] = 0;//sa[0]一定是添加的字符0, 排名一定是0
for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
//算排名第i的数的rank，按sa顺序能够保证rank的正确性，但是要cmp判断与上一个字符串相等的情况
if (++p>=n) break;//剪枝，已经没有重复元素
m = p;
}
}
void getH() {//算height
int i, j, k = 0;//k是比i-1前一名的后缀
for (int i=0;i<n;i++) {//H[0], H[1], H[2] ...的顺序计算
if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
j = SA[rk[i]-1]; //前一名的后缀位置
while(ch[i+k] == ch[j+k]) k++; //往后比较
height[rk[i]] = k; //更新答案
}
}
void init() {
int i;
n = strlen(ch) + 1, m = 128;
for (int i=0;i<n-1;i++) a[i] = ch[i];//处理原字符串
a[n - 1] = 0;//补末尾的0
}
void solve() {
int i;
build();
getH();
for (int i=1;i<n;i++) printf("%d ", SA[i]+1);//输出范围1~n-1
printf("\n");
for (int i=2;i<n;i++) printf("%d ", height[i]);
}
int main() {
scanf("%s", ch), init(), solve();
return 0;
}
从1开始的SA (不用补0)：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35"
using namespace std;
const int MAXN = 1000000 + 5;
char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串，a为处理后的整数原串
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
SA[i]: 排名第i的后缀的位置(下标是后缀排名)
rk[i]: 第i个后缀的排名
tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
tax[i]:基数排序的桶
height[i]: 排名为i, i-1后缀的最长公共前缀
*/
void build() {//构造后缀数组
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//基数排序排第一轮
for (int k = 1; k <= n; k *= 2) {
int p = 0;
for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)无第二关键字，所以排序应该排在前面
for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
//只有SA[i]>=k的SA[i]才是第二关键字的位置
//从图中可以看出第一关键字和第二关键字的位置相差k，故SA[i] - k
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//保证了第一关键字的顺序再排第二关键字
//基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标)
swap(rk, tp);//此时tp没用，暂存上一轮rank的值
p = 1, rk[SA[1]] = 1;
for (int i = 2; i <= n; ++i)
rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
//算排名第i的数的rank，按sa顺序能够保证rank的正确性，但是要cmp判断与上一个字符串相等的情况
if (p >= n) break;//剪枝，已经没有重复元素
m = p;
}
}
void getH() {//算height
int k = 0;//k是比i-1前一名的后缀
for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...的顺序计算
if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
int j = SA[rk[i] - 1]; //前一名的后缀位置
while(ch[i + k] == ch[j + k]) k++; //往后比较
height[rk[i]] = k; //更新答案
}
}
void solve() {
n = strlen(ch + 1), m = 256;
for (int i = 1; i <= n; ++i) a[i] = ch[i];//处理原字符串
build();
getH();
for (int i = 1; i <= n; ++i) printf("%d ", SA[i]);
printf("\n");
for (int i = 2; i <= n; ++i) printf("%d ", height[i]);
}
int main() {
scanf("%s", ch + 1), solve();
return 0;
}
写时注意：
1、不要将字符对应到0
2、不同字符串之间一定要用不同字符连接
3、用不同字符串连接字符串后注意空间开大
生成树 学习笔记
模板及讲解
最小生成树：在一个图中选择$n-1$条边，使所有点连通且路径总权最小。常用算法是用并查集辅助求解的Kruskal
最小瓶颈路：求一条路径，使得$u−>v$路径上的最大边权最小。可以知道，最小瓶颈路必在最小生成树上，所以用最小生成树求解
最小生成树性质
1切割性质
2回路性质
3相同边权数量相等
4不同边权加入时互相独立
5不产生环的同权值边可以替换边
Kruskal 重构树
定义
在做 Kruskal 的时候，我们将边权转点权，得到$2n-1$个点的树。
构造方法
每次 Kruskal 时，如果当前边是需要的，那么我们建立一个新节点，节点权值为边权，然后从这个点向两边两个集合的并查集代表连边。
性质
1、是一棵树，并且是一个二叉堆
2、原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值
3、重构树中代表原最小生成树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。
例题
给你$N$个点的无向有边权图，图中有$M$条边，现在有$K$个询问，每个询问的格式是：
A B，表示询问从$A$点走到$B$点的所有路径中，最长的边最小值是多少？
最长的边最小值，我们考虑最小生成树。这题明显可以求出最小生成树，然后再在树上倍增 / 树剖求出最长的边。这里可以运用性质2，即原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值，那么我们构造出重构树，询问树上两点$\text{LCA}$的权值即为答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 30000 + 5, LOGS = 20;
struct edge {
int u, v, w;
bool operator < (const edge &rhs) const {return w < rhs.w;}
} ed[30000 + 5];
int n, m, Q, val[MAXN], f[MAXN], idx;
vector<int > G[MAXN];
int pre[MAXN][LOGS + 2], dep[MAXN];
void ins(int u, int v) {G[u].push_back(v);}
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void dfs(int u, int fa) {
pre[u][0] = fa, dep[u] = dep[fa] + 1;
for (int i = 1; i <= LOGS; ++i) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) dfs(v, u);
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = LOGS; i >= 0; --i) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i = LOGS; i >= 0; --i) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void clean() {
ms(val, 0), ms(f, 0);
ms(pre, 0), ms(dep, 0);
}
int solve() {
clean();
cin >> n >> m >> Q;
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
sort(ed + 1, ed + 1 + m), idx = n;
// Kruskal
int tot = 0;
for (int i = 0; i <= n * 2; ++i) f[i] = i;
for (int i = 1; i <= m; ++i) {
int x = find(ed[i].u), y = find(ed[i].v);
if (x != y) {
++idx;
ins(idx, f[x]), ins(idx, f[y]);
f[x] = f[y] = idx, val[idx] = ed[i].w;
++tot;
if (tot >= n - 1) break ;
}
}
// LCA
dfs(idx, 0);
while (Q--) {
int x, y; scanf("%d%d", &x, &y);
printf("%d\n", val[LCA(x, y)]);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
常见题型
1、求一个图的最小/大生成树
Q：给出一个图，求出这个图的最小/大生成树
解：见讲解
例题：BZOJ 2429
2、将一个图转为树
Q：给出一个图，图中只有使图连通的最大/小的那几条边有用
解：求最小/大生成树。
例题：NOIP2013 D1 T3
3、求一条路径使得最大边最小
Q：给出一个图，求一条路径使得$a->b$最大边最小(这种题的题面一般带有二分的标志：最大值最小)
解：最小瓶颈路。最大边最小的路径在最小生成树上。
例题：BZOJ 2429
4、最小生成树性质
Q：BZOJ 1016
解：BZOJ 1016
例题：BZOJ 1016
5、最小生成树-倍增 (回路性质)
Q：CF 609E
解：CF 609E
例题：CF 609E
前缀和与差分 学习笔记
模板及讲解
差分序列
差分序列$f$记录$a[i]-a[i-1]$的值，$a$为原序列
那么根据定义可以发现差分序列的前缀和就是原序列的数
那么输入$a,b$, 我们让$f[a]+1, f[b+1]-1$就可以构造出差分序列
这样可以实现$O(1)$区间修改，$O(n)$单点查询(这里可以用数据结构维护)
差分序列性质：
1、差分序列前缀和$S_i$是原序列的数$A_i$
2、原数组所有数等于 0 等价于 差分序列为 0
3、$f[a]+1, f[b+1]-1$等同于在原数组区间修改
1、修改区间操作
BZOJ 1651
2、差分序列性质解题
积木大赛：区间减为0最小修改次数。
差分序列正负数配对消去(相当于$a[l]+1, a[r]-1$)，剩余正数与$a[0]$配对)
原数组所有数等于 0 等价于 差分序列为 0
IncDec Sequence (Bzoj 3043)：区间 增/减 后所有数相等的最小修改次数，以及最后高度的可能情况。
原数组所有数等于 0 等价于 差分序列为 0 ，这里只要相同则对$a[1]$无要求
差分序列正负数配对消去(相当于$a[l]+1, a[r]-1$)，剩余正数/负数与$a[1], a[n+1]$配对)
求可能情况则可以认为剩余正数/负数可以与$a[1], a[n+1]$配对，则有$|正数-负数|$高度种情况
环形积木大赛：
找到一个最小值断环成链即可用上面的差分方法
3、差分与前缀和 (by ruanxingzhi 差分与前缀和)
差分降次，前缀和升次，对于前面加速其实就是将数组降次后，再升次得到原数组
区间$[l,r]$加一次函数(等差数列)：
将数组差分后，在$a[l]+=首项$，后面$a[l+1,r]+=d$，$a[r+1]-=首项+(r-l)d$
显然这个可以用线段树维护。
区间$[l,r]$加二次函数：
考虑多阶差分。
将二次函数差分后得到一次函数。
一次函数差分后得到常值函数。
然后用线段树维护即可。
找规律：
若觉得答案为关于$n$的多项式，那么可以取其前几项然后不断差分，如果发现$k$阶差分所有项都是同一常数，那么这个多项式就是$k$次的。
手动高斯消元找到$f(n)$，大概是用一阶差分来高斯消元
矩阵旋转$45^{\circ}$
输入的时候按正常顺序输入，但存储时要存到$(i+j-1,n-i+j)$，这个公式退推一下就能出来
常见题型
1、差分序列(一维前缀和)
Q：区间修改单点查询。
解：见解析
例题：BZOJ 1651
2、树上差分序列(树上前缀和)
Q：在树上修改某一条路径的值。
解：我们让$f[u]+1, f[v]+1, f[LCA(u, v)]-2$，这样做以后在树上的前缀和$\sum_{k\in son(i)}{f[k]}$就是节点$i$的值
例题：NOIP2015 D2 T3
3、差分序列约束区间
Q：某区间必须小于某个值。
解：对于每个约束$a,b$，我们使$f[a+1]–,f[b]++$，这样可以保证$a,b$之间的元素严格小于$a,b$
例题：BZOJ 1635
4、二维前缀和
Q：查询某个矩阵的子矩阵的和
解：容斥原理，和二维树状数组的求法差不多
例题：NOIP2016 D2 T1
5、旋转矩阵后前缀和维护
Q：在一个矩阵中找出一个分值最大的斜矩阵
解：把矩阵旋转$45^{\circ}$，然后就可以在水平求前缀和了
例题：计蒜客NOIP模拟赛-1 Day1 T1
Hdu 1561(树形背包DP)
Hdu 1561
经典树形依赖背包问题。
因为可能出现森林，所有要建立一个虚结点0，将森林中所有树的根节点作为结点0的儿子
$f[i][j]$表示以i为根选j个课程
$f[u][j] = max(f[u][j], f[u][j-k]+f[v][k])$ v是u的儿子