区间第k大

Posted on Edited on In

题目大意： 一个区间的价值定义为该区间中的最大值减最小值 给定 n 个数，求所有区间价值中，第 k 大值为多少。n是40万 显然对于一个右端点，左端点越靠左挪动，得到的价值，只能是递减或者是不降的

并且一定存在一个确切的位置，满足在这个位置左边（作为左端点）所得到的价值大于等于二分出来的mid，在这个位置右边一定小于

其中最大最小值用单调队列来维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int judge(int x)
{
    l1 = l2 = 1;
    r1 = r2 = 0;
    long long res = 0;
    for(int i = 1, l = 1; i <= n; ++ i)
    {
        while(l1 <= r1 && a[q1[r1]] <= a[i]) r1 --;
        while(l2 <= r2 && a[q2[r2]] >= a[i]) r2 --;
        q1[++ r1] = i， q2[++ r2] = i;
        // cout << r1 << " " << r2 << endl;
        while(l1 <= r1 && l2 <= r2 && a[q1[l1]] - a[q2[l2]] >= x)
        {
            l ++;
            if(q1[l1] < l) l1 ++;
            if(q2[l2] < l) l2 ++;
        }
        res += l - 1;
    }
    return res >= k;
}

while (l < r)
{
    int mid = (l + r + 1) / 2;
    if (judge(mid) >= k)//表示>=x的数是否>=k
        l = mid;
    else r = mid - 1;
}

注意是mid=(l+r+1)/2

因为我们想得到的在小于等于某个范围内的最大值