Codeforces - 6E - Exposition

https://codeforc.es/problemset/problem/6/E

既然可以多个log，那就直接map伺候。尺取之后要查询区间里面的最大值和最小值的差。众所周知尺取的时候要是不是有序序列，不可能方便地维护极值。（或者不用map以及平衡树的话，那就用线段树，每次update一个数量，然后RMQ最值，线段树（假如不是这个范围）还得先离散化，非常傻逼）。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;

int h[100005];

map<int, int> m;

vector<int> b;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

    //freopen("Yinku.out", "w", stdout);

#endif // Yinku

    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; ++i)

        scanf("%d", &h[i]);

    int maxlen = 0;

    b.resize(n);

    for(int l = 1, r = 1; r <= n; ++r) {

        ++m[h[r]];

        while(m.rbegin()->first - m.begin()->first > k) {

            if(m[h[l]] == 1)

                m.erase(h[l]);

            else

                --m[h[l]];

            ++l;

        }

        if(maxlen < r - l + 1) {

            maxlen = r - l + 1;

            b.clear();

            b.push_back(l);

        } else if(maxlen == r - l + 1)

            b.push_back(l);

    }

    printf("%d %d\n", maxlen, b.size());

    for(auto i : b)

        printf("%d %d\n", i, i + maxlen - 1);

}

巴特西

Codeforces - 6E - Exposition - 尺取

最新文章

热门文章