Adva::0x06

2024-02-10 23:41:16

Adva::0x06 倍增

Part 1. 引言

倍增，字面意思为“成倍增长”。指在进行递推时，只将状态空间中形如 \(2^k\) 的值作为代表进行递推，其他位置的值可以通过记录的值计算出来，降低了时间复杂度。

Part 2. 倍增初步

给定一个长度为 \(n\) 的数列 \(a\)，然后进行若干次询问，每次给定一个整数 \(T\)，请求出最大的 \(k\) 使得 \(\sum_{i=1}^{k}a_i \leq T\)。你的算法必须是在线的，另外，假设 \(0 \leq T \leq \sum a\)。

首先 \(\operatorname{O}(n)\) 预处理出前缀和数组 \(s\)。

我们令 \(p = 1, k = 0, sum = 0\)。对于每一次操作，比较 \(k\) 之后的 \(p\) 个数的和加上已有的 \(sum\) 与 \(T\) 的大小关系：

\(sum + s_{k + p} - s_k \leq T\)，令 \(sum \leftarrow sum+ s_{k + p} - s_k, k \leftarrow k + p, p \leftarrow p\times 2\)。
否则，令 \(p \leftarrow p \div 2\)。

循环直到 \(p = 0\)，\(k\) 就是答案。时间复杂度 \(\operatorname{O}(\log_2k)\)。

Genius ACM

给定整数 \(m\)，对于任意一个整数集合 \(s\)，定义校验值：

从集合中选出 \(m\) 对数，使得“每对数差的平方”之和最大，最大值即为校验值。

给定数列 \(a_1 \sim a_n\) 以及整数 \(T\)，我们要把 \(a\) 分成若干段，使得每一段校验值不超过 \(T\)。求最少分成几段。

由数学知识，应该取 \(s\) 中最大与最小，次大与次小 \(\dots\) 组成 \(m\) 对。

问题：确定左端点 \(L\)，求一个最大的右端点 \(R\)，使得 \(a_L \sim a_R\) 的校验值不超过 \(T\)。

初始化 \(p = 1, R = L\)。求出 \(L \sim R + p\) 的校验值 \(x\)，若 \(x \leq T\)，\(R \leftarrow R + p, p \leftarrow p \times 2\)；否则 \(p \leftarrow p \div 2\)。时间复杂度 \(\operatorname{O}(n\log_2^2n)\)。

* 更快的方法

我们使用类似于归并排序的方法，每次只对新增部分排序，然后合并。时间复杂度 \(\operatorname{O}(n \log_2 n)\)。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <climits>
using namespace std;
const int kMaxN = 1e6 + 5;
int K, n, m, a[kMaxN], b[kMaxN], tmp[kMaxN];
long long t;
long long calc(int l, int mid, int r) {
	for (int i = mid; i < r; ++i) {
		b[i] = a[i];
	}
	sort(b + mid, b + r);
	int i = l, j = mid;
	for (int k = l; k < r; ++k) {
		if (j >= r || i < mid && b[i] <= b[j]) tmp[k] = b[i++];
		else tmp[k] = b[j++];
	}
	long long sum = 0;
	for (int i = l, j = r; i < (m + l) && i < j; ++i, --j) {
		sum += 1ll * (tmp[j - 1] - tmp[i]) * (tmp[j - 1] - tmp[i]);
	}
	return sum;
}
int main() {
	cin >> K;
	while (K--) {
		cin >> n >> m >> t;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
		}
		int st = 1, ed = 1, ans = 0;
		while (ed <= n) {
			int p = 1;
			while (p) {
				long long val = calc(st, ed, ed + p);
				if (ed + p <= n + 1 && val <= t) {
					ed += p, p *= 2;
					if (ed > n) break;
					for (int i = st; i < ed; ++i) {
						b[i] = tmp[i];
					}
				} else {
					p /= 2;
				}
			}
			++ans, st = ed;
		}
		cout << ans << endl;
	}
	return 0;
}

Part 3. ST 表

在 RMQ 问题中，著名的 ST 表就是倍增的产物。ST 表能在 \(\operatorname{O}(n \log_2n)\) 的时间复杂度预处理后，以 \(\operatorname{O}(1)\) 的时间回答区间最大值。

我们设 \(F(i, j)\) 为 \([i, i + 2 ^ j - 1]\) 内的最大值。

显然，\(F(i, 0) = a_i, F(i, j) = \max(F(i, j - 1), F(i + 2 ^ {j - 1}, j - 1))\)。

const int kMaxN = 1e5 + 5;
int n, a[kMaxN], f[kMaxN][30];
void preST() {
	for (int i = 1; i <= n; ++i) {
		f[i][0] = a[i];
	}
	int t = log2(n);
	for (int j = 1; j <= t; ++j) {
		for (int i = 1; i <= (n - (1 << j)) + 1; ++i) {
			f[i][j] = max(f[i][j], f[i + (1 << j - 1)][j - 1]);
		}
	}
}
int queryST(int l, int r) {
	int k = log2(r - l + 1);
	return max(f[l][k], f[r - (1 << k) + 1][k]);
}

码农公寓