整体二分

发表于 2022-10-26 分类于信奥，算法阅读次数：

对于一个询问，我们往往可以通过二分答案的方法求出解：在答案的可能范围中选择一个值 $mid$ ，然后判断正确答案是比 $mid$ 大还是小，以此来缩小可能的值域范围。如果判断的过程可以 $O(n)$ 解决，那么往往可以在 $n \log w$ 的复杂度之后解出答案。

比如求区间第 $k$ 小 。我们可以先假设一个 $mid$ 是第 $k$ 小，然后统计实际上比 $mid$ 小的数有几个，以此来确定 $mid$ 真正的排名是多少。如果比 $k$ 大，说明真正的第 $k$ 小小于 $mid$ ，反之则大于 $mid$ 。以此可以完成二分。

但是当我们要多次求不同的区间第 $k$ 小时，如果我们对每一个询问都进行一次二分操作，复杂度将会难以接受。怎么办呢？

我们考虑延续二分的思路。把所有的询问都读进来之后，我们不妨假设每一个询问的答案都是 $mid$ ，然后判断所有询问中，有哪些询问的真实答案比 $mid$ 大，有哪些询问的真实答案比 $mid$ 小，然后分别递归求解。

但这么做有两个问题：

如何判断？按照上面的方法，对于每一个询问都要花 $O(n)$ 的时间去判断，这显然难以接受。
二分能有 $\log$ 的复杂度，是因为在 $[1, mid],(mid,w]$ 两个值域中只有一个会进入下一轮，而现在我们对两个值域都要递归求解，时间复杂度如何保证？

对于第1个问题，我们可以先对数据进行预处理。我们可以用树状数组维护出区间 $[1,i]$ 中有几个数小于 $mid$（就是小于 $mid$ 的看成1，大于 $mid$ 的看成0，然后用树状数组维护前缀和），之后在判断，只要拿 $[1,r]$ 的值减去 $[1,l)$ 的值就好了。这样就把 $O(n)$ 判断降低到了 $O(\log n)$ 。不过预处理需要 $O(n \log n)$ 的时间。

对于第2个问题，我们使用一些技巧来解决：在1中的树状数组中，我们不再把所有的数都加入树状数组，而是只把当前答案值域的数放进树状数组。那么对于每个数，它最多会进入 $w $ 次递归，每一次递归都会进一次树状数组，总共的树状数组操作就有 $O(n \log w)$ 次。同样的道理，对于每一个询问，它最多只会进入 $\log w$ 次递归，每一次递归都会查询一次树状数组，总共的查询数也是 $O(n \log w)$ 。由于树状数组单次操作复杂度为 $O(\log n)$ ，总时间复杂度就是 $O(n \log n \log w)$ 。我们还可以对值域进行离散化，将 $w$ 缩小为 $n$ 。复杂度就变成了 $n \log^2 n$ 。

不过，由于我们只是把值域在 $[l,r]$ 中的数放进了树状数组，故在递归进入 $(mid,r]$ 时，需要把所有待递归的询问的 $k$ 减掉 $[l,mid]$ 的贡献。因为接下来的递归， $[l,mid]$ 中的数将不再进入树状数组。

代码如下（引自 OI-wiki）：

code

struct Num {
	int p, x;
};	// 位于数列中第 p 项的数的值为 x

struct Query {
	int l, r, k, id;
};	// 一个编号为 id, 询问 [l,r] 中第 k 小数的询问

int ans[N];
void add(int p, int x);	// 树状数组, 在 p 位置加上 x
int query(int p);		// 树状数组, 求 [1,p] 的和
void clear();			// 树状数组, 清空

void solve(int l, int r, vector<Num> a, vector<Query> q)
// a中为给定数列中值在值域区间 [l,r] 中的数
{
	int m = (l + r) / 2;
	if (l == r) {
		for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
		return;
	}
	vector<Num> a1, a2;
	vector<Query> q1, q2;
	for (unsigned i = 0; i < a.size(); i++)
		if (a[i].x <= m)
			a1.push_back(a[i]), add(a[i].p, 1);
		else
			a2.push_back(a[i]);
	for (unsigned i = 0; i < q.size(); i++) {
		int t = query(q[i].r) - query(q[i].l - 1);
		if (q[i].k <= t)
			q1.push_back(q[i]);
		else
			q[i].k -= t, q2.push_back(q[i]);
	}
	clear();
	solve(l, m, a1, q1), solve(m + 1, r, a2, q2);
	return;
}

根据上面的分析，其实我们已经可以发现保持整体二分的复杂度的要点了：对于序列中的每一个元素，我们应该做到只对当前值域中的那些元素进行数据结构操作。这样，如果一次数据结构操作的时间为 $T$ ，总时间复杂度就是 $O(Tn \log n)$ 。

最后就是如何进行修改的问题。其实非常简单，把它和询问一起作为操作参与递归。只不过在递归过程中要注意以下三点：

注意保持时间顺序。始终保证修改和查询的相对位置不变。
修改后的元素如果超过了值域之外，不应该写入数据结构中。
递归的结尾别忘了把修改的内容还原。

带修区间第 $k$ 小参考代码（引自 OI-wiki）：

code

struct Opt {
	int x, y, k, type, id;
	// 对于询问, type = 1, x, y 表示区间左右边界, k 表示询问第 k 小
	// 对于修改, type = 0, x 表示修改位置, y 表示修改后的值,
	// k 表示当前操作是插入(1)还是擦除(-1), 更新树状数组时使用.
	// id 记录每个操作原先的编号, 因二分过程中操作顺序会被打散
};

Opt q[N], q1[N], q2[N];
// q 为所有操作,
// 二分过程中, 分到左边的操作存到 q1 中, 分到右边的操作存到 q2 中.
int ans[N];
void add(int p, int x);
int query(int p);	// 树状数组函数, 含义见题3

void solve(int l, int r, int L, int R)
// 当前的值域范围为 [l,r], 处理的操作的区间为 [L,R]
{
	if (l > r || L > R) return;
	int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
	// cnt1, cnt2 分别为分到左边, 分到右边的操作数
	if (l == r) {
		for (int i = L; i <= R; i++)
			if (q[i].type == 1) ans[q[i].id] = l;
		return;
	}
	for (int i = L; i <= R; i++)
		if (q[i].type == 1) {	// 是询问: 进行分类
			int t = query(q[i].y) - query(q[i].x - 1);
			if (q[i].k <= t)
				q1[++cnt1] = q[i];
			else
				q[i].k -= t, q2[++cnt2] = q[i];
		} else
			// 是修改: 更新树状数组 & 分类
			if (q[i].y <= m)
				add(q[i].x, q[i].k), q1[++cnt1] = q[i];
			else
				q2[++cnt2] = q[i];
	for (int i = 1; i <= cnt1; i++)
		if (q1[i].type == 0) add(q1[i].x, -q1[i].k);	// 清空树状数组
	for (int i = 1; i <= cnt1; i++) q[L + i - 1] = q1[i];
	for (int i = 1; i <= cnt2; i++)
		q[L + cnt1 + i - 1] = q2[i];	// 将临时数组中的元素合并回原数组
	solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
	return;
}

最后上例题和代码：

[POI2011 R3 Day2] 流星 Meteors

AC 代码：

code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;

struct query {
	int id;
	long long w;
	vector<int> p;
};

struct edit {
	int l, r;
	long long w;
};

int n, m, k;
int ans[maxn];
long long tree[maxn];
query a[maxn], a1[maxn], a2[maxn];
edit b[maxn];

void update(int pos, long long x) {
	while (pos <= m) {
		tree[pos] += x;
		pos += pos & (-pos);
	}
}

long long ask(int pos) {
	long long res = 0;
	while (pos >= 1) {
		res += tree[pos];
		pos -= pos & (-pos);
	}
	return res;
}

void solve(int l, int r, int ql, int qr) {
	// printf("%d %d %d %d\n", l, r, ql, qr);
	if (l > r || ql > qr) return;
	if (l == r) {
		for (int i = ql; i <= qr; i++) ans[a[i].id] = l;
		return;
	}
	int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
	for (int i = l; i <= mid; i++) {
		if (b[i].l <= b[i].r) update(b[i].l, b[i].w), update(b[i].r + 1, -b[i].w);
		else update(1, b[i].w), update(b[i].r + 1, -b[i].w), update(b[i].l, b[i].w), update(m + 1, -b[i].w);
	}
	// if (l == 1 && r == k + 1) for (int i = 1; i <= m; i++) printf("%lld%c", ask(i), " \n"[i == m]);
	for (int i = ql; i <= qr; i++) {
		long long sum = 0;
		for (int p : a[i].p) {
			sum += ask(p);
			if (sum >= a[i].w) break;
		}
		if (sum >= a[i].w) a1[++cnt1] = a[i];
		else a[i].w -= sum, a2[++cnt2] = a[i];
	}
	for (int i = l; i <= mid; i++) {
		if (b[i].l <= b[i].r) update(b[i].l, -b[i].w), update(b[i].r + 1, b[i].w);
		else update(1, -b[i].w), update(b[i].r + 1, b[i].w), update(b[i].l, -b[i].w), update(m + 1, b[i].w);
	}
	for (int i = 1; i <= cnt1; i++) a[ql + i - 1] = a1[i];
	for (int i = 1; i <= cnt2; i++) a[ql + cnt1 + i - 1] = a2[i];
	solve(l, mid, ql, ql + cnt1 - 1), solve(mid + 1, r, ql + cnt1, qr);
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		static int id;
		scanf("%d", &id);
		a[id].p.emplace_back(i);
	}
	for (int i = 1; i <= n; i++) {
		a[i].id = i;
		scanf("%lld", &a[i].w);
	}
	scanf("%d", &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d %d %lld", &b[i].l, &b[i].r, &b[i].w);
	}
	b[k + 1].l = 1, b[k + 1].r = m, b[k + 1].w = (long long)(1e9 + 5);
	solve(1, k + 1, 1, n);
	for (int i = 1; i <= n; i++) {
		if (ans[i] == k + 1) printf("NIE\n");
		else printf("%d\n", ans[i]);
	}
	return 0;
}