当前位置：首页 > article >正文

【Codeforces】CF 1997 E

article 2024/10/8 13:23:51

Level Up

#数据结构 #二分 #树状数组

题目描述

Monocarp is playing a computer game. He starts the game being level $1$ . He is about to fight $n$ monsters, in order from $1$ to $n$ . The level of the $i$ -th monster is $a_i$ .

For each monster in the given order, Monocarp’s encounter goes as follows:

if Monocarp’s level is strictly higher than the monster’s level, the monster flees (runs away);
otherwise, Monocarp fights the monster.

After every $k$ -th fight with a monster (fleeing monsters do not count), Monocarp’s level increases by $1$ . So, his level becomes $2$ after $k$ monsters he fights, $3$ after $2 k$ monsters, $4$ after $3 k$ monsters, and so on.

You need to process $q$ queries of the following form:

$i x$ : will Monocarp fight the $i$ -th monster (or will this monster flee) if the parameter $k$ is equal to $x$ ?

输入格式

The first line contains two integers $n$ and $q$ ( $\le n, q \le 2 \cdot 10^5$ ) — the number of monsters and the number of queries. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $\le a_i \le 2 \cdot 10^5$ ) — the levels of the monsters. In the $j$ -th of the following $q$ lines, two integers $i$ and $x$ ( $\le i, x \le n$ ) — the index of the monster and the number of fights required for a level up in the $j$ -th query.

输出格式

For each query, output “YES”, if Monocarp will fight the $i$ -th monster in this query, and “NO”, if the $i$ -th monster flees.

样例 #1

样例输入 #1

样例输出 #1

YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES

解法

解题思路

首先我们发现，对于位置 $i$ 的怪物，能够与它战斗的 $k$ 一定满足单调性，也就是 $k$ 越大，就越有可能与它发生战斗，相应的，我们可以得到一个阈值，在这个值之前一定不会战斗，在这个值之后，一定会战斗，我们考虑如何求这个阈值。

因为位置在 $i$ 怪物之前的怪物可能会发生战斗，从而提升我们的等级，因此，我们需要考虑什么样的怪物对我们的等级会有贡献。

容易发现，如果我们当前可以与怪兽发生战斗的最低等级为 $k$ ，那么就会对 $k - I NF$ 的升级轮数具有贡献经验的作用。

因此我们可以从左到右枚举每个怪物，然后二分出我们可以与它战斗的最低等级。二分时，我们只需要判断当前的经验能让我们升多少级，并与怪物的等级作比较，最后我们再使用树状数组将 $k - I NF$ 的升级轮数加上 $1$ 即可。

在预处理之后，就可以进行 $O (1)$ 查询啦

代码


const int N = 2e5 + 10;
 
int tree[N];
 
int n, q;
inline int lowbit(int x) { return x & (-x); }
inline void add(int i, int val) {
	while (i <= n) {
		tree[i] += val;
		i += lowbit(i);
	}
}
 
inline int query(int i) {
	int res = 0;
	while (i > 0) {
		res += tree[i];
		i -= lowbit(i);
	}
	return res;
}
 
void solve() {
	std::cin >> n >> q;
 
	std::vector<int>a(n + 1);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
	}
 
	std::vector<int>res(n + 1);
	for (int i = 1; i <= n; ++i) {
		int l = 1, r = n, k = 1;
		while (l <= r) {
			int mid = l + r >> 1;
			int s = query(mid) / mid + 1;
			if (s <= a[i]) {
				k = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		res[i] = k;
		add(k, 1);
	}
 
	while (q--) {
		int i, x;
		std::cin >> i >> x;
 
		if (x >= res[i]) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
}
 
signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
 
	int t = 1;
	//std::cin >> t;
 
	while (t--) {
		solve();
	}
};