Codeforces Round #333 (Div. 2) B. Approximating a Constant Range

Codeforces Round #333 (Div. 2) に参加しました。D 解きたかった〜〜〜〜〜〜〜〜〜〜

問題

codeforces.com

解法

しゃくとり法的にやります。

しゃくとり法のやり方はいろいろあったと思いますが, 僕はセグメント木でやりました。seg1[l, r] = (区間[l, r] の最大値), seg2[l, r] = (区間[l, r] の最小値)として, seg1[l, r] - seg[l, r] <= 1 となるようにしゃくとりしていきます。

ただ一番賢いのは multiset を使うことだったと思います…

const int MAXN = 100100;
int a[MAXN];

class segTree1 {
public:
    int N;
    vector<int> seg;
    segTree1(int V) {
        N = 1;
        while (N < V) N *= 2;
        seg.resize(2*N-1, MAXN);
    }
    void update(int k, int x) {
        k += N-1;
        seg[k] = x;
        while (k) {
            k = (k-1) / 2;
            seg[k] = min(seg[2*k+1], seg[2*k+2]);
        }
    }
    int get(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return MAXN;
        if (a <= l && r <= b) return seg[k];
        return min(get(a, b, 2*k+1, l, (l+r)/2), get(a, b, 2*k+2, (l+r)/2, r));
    }
    int get(int a, int b) {
        return get(a, b, 0, 0, N);
    }
};

class segTree2 {
public:
    int N;
    vector<int> seg;
    segTree2(int V) {
        N = 1;
        while (N < V) N *= 2;
        seg.resize(2*N-1, -1);
    }
    void update(int k, int x) {
        k += N-1;
        seg[k] = x;
        while (k) {
            k = (k-1) / 2;
            seg[k] = max(seg[2*k+1], seg[2*k+2]);
        }
    }
    int get(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) return seg[k];
        return max(get(a, b, 2*k+1, l, (l+r)/2), get(a, b, 2*k+2, (l+r)/2, r));
    }
    int get(int a, int b) {
        return get(a, b, 0, 0, N);
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    segTree1 seg1(n);
    segTree2 seg2(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        seg1.update(i, a[i]);
        seg2.update(i, a[i]);
    }
    int ans = 1;
    int s = 0, t = 1;
    for (;;) {
        while (t <= n) {
            if (seg2.get(s, t) - seg1.get(s, t) <= 1) {
                t++;
            } else break;
        }
        ans = max(ans, t-s-1);
        if (t > n) break;
        while (seg2.get(s, t) - seg1.get(s, t) > 1) s++;
        ans = max(ans, t-s);
    }
    cout << ans << endl;
    return 0;
}