BZOJ4358. permu
Statement
给出一个长度为 nnn 的排列 PPP，以及 mmm 个询问。每次询问某个区间 [l,r][l,r][l,r] 中，最长的值域连续段长度。
数据范围：n,m≤5×104n,m\le5\times10^4n,m≤5×104。
Solution
考虑莫队区间如何扩展。
维护每个元素向上延伸和向下延伸的最大距离。加入新元素 xxx 时，会合并 x−1x-1x−1 所在集合和 x+1x+1x+1 所在集合；但是对答案有贡献的只可能是合并后集合的端点。所以可以只更新这两个元素，也方便了撤销。
时间复杂度 O(nm)O(n\sqrt m)O(nm)。
Code
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>const int N = 5e4 + 3, SN = 293;int n, q, a[N], B, T, ans[N];#define ...
P4689. [Ynoi2016] 这是我自己的发明
Statement
给一个树，nnn 个点，有点权，初始根是 111。mmm 个操作，种类如下：
1 x\texttt{1}~x1 x：将树根换为 xxx。
2 x y\texttt{2}~x~y2 x y：给出两个点 x,yx,yx,y，从 xxx 的子树中选每一个点，yyy 的子树中选每一个点，求点权相等的情况数。
数据范围：1≤n≤1051\le n\le10^51≤n≤105，1≤m≤5×1051\le m\le5\times10^51≤m≤5×105 , 1≤ai≤1091\le a_i\le10^91≤ai≤109。
Solution
根号做法，按颜色的出现次数根号分治。
对于出现次数 >n>\sqrt n>n 的颜色
最多 n\sqrt nn 种颜色，那么对于每种颜色 O(n)O(n)O(n) 地统计 xxx 子树内出现次数 cntx\text{cnt}_xcntx。询问 x,yx,yx,y 的答案就是 cntx⋅cnty\text{cnt}_x\cdot\text{cnt}_ycntx⋅cnty。
当然由于换根，可能 xxx 的 ...
排序、数学杂项与博弈论 学习笔记
排序算法
平均
最好
最坏
辅助空间
稳定性
概述
冒泡排序
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(n2)O(n^2)O(n2)
T(1)T(1)T(1)
稳定
扫一遍移动当前已知最大元素与下一元素交换
简单选择排序
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
T(1)T(1)T(1)
不稳定
第 iii 次选择剩余最大值与第 iii 个元素换位
插入排序
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(n2)O(n^2)O(n2)
T(1)T(1)T(1)
稳定
拿出当前元素，挨个尝试往前放置找到合适位置
希尔排序
O(n)O(n)O(n)
T(1)T(1)T(1)
不稳定
步长从 n2\frac{n}{2}2n 到 111 进行直接插入排序
归并排序
O(nlogn)O(n\log n)O(nlogn)
O(nlogn)O(n\log n)O(nlogn)
O(nlogn)O(n\log n)O(nlogn)
T(n)T(n)T(n)
稳 ...
图论 学习笔记
并查集
设 mmm 为合并次数，nnn 为点数，则：
朴素：O(mn)O(mn)O(mn)
按 size / height 合并：O(mlogn)O(m\log n)O(mlogn)
路径压缩：O(mlogn)O(m\log n)O(mlogn)
按 size / height 合并 + 路径压缩：近似 O(m)O(m)O(m)
最小生成树 MST
Boruvka
每一轮，对每个联通块选择一条到其他联通块的一条最短路径。
时间复杂度 O((n+m)logn)O((n+m)\log n)O((n+m)logn)。
最近公共祖先 LCA
倍增 & 树剖
时间复杂度 O((n+q)logn)O((n+q)\log n)O((n+q)logn)。
Tarjan
只能离线。
时间复杂度 O(n+q)O(n+q)O(n+q)。
欧拉序 + ST 表
时间复杂度 O(nlogn+q)O(n\log n+q)O(nlogn+q)，但是有 222 倍常数，实际也不会很快。
DFS 序 + ST 表
讨论一组询问 u,vu,vu,v 和他们的 lca\text{l ...
数据结构 学习笔记
树状数组
一维：区间修改 区间查询
设原序列 {ai}\{a_i\}{ai} 的差分序列为 {di}\{d_i\}{di}（即 di={ai−ai−1i≥2a1i=1d_i=\begin{cases}a_i-a_{i-1}&i\ge2\\a_1&i=1\end{cases}di={ai−ai−1a1i≥2i=1）。
∑i=1nai=∑i=1n∑j=1idj=∑i=1ndi×(n−i+1)=(n+1)×∑i=1ndi −∑i=1ni×di\begin{aligned}
\sum\limits_{i=1}^na_i&=\sum_{i=1}^n\sum_{j=1}^id_j\\
&=\sum_{i=1}^nd_i\times(n-i+1)\\
&=(n+1)\times\sum_{i=1}^nd_i~-\sum_{i=1}^ni\times d_i
\end{aligned}
i=1∑nai=i=1∑nj=1∑idj=i=1∑ndi×(n−i+1)=(n+1)×i=1∑ndi −i=1∑ni×di
因此，除 ...
数论 学习笔记
约数个数
@Ubospica 对于约数个数上界的估计
d(n)≤nclnlnnd(n)\le n^{\frac c{\ln\ln n}}d(n)≤nlnlnnc，其中 c≈1.066c\approx1.066c≈1.066。当 n>5000n>5000n>5000 约有 d(n)<nd(n)<\sqrt nd(n)<n。
质数判定
关于质数判定的一些资料：
@wangrx 一定范围内的确定性判素
知乎 如何编程判断一个数是否是质数？
费马素性检验 / 费马测试
费马小定理的逆否命题：若存在 1≤a<p1\le a<p1≤a<p，使得 ap−1≢1(modp)a^{p-1}\not\equiv1\pmod pap−1≡1(modp)，则 ppp 一定不是素数。
多次选取质数 a∈[1,p)a\in[1,p)a∈[1,p)，使用快速幂检查 pa−1 mod pp^{a-1}\bmod ppa−1modp 是否为 111：若存在快速幂的结果不是 111，则 ppp 一定不是素数；否则 ppp 大概率是素数。
遗憾的 ...
动态规划 学习笔记
决策单调性优化 DP
2D/1D DP 的决策单调性优化
2D/1D DP 指状态有两维、转移有一维的 DP。
定理：对于形如 f(i,j)=mink=ij−1{f(i,k)+f(k+1,j)}+w(i,j)f(i,j)=\min\limits_{k=i}^{j-1}\{f(i,k)+f(k+1,j)\}+w(i,j)f(i,j)=k=iminj−1{f(i,k)+f(k+1,j)}+w(i,j) 的 DP 式，若：
区间包含单调性：对于 i≤i′<j≤j′i\le i'<j\le j'i≤i′<j≤j′，满足 w(i′,j)≤w(i,j′)w(i',j)\le w(i,j')w(i′,j)≤w(i,j′)。（（互相包含的两个区间）大区间大于小区间）
四边形不等式：对于 i≤i′<j≤j′i\le i'<j\le j'i≤i′<j≤j′，满足 w(i,j)+w(i′,j′)≤w(i′,j)+w(i,j′)w(i,j)+w(i',j')\le w(i&#x ...
网络流 学习笔记
有源汇最大流算法家族
EK
BFS 寻找最短增广路。
时间复杂度 O(n2m2)O(n^2m^2)O(n2m2)。
Dinic
Dinic 是 EK 的优化。
BFS 得到距离标号，用 DFS 同时增广相同长度的增广路。
反向标号：从 TTT 开始 BFS 重算距离标号，从 SSS 开始 DFS。
时间复杂度 O(n2m)O(n^2m)O(n2m)。
在边权全为 111 的图上跑最大流的时间复杂度为 O(min{n23m,m32})O(\min\{n^{\frac23}m,m^{\frac32}\})O(min{n32m,m23})。
ISAP
ISAP 可视为 Dinic 的优化。
在 DFS 之后直接 distu=min{distv}+1\text{dist}_u=\min\{\text{dist}_v\}+1distu=min{distv}+1。
再加一个 gapx\text{gap}_xgapx 表示 ∑[distu=x]\sum[\text{dist}_u=x]∑[distu=x]。若 gapx\text{gap}_xgapx 断层，则不可能再 ...
语言和语法 学习笔记
注意事项
负数 >> 1 和 / 2 不同，右移是向下取整，除法是向零取整。e.g. (-5) >> 1 = -3, (-5) / 2 = -2。
pb_ds 库
所有数据结构都在 __gnu_pbds 命名空间。
哈希表
头文件：
12#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp>
定义：
拉链法处理冲突 cc_hash_table<key_type, value_type> hash_name
探测法处理冲突 gp_hash_table<key_type, value_type> hash_name（较快）
成员函数：
hash_name[key] 重载中括号运算符访问 value 值的引用，若 value 值不存在则新开辟空间。
iterator find(key_type num) 返回按 key 查找到的 value 值的迭代器，未找到返回 hash_name.end()。
平 ...