DDOSvoid's Blog

noip 模拟赛(某次校内赛)

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

没有链接放了 = =

题目描述

一个区间的价值定义为该区间中的最大值减最小值 给定 n 个数，求所有区间价值中，第 k 大值为多少

输入输出格式

输入格式：

输入文件名为 kth.in。 第 1 行两个数 n、k(k<=n*(n-1)/2) 第 2 行 n 个数,每个数<=10 9

输出格式：

输出文件名为 kth.out。 输出区间价值的第 k 大值。

输入输出样例

输入样例#1：
3 2
2 1 3

输出样例#1：
2

说明

对于30%的数据，n=500
对于60%的数据，n<=5000
对于100%的数据，n<=400000

Solution

显然可以二分，考虑如何判断

我们固定右端点，那么满足的右端点一定是递增的

关于移动左端点如何保存最大和最小值，其实就是滑动窗口，单调队列即可

虽然我写的是st表

时间复杂度 $O(nlogn)$

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#define maxn 400010
#define ll long long
#define INF 1000000000
using namespace std;

int n, a[maxn]; ll k;

int st1[maxn][21], st2[maxn][21], Log[maxn]; 
void init_st() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            st1[i][j] = min(st1[i][j - 1], st1[i + (1 << j - 1)][j - 1]);
            st2[i][j] = max(st2[i][j - 1], st2[i + (1 << j - 1)][j - 1]);
        }
}

int query_min(int l, int r) {
    int k = Log[r - l + 1];
    return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}

int query_max(int l, int r) {
    int k = Log[r - l + 1];
    return max(st2[l][k], st2[r - (1 << k) + 1][k]);
}

ll check(int x) {
    int j = 1; ll s = 0; 
    for (int i = 1; i <= n; ++i) {
        while (j <= n && query_max(i, j) - query_min(i, j) < x) ++j;
        s += n - j + 1;  
    }
    return s; 
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), st1[i][0] = st2[i][0] = a[i];
    init_st(); 
    ll l = 1, r = (ll) n * (n - 1) / 2, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid) >= k) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << endl; 
    return 0;
}