Educational Codeforces Round 80 E. Messenger Simulator

問題: Problem - E - Codeforces

公式解説: Educational Codeforces Round 80 Editorial - Codeforces

問題概要

整数 $n, \mathit{m} (1 \leq n, \mathit{m} \leq 3 \times 10^5$ と数列 $a_1, a_2, \cdots, a_m (1 \leq a_i \leq n)$ が与えられる．

順列 $p = [ 1, 2, \cdots, n]$ に対して以下の $\mathit{m}$ 回の操作を適用する過程で，1 から $n$ までの各値のインデックスの最小値と最大値を答えよ．

$i$ 回目の操作: $a_i$ を $p$ の先頭 (インデックス 1 の位置) にもってくる．

解法概要

各要素がインデックスの最小値・最大値を取りうるのがどのタイミングかを考えてみる．

最小値は簡単で，$a$ の中に注目する要素 $p_i$ が登場するなら 1，そうでなければ $p_i$ そのものとなる．

最大値については．$a$ 中で $p_i$ が登場する直前またはすべての操作が終わったあとのいずれかのタイミングで最大値になる．

ただし問題の操作をそのままやろうとすると，ある要素を先頭にもってきた時に元々その要素より前にあって要素たちを後ろに1つずつ動かすことが必要．これは愚直にやると当然 TLE してしまう．

そこで，1つの要素のインデックスだけをいじればいいように，操作を次のように言い換える．

$i$ 回目の操作: $a_i$ をインデックス $m_{\mathit{MAX}} - 1 - i$ の位置に持ってくる．

ただし，この場合 $p$ に対応する配列の初期化が必要で，次のようになる．

要素 $i$ のインデックスを $m_{\mathit{MAX}} + i$ とする．

あとは先ほど考察した「最大値を取りうるタイミング」で注目する要素が何番目に小さいインデックスを持つのかをチェックして答えの配列を更新すればよい．何番目に小さいインデックスを持つのかを計算する部分は愚直にやっては間に合わないが，どのインデックスに値が入っているかを BIT で管理しておけば，$O(\log{(n_{\mathit{MAX}} +m_{\mathit{MAX}})})$ で順位を求めることが可能になる (「どの値が入っているか」の情報は別の配列で持っておく．BIT では「値の有無」だけ管理すればよい) ．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int N_MAX = 300000;
constexpr int M_MAX = 300000;

template<typename T>class BIT {
    public:
    int n;
    vector<T> bit;
    
    BIT(int n): n(n){
        bit.resize(n);
        fill(bit.begin(), bit.end(), (T)0);
    }

    void add(int idx, T x){
        for(int i=idx;i<=this->n;i+=i&-i) bit[i] += x;
    }

    //bit[1]からbit[end]までの和 (閉区間)
    T sum(int end){
        T ret = (T)0;
        for(int i=end;i>=1;i-=i&-i) ret += bit[i];
        return ret;
    }
};


int main() {
    int n, m;
    cin >> n >> m;
    vector<int> pos(n+1), ans_min(n+1), ans_max(n+1);
    BIT<int> tree(N_MAX+M_MAX+1);
    for(int i=1;i<=n;++i) {
        pos[i] = M_MAX + i;
        ans_min[i] = i;
        ans_max[i] = i;
        tree.add(M_MAX+i, 1);
    }

    int a = -1;
    for(int i=0;i<m;++i) {
        cin >> a;
        
        ans_max[a] = max(ans_max[a], tree.sum(pos[a]));
        
        tree.add(pos[a], -1);
        tree.add(M_MAX - i, 1);
        pos[a] = M_MAX - i;
        ans_min[a] = 1;
    }

    for(int i=1;i<=n;++i) {
        ans_max[i] = max(ans_max[i], tree.sum(pos[i]));
        cout << ans_min[i] <<  " " << ans_max[i] << endl;
    }
    cout << endl;

}

所感

時間かけちゃったけど自力で解けて素直に嬉しい．