第一眼：这题不就是纯数据结构吗？线段树直接秒 第二眼：不对 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本题难度：黄 上位/绿 下位 由于只需要输出 Yes No，思考如何转化。 我们可以对 AAA 数组中所有 <Ki\lt K_i<Ki 的元素打上封锁标记，然后求出没有被封锁的，连续的元素块的最大长度即可。 如第二个样例的第 666 次询问，我们可以把 A3,A7A_3,A_7A3 ,A7 打上标记，此时没有被封锁的连续的元素块有：(A1,A2)(A_1,A_2)(A1 ,A2 )，(A4,A5,A6)(A_4,A_5,A_6)(A4 ,A5 ,A6 )，(A8,A9,A10)(A_8,A_9,A_{10})(A8 ,A9 ,A10 )。显然最大长度为 3≥23\ge 23≥2 ，所以该询问的答案为 Yes。 但是如何打封锁标记呢？如果直接对于每次询问清空然后再打标记，或对比上一次询问的差异修改，最坏情况下都得进行 NNN 次标记操作，总共标记次数是 O(NQ)O(NQ)O(NQ) 的。 这时就需要转离线了：我们把所有询问按询问的 KiK_iKi 值从小到大排个序，然后每次询问就只需要新增封锁点了！显然，每个点最多只会被标记一次，所以总共只能标记 NNN 次。 我们可以维护两个可重集合，一个命名为 nums\text{nums}nums，存储被标记的元素的下标，另一个命名为 sizes\text{sizes}sizes，存储每一个连续元素块的大小。对于第二个样例的第 666 次询问，第一个集合就为 {3,7}\{3,7\}{3,7}，第二个集合就为 {2,3,3}\{2,3,3\}{2,3,3}。 对于一个需要封锁的元素 AxA_xAx ，我们进行如下操作： 1. 找到这个点所处的元素块的左右端点（即 nums.upper_bound(x)\text{nums.upper\_bound}(x)nums.upper_bound(x) 和 nums.upper_bound(x)−1\text{nums.upper\_bound}(x)-1nums.upper_bound(x)−1）。 2. 计算出该元素块的大小为 nums[nums.upper_bound(x)]−nums[nums.upper_bound(x)−1]−1\text{nums}[\text{nums.upper\_bound}(x)]-\text{nums}[\text{nums.upper\_bound}(x)-1]-1nums[nums.upper_bound(x)]−nums[nums.upper_bound(x)−1]−1。 3. 在 sizes\text{sizes}sizes 中删除这个元素块的大小。 4. 将该元素块分成两个，显然这两个的大小分别为 x−[nums.upper_bound(x)−1]−1x-[\text{nums.upper\_bound}(x)-1]-1x−[nums.upper_bound(x)−1]−1，[nums.upper_bound(x)]−x−1[\text{nums.upper\_bound}(x)]-x-1[nums.upper_bound(x)]−x−1。 5. 在 sizes\text{sizes}sizes 中加入这两个数。 6. 在 nums\text{nums}nums 中加入 xxx。（如果一开始就加的话就会导致 nums[nums.upper_bound(x)−1]\text{nums[nums.upper\_bound}(x)-1]nums[nums.upper_bound(x)−1] 的值为 xxx） 这么操作过后连续的未被封锁的元素长度的最大值就 nums\text{nums}nums 的最后一个元素了！我们只需要判断这个数是否大于等于 LiL_iLi 即可。 时间复杂度：O(Nlog⁡N+Qlog⁡Q+Qlog⁡N)O(N\log N+Q\log Q+Q\log N)O(NlogN+QlogQ+QlogN)。由于 set 是平衡树实现修改操作常数巨大，故运行时间约为 2s。你可以用树状数组模拟 set，减小常数。 这里写一个变式： 给定一个 NNN 的元素的数组 AAA。定义 f(x)f(x)f(x) 如下： max⁡i=1N−x+1(min⁡j=ii+x−1Aj)\max_{i=1}^{N-x+1}(\min_{j=i}^{i+x-1} A_j) i=1maxN−x+1 (j=imini+x−1 Aj ) 请你求出 f(1),f(2),...,f(N)f(1),f(2),...,f(N)f(1),f(2),...,f(N) 的值。N≤5×105N\le 5\times 10^5N≤5×105。