問題概要

長さが $ n (\leq 10^6) $ の数列 $ a = a_1, a_2, \cdots a_n (1 \leq a_i \leq 10^6) $ がある．このとき，

$ f(l, r) = $ $ a $ から $ l \leq a_i \leq r $ となるような $ a_i $ を全て取り除いたもの (ただし，$ 1 \leq l,r \leq x $ )

とする．

$ f(l, r) $ が非減少列となる $ l,r $ の選び方が何通りあるかを求めよ．

解法概要

まず初めに，$ a $ に 1 から$ x $ までの整数が全て含まれる場合を考える．

$ a_i $ の出現するインデックスの最小値と最大値をそれぞれ $ \mathit{maxidx}(a_i) $ ，$ \mathit{minidx}(a_i) $ とする．

f:id:noimin:20190518164442p:plain

$ f(l, r) $ が非減少列のとき，$ f(l, r+1) $ や $ f(l-1, r) $ も非減少列である (非減少列から特定の数のみを取り除いても他の隣り合う要素の大小が逆転することはないため) ．

このことを利用して， $ l $ を固定したときの $ r $ をいい感じに求めて，$ l $ を増やしながら $ r $ もそれに合わせて増やしていくことを考える． (いわゆる尺取り法)

$ l $ の値ごとに可能な $ r $ の選び方を答えに加算していきたいので，$ r $ は「$ l $ がその値のとき， $ f(l, r) $ が非減少列となる最小の数」とする．

$ l = 1 $ のとき， $ f(1, x-1) $ は絶対に非減少列になる (値が 1 種類しか含まれないため) ．ただし今求めたい $ r $ は非減少列となる最小の数なので，r をできる限り小さくしたい．したがって，$ \mathit{maxidx}(r) > \mathit{minidx}(r+1) $ となるような (つまり，$ r $ を残してしまったら非減少にならなくなるような) r まで r を減らす．

$ f(l, r) $ が非減少列のとき，$ f(l, r+1) $ も非減少列なのだから，「$ l $ がその値のとき， $ f(l, r) $ が非減少列となる最小の数」としての $ r $ が求められたら，$ l = 1 $ である $ l,r $ の選び方は $ x-r+1 $ である．

$ l = 2 $ 以降では $ l - 1 $ に対応する $ r $ から始めて，$ r $ を適切に増やしていく必要がある．これは，1 から $ l-1 $ までの値と $ r+1 $ から $ x $ までの値で非減少列を作る必要がある．そのため，$ \mathit{minidx}(r+1) $ が $ \mathit{maxidx}(l-1) $ を超えるまで (もしくは $ r = x $ まで) $ r $ を増やさなければならない．

$ r $ が求められたら，$ l = 1 $ のときと同様に $ x-r+1 $ を答えに加算する．

ただし，$ l $ をこれ以上増やせない場合がある．上図でいう $ l = 3 $ のとき， 1 と 2 は数列に残されるが，1 と 2を残している地点で非減少にはなり得ない．そのため，これ以上大きな $ l $ を試す必要はない．

ここまで $ a $ に 1 から $ x $ までの整数が全て含まれる場合を考えた．実際のテストケースでは 1 から$ x $ までの整数が全て含まれるとは限らないので面倒くさくなる．例えば，上図の例でいう 4 が抜けた場合，

8 5
5 1 2 2 3 3 5 1

を考えてみよう．このとき，元の数列に 4 が含まれなくても $ f(1, 4) $ のような場合を考慮に入れて数え上げなければならないため注意が必要である．

このような「抜け」は，例えば $ \mathit{maxidx}(a_i) $ ，$ \mathit{minidx}(a_i) $ に -1 を入れて特別な場合として場合分けするなどで対処できる．

ソースコード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n, x, a;
    scanf("%d%d", &n, &x);
    vector<int> min_idx(x+2, -1), max_idx(x+2, -1);
    for(int i=0;i<n;++i){
        scanf("%d", &a);
        if(min_idx[a] == -1) {
            min_idx[a] = i;
        }
        max_idx[a] = i;
    }

    vector<int> numbers;
    numbers.push_back(0);
    for(int i=1;i<=x;++i) {
        if(min_idx[i] != -1) numbers.push_back(i);
    }
    numbers.push_back(x+1);
    int nn = numbers.size();

    int l = 1, r = max(1, numbers[nn-3]), r_prev_i = nn-4, r_next_i = nn-2;
    while(r > l && (min_idx[numbers[r_next_i]] == -1 || max_idx[r] < min_idx[numbers[r_next_i]])) {
        --r;
        if(r == numbers[r_prev_i]) {
            --r_prev_i;
            --r_next_i;
        }
    }
    ll ans = ll(x-r+1);

    int l_prev_i = distance(numbers.begin(), lower_bound(numbers.begin(), numbers.end(), l+1)) - 1;
    while(++l <= x) {
        if(l >= r) r = l;
        if(l > numbers[l_prev_i+1]) ++l_prev_i;
        if(r == numbers[r_next_i]) ++r_next_i;

        while(r < numbers[nn-2] && max_idx[numbers[l_prev_i]] > min_idx[numbers[r_next_i]]) {
            ++r;
            if(r == numbers[r_next_i]) ++r_next_i;
        }

        ans += ll(x-r+1);
        if(min_idx[l] != -1 && max_idx[numbers[l_prev_i]] > min_idx[l]) break;
    }

    printf("%lld\n", ans);
    
}

所感

解法概要での扱いは小さめだけど，1 から x までの値に抜けがある場合の場合分け処理がなかなか書けなかった……．

NoiminのNoise

Educational Codeforces Round 65 (Rated for Div. 2) E. Range Deleting

問題概要

解法概要

ソースコード

所感