牛客多校4.K.King of Range ST表+双指针

给定 n n n个整数和 m m m个询问，对于每个询问给定一个常数k，你需要找到有多少个区间 ( l , r ) (l, r) (l,r)满足序列的内所有元素 ≥ k \geq k ≥k​​。注意序列无序。

n ∈ [ 1 , 1 0 5 ] , m ∈ [ 1 , 100 ] n \in [1, 10^5], m \in [1, 100] n∈[1,105],m∈[1,100]​​，显然需要一个高效​的算法，首先考虑双指针求解。

首先对于一段区间 [ l , r ] [l, r] [l,r]​，如果其区间最大值和区间最小值之差大于 k k k，那么当前区间可以产生 n − r + 1 n - r + 1 n−r+1​​个符合条件的区间：设 m a x n , m i n n maxn,minn maxn,minn分别表示当前区间的最大值、最小值，如果 m a x n − k > m i n n maxn - k > minn maxn−k>minn​​，那么说明该区间一定符合要求，那么包含该区间的区间也一定符合要求( m i n n minn minn值只会越来越小， m a x n maxn maxn值指挥越来越大)，因此符合要求的区间数 n − r + 1 n - r + 1 n−r+1

那么我们可以每次固定区间左端点，右端点向后找到第一个满足区间最大值和区间最小值之差大于 k k k的点，然后将符合要求的区间数累加到答案中即可。

接下来考虑如何处理区间最大值最小值。考虑最优RMQ问题解决方案：ST表。因此可以 0 ( n l o g n ) 0(nlogn) 0(nlogn)建大小ST表，然后在上述过程中 O ( 1 ) O(1) O(1)查询。

一开始左指针没控制好，WA了几发，心态爆炸。。。

#include 
using namespace std;
 
#define N 2000010
 
int stmax[N][22], stmin[N][22], mn[N];
int a[N];
 
int t, q, n, x, y;
 
void init(){
    mn[0]=-1;
    for (int i=1;i