基本技巧——倍增
概念
倍增法，顾名思义就是翻倍、成倍增长。
它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
常常在递推中状态空间的第二维记录二的整数次幂的值，通过这些值拼凑出答案。
通过任意整数都可以表示为若干个二的次幂项的和（二进制），以此计算。
ST 表概述
ST 表可以做到 \(\mathcal O(n\log n)\) 预处理，\(\mathcal O(1)\) 求出序列区间最大值。
按照最基础的思想，设 \(f(i,j)\) 表示区间 \([i,j]\) 的最大值，考虑上述倍增思想。
重新设计状态，
用 \(f(i,j)\) 表示区间 \([i,i+2^j-1]\) 的最大值，也就是从 \(i\) 开始的 \(2^j\) 个数。
考虑这样子递推的边界，
- 显然 \(f(i,0)=a_i\)。
- 显然 \(f(i,j)=\max\{f(i,j-1),f(i+2^{j-1},j-1)\}\)。
这么折半的预处理，可以做到 \(\mathcal O(n\log n)\) 的复杂度。
考虑查询，如果我们按照朴素的思想去处理的话，也是 \(\mathcal O(n\log n)\) 的，但是
有一个很简单的性质，\(\max\{x,x\}=x\)，这意味着我们可以重复计算一个区间的最大值。
于是，我们可以把区间中一部分重复的区间跳过，直接去计算：
能覆盖整个区间的两个左右端点上的整个区间，就可以做到 \(\mathcal O(1)\)。
除 RMQ 以外，还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」等。
ST 表能较好的维护「可重复贡献」的区间信息（同时也应满足结合律），时间复杂度较低。
蓝书的代码：
void init() {
for (int i = 1; i <= n; ++i) f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; ++j)
for (int i = 1; i <= n - (1 << j) + 1; ++i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
倍增 LCA 概述
朴素思想，从两个点一步一步往上跳，跳到同一高度后再一起跳。
考虑倍增，记 \(f(u,x)\) 表示 \(u\) 向上 \(2^x\) 步的节点是哪个，直到跳到一起。
然后就可以 \(\mathcal O(n\log n)\) 预处理，\(\mathcal O(\log n)\) 查询了。
这个思想是先尽可能的多跳，如果跳多了就返回，再跳更小的步数。
在 LCA 的同时，还可以同步记录一些其他的东西。
比如下面的代码记录了子树中的最大节点编号（P10113 [GESP202312 八级] 大量的工作沟通），
int n, f[N];
int dep[N], mxj[N];
int lt[N][35];
void init(int u, int fa) {
dep[u] = dep[fa] + 1, mxj[u] = max(u, mxj[fa]);
for (int k = 0; k <= 30; ++k) lt[u][k + 1] = lt[lt[u][k]][k];
for (int v : g[u]) if (v != fa) lt[v][0] = u, init(v, u);
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int k = 30; ~k; --k) if (dep[lt[x][k]] >= dep[y]) x = lt[x][k];
if (x == y) return x;
for (int k = 30; ~k; --k) if (lt[x][k] != lt[y][k]) x = lt[x][k], y = lt[y][k];
return lt[x][0];
}
例题
给定一个长度为 \(N\) 的序列 \(A\)，对于询问的整数 \(T\)，求出
最大的整数 \(k\)，使得
找到在线算法。
首先，可以求出 \(A\) 的前缀和 \(S\)，然后就可以简单的二分了。
但是，如果答案 \(k\) 非常小，二分的算法就会很不优，甚至不如顺序枚举。
考虑倍增算法（下面是蓝书上的），
- 另 \(p=1,k=0,r=0\)。
- 如果 \(r+S_{k+p}-S_k\le T\)，就另 \(r\gets r+S_{k+p}-S_k\)；\(k\gets k+p\)；\(p\gets2p\)。
- 否则，另 \(p\gets p/2\)。
- 重复上一步，直至 \(p=0\)，此时 \(k\) 即为答案。
这个思想与倍增 LCA 的思想不同，是先跳，如果能跳就增大下一次跳的，跳不了就减小。
天才 ACM
题目：https://www.acwing.com/problem/content/111/。
考虑到，一个集合的校验值，一定是最大对最小，次大对次小。
随便举个例子，若 \(a<b<c<d\)，则
\[(d-a)^2+(c-b)^2=a^2+b^2+c^2+d^2-2(ad+bc)\\ (b-a)^2+(d-c)^2=a^2+b^2+c^2+d^2-2(ab+cd) \]上式减下式，
\[ab+cd-ad-bc=a(b-d)+c(d-b)=(c-a)(d-b) \]乘积为正数，即上式大于下式，即贪心可行且正确。
回归问题，容易总结出来：
对于左端点，找到最右的点，使得校验值小于限制的值。
考虑到计算校验值是 \(\mathcal O(n\log n)\) 的，因此这里需要优化。
注意到和上面的题形式类似，可以倍增处理，
因为倍增的复杂度是 \(\mathcal O(\log n)\) 的，因此整体复杂度为，
\[\mathcal O(n\log^2n) \]不太可过，但是注意到每次右端点增加的时候，可以类似归并排序的合并。
于是复杂度降为，
\[\mathcal O(n\log n) \]但是细节很多，本人采用了闭区间的写法，
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
constexpr int N = 1e6 + 10;
int n, m;
ll t;
int a[N], b[N];
int q[N];
bool getchk(int l, int r, int ad) {
int lt = r - ad + 1;
for (int i = lt; i <= r; ++i) b[i] = a[i];
sort(b + lt, b + r + 1);
int tot = 0, u = l, v = lt;
while (u < lt && v <= r) {
if (b[u] < b[v]) q[tot++] = b[u++];
else q[tot++] = b[v++];
}
while (u < lt) q[tot++] = b[u++];
while (v <= r) q[tot++] = b[v++];
ll chk = 0;
for (int i = 0, j = tot - 1, k = 1; k <= m && i < j; ++i, --j, ++k)
chk += 1ll * (q[j] - q[i]) * (q[j] - q[i]);
return chk <= t;
}
int getpos(int l) {
int p = 1, k = l - 1;
while (p) {
if (k + p <= n && getchk(l, k + p, p)) {
k = k + p, p <<= 1;
for (int i = l; i <= k + p; ++i) b[i] = q[i - l];
} else p >>= 1;
} return k;
}
void solev() {
cin >> n >> m >> t;
for (int i = 1; i <= n; ++i) cin >> a[i];
int l = 1, ans = 0;
while (l <= n) l = getpos(l) + 1, ++ans;
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T; cin >> T;
while (T--) solev();
return 0;
}