奇异搞笑

第一眼：这题不就是纯数据结构吗？线段树直接秒

第二眼：不对

---

本题难度：黄 上位/绿 下位

由于只需要输出 Yes No，思考如何转化。

我们可以对 $A$ 数组中所有 $\lt K_i$ 的元素打上封锁标记，然后求出没有被封锁的，连续的元素块的最大长度即可。 如第二个样例的第 $6$ 次询问，我们可以把 $A_3,A_7$ 打上标记，此时没有被封锁的连续的元素块有：$(A_1,A_2)$，$(A_4,A_5,A_6)$，$(A_8,A_9,A_{10})$。显然最大长度为 $3\ge 2$​，所以该询问的答案为 Yes。

但是如何打封锁标记呢？如果直接对于每次询问清空然后再打标记，或对比上一次询问的差异修改，最坏情况下都得进行 $N$ 次标记操作，总共标记次数是 $O(NQ)$ 的。

这时就需要转离线了：我们把所有询问按询问的 $K_i$ 值从小到大排个序，然后每次询问就只需要新增封锁点了！显然，每个点最多只会被标记一次，所以总共只能标记 $N$ 次。

我们可以维护两个可重集合，一个命名为 $\text{nums}$，存储被标记的元素的下标，另一个命名为 $\text{sizes}$，存储每一个连续元素块的大小。对于第二个样例的第 $6$ 次询问，第一个集合就为 $\{3,7\}$，第二个集合就为 $\{2,3,3\}$。

对于一个需要封锁的元素 $A_x$，我们进行如下操作：

1. 找到这个点所处的元素块的左右端点（即 $\text{nums.upper\_bound}(x)$ 和 $\text{nums.upper\_bound}(x)-1$）。
2. 计算出该元素块的大小为 $\text{nums}[\text{nums.upper\_bound}(x)]-\text{nums}[\text{nums.upper\_bound}(x)-1]-1$。
3. 在 $\text{sizes}$ 中删除这个元素块的大小。
4. 将该元素块分成两个，显然这两个的大小分别为 $x-[\text{nums.upper\_bound}(x)-1]-1$，$[\text{nums.upper\_bound}(x)]-x-1$。
5. 在 $\text{sizes}$ 中加入这两个数。
6. 在 $\text{nums}$ 中加入 $x$。（如果一开始就加的话就会导致 $\text{nums[nums.upper\_bound}(x)-1]$ 的值为 $x$）

这么操作过后连续的未被封锁的元素长度的最大值就 $\text{nums}$ 的最后一个元素了！我们只需要判断这个数是否大于等于 $L_i$ 即可。

#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
int a[1000005];
pair <int, int> b[1000005];
bool ans[1000005];
int n, m, cur = 1;
multiset <int> nums;
multiset <int> sizes;
struct Query{
	int x, y, idx;
	bool operator < (const Query &b) const{
		if(y == b.y) return idx < b.idx;
		return y < b.y;
	}
}q[1000005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	nums.insert(0);
	nums.insert(n + 1);
	sizes.insert(n);
	for(int i = 1; i <= n; i++) cin >> a[i], b[i] = {a[i], i};
	for(int i = 1; i <= m; i++){
		cin >> q[i].x >> q[i].y;
		q[i].idx = i;
	}
	sort(q + 1, q + m + 1);//转离线，以便修改被封锁的元素
	sort(b + 1, b + n + 1);//由于是封锁从小到大的，所以将数组中的元素从小到大排序
	for(int i = 1; i <= m; i++){
		while(cur <= n && b[cur].first < q[i].y){//添加封锁的元素
			auto idx = nums.upper_bound(b[cur].second);//按照上面的方法进行操作
			int tmplen = *idx;
			idx--;
			tmplen -= *idx;
			tmplen--;
			sizes.erase(sizes.find(tmplen));
			sizes.insert(b[cur].second - (*idx) - 1);
			idx++;
			sizes.insert((*idx) - b[cur].second - 1);
			nums.insert(b[cur].second);
			cur++;
		}
		ans[q[i].idx] = ((*sizes.rbegin()) >= q[i].x);//判断，rbegin换成end--也可以
	}
	for(int i = 1; i <= m; i++){
		cout << (ans[i] ? "Yes\n" : "No\n");
	}

	return 0;
}

时间复杂度：$O(N\log N+Q\log Q+Q\log N)$。由于 set 是平衡树实现修改操作常数巨大，故运行时间约为 2s。你可以用树状数组模拟 set，减小常数。

这里写一个变式：

给定一个 $N$ 的元素的数组 $A$。定义 $f(x)$ 如下：

$$\max_{i=1}^{N-x+1}(\min_{j=i}^{i+x-1} A_j)$$

请你求出 $f(1),f(2),...,f(N)$ 的值。$N\le 5\times 10^5$。