P4587 [FJOI2016] 神秘数题解

提供一个可能不太一样的思考角度。

首先考虑什么样的数可以对答案产生贡献。

一些经典的“如何用少量的数的和表示值域内的所有数”类型问题或许能给出一些启发。这里直接给出结论：将集合内的数从小到大排序，并设

\text{pre}_i

为集合内前

i

小的数的和。此时，对于正整数

k

，若存在

i

满足

\text{pre}_i < k

且

a_{i + 1} > k

，则

k

可以产生贡献。证明考虑前文提到的问题即可。

进一步地，我们可以得出一个较为暴力的多项式做法：对于一次询问，将

[l, r]

内的数排序，并顺序扫描，对于下标

i

（这里我们可以认为是从

1

开始），若

\text{pre}_i + 1 < a_{i + 1}

，则

\text{ans} = \text{pre}_i + 1

。该做法的复杂度为

O(qn \log n)

，不能通过。

接下来尝试如何进一步限制可能产生贡献的位置。一个经典的角度是：若下标

i

可能产生贡献，则

a_i

与

a_{i + 1}

的值（或者说它们之间的差距）是指数级增长的。用心感受后，你可能会发现数值增长的速率约为每次

\times 2

。具体的增长速率下限可能并不容易求出，不过没关系，我们可以从下面的角度思考：

考虑在值域上进行类似“二分”的操作来求答案。设当前考虑的区间为

[l, r]

，则我们定义

\text{sum}

为

[l, \text{mid}]

内所有元素的和，

\text{mn}

为

[\text{mid} + 1, +\infty)

内的元素的最小值。

接下来比较

\text{sum}

与

\text{mn}

的大小关系：

若 $\text{sum} + 1 < \text{mn}$ ，则用 $\text{sum} + 1$ 更新答案。此时因为更大的数必然不可能对答案产生贡献，故我们只需递归 $[l, \text{mid}]$ 即可。
否则，考虑 $\text{sum} + \text{mn} \ge 2 \times \text{mid} - 1 > r$ ，我们再次得出了 $[\text{mid} + 1, r]$ 内的数不可能产生贡献的结论。因此我们仍只需递归 $[l, \text{mid}]$ 。

我们显然可以用线段树维护上文的操作过程。这题有多组询问，因此使用可持久化线段树即可。

该做法的时间复杂度为

O(n \log V + q \log^2 V)

，空间复杂度为

O(n \log V)

，并且不需要什么复杂的关于

\log

底数的说明。

code

CPP

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

using namespace std;

constexpr int N = 1e5 + 5, INF = 2e9;

struct Segment_Tree {
	int L, R, cnt;
	int rt[N];
	struct Node {
		int l, r, sum;
	} a[N << 5];
	
	void push_up(int p) {
		a[p].sum = a[a[p].l].sum + a[a[p].r].sum;
	}
	
	void init(int n) {
		L = 1, R = n;
		rt[0] = cnt = 1;
	}
	
	void update(int &p, int q, int l, int r, int k) {
		a[p = ++cnt] = a[q];
		if (l == r) {
			a[p].sum += k;
			return;
		}
		if (k <= mid) {
			update(a[p].l, a[q].l, l, mid, k);
		} else {
			update(a[p].r, a[q].r, mid + 1, r, k);
		}
		push_up(p);
	}
	
	void update(int id, int k) {
		update(rt[id], rt[id - 1], L, R, k);
	}
	
	int qry(int p, int q, int l, int r) {
		if (a[q].sum - a[p].sum == 0) {
			return INF;
		}
		if (l == r) {
			return l;
		}
		if (a[a[q].l].sum - a[a[p].l].sum > 0) {
			return qry(a[p].l, a[q].l, l, mid);
		} else {
			return qry(a[p].r, a[q].r, mid + 1, r);
		}
	}
	
	int res, mn;
	void query(int p, int q, int l, int r) {
		if (l == r) return;
		int sum = a[a[q].l].sum - a[a[p].l].sum;
		mn = min(mn, qry(a[p].r, a[q].r, mid + 1, r));
		if (sum + 1 < mn) {
			res = sum + 1;
		}
		query(a[p].l, a[q].l, l, mid);
	}
	
	int query(int l, int r) {
		res = a[rt[r]].sum - a[rt[l - 1]].sum + 1, mn = 1e9;
		query(rt[l - 1], rt[r], L, R);
		return res;
	}
} ST;

int n, q;
int a[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	ST.init(1e9);
	for (int i = 1; i <= n; ++i) {
		ST.update(i, a[i]);
	}
	
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		cout << ST.query(l, r) << '\n';
	}
	
	return 0;
}

P4587 [FJOI2016] 神秘数题解

文章操作

相关推荐

评论

P4587 [FJOI2016] 神秘数题解