面白かった。
数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。

問題概要

$1, 2, \dots, N$ がこの順に並んでいる。ここから $M$ 回の操作を行う。

$i$ 回目の走査は、 $1$ 以上 $N$ 以下の値 $a_{i}$ で表され
現在の順列のうち、値 $a_{i}$ を先頭にもってくる操作を行う

たとえば (3, 4, 2, 1) に対して、値 2 を指定すると (2, 3, 4, 1) になる。各 $i (= 1, 2, \dots, N)$ に対して、操作過程において $i$ が登場した index の最小値と最大値を求めよ。

制約

$1 \le N, M \le 3 \times 10^{5}$

考えたこと

まず最小値は簡単

$a$ の中に $i$ があるなら、最小値は $1$
$a$ の中に $i$ がないなら、最小値は $i$

$i$ の登場する最大値を考える。 $a$ が

○, ○, ..., ○, $i$ ○, ○, ..., ○, $i$ , ○, ○, ..., ○, $i$ , ○, ..., ○

と表されるときに、先頭を除くと

「( $i$ で挟まれた区間に登場する値の種類数) + 1」の最大値

が答えになることがわかる。先頭は例外で

( $i$ で挟まれた区間に登場する $i$ より大きい値の種類数) + 1

となる。ただこれは扱いづらいので、 $a$ の先頭に付け加えて

$N, N-1, N-2, \dots, 2, 1$ ○, ○, ..., ○, $i$ ○, ○, ..., ○, $i$ , ○, ○, ..., ○, $i$ , ○, ..., ○

という風にする。こうしておくと、 $i$ で挟まれた区間に登場する値の種類数さえ答えればよくなる。それを行うための方法として、Mo や、BIT がある。それらについては以下の記事に。

drken1215.hatenablog.com

コード (1)： BIT

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> a;
    for (int i = 0; i < N; ++i) a.push_back(N-i-1);
    for (int j = 0; j < M; ++j) {
        int b; cin >> b; --b;
        a.push_back(b);
    }
    
    BIT<int> bit(N+M+10);
    vector<int> prev(N, -1);
    vector<bool> exist(N, false);
    vector<int> res(N, 0);
    for (int i = 0; i < N+M; ++i) {
        if (prev[a[i]] != -1) {
            chmax(res[a[i]], bit.sum(prev[a[i]]+2, prev[a[i]]+3) + 1);
        }
        bit.add(prev[a[i]]+2, i+2, 1);
        if (i >= N) exist[a[i]] = true;
        prev[a[i]] = i;
    }
    for (int i = 0; i < N; ++i) {
        chmax(res[i], bit.sum(prev[i]+2, prev[i]+3) + 1);
    }
    for (int i = 0; i < N; ++i) {
        if (exist[i]) printf("%d ", 1);
        else printf("%d ", i+1);
        printf("%d\n", res[i]);
    }
}

コード (2)： Mo 法

想定解法ではなさそうだけど、本番は Mo でやった。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
 
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
 
template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}
 
 
 
struct Mo {
    vector<int> left, right, index; // the interval's left, right, index
    vector<bool> v;
    int window;
    int nl, nr, ptr;
    
    Mo(int n) : window(max((int)sqrt(n), 1)), nl(0), nr(0), ptr(0), v(n, false) { }
    
    /* push */
    void push(int l, int r) { left.push_back(l), right.push_back(r); }
    
    /* sort intervals */
    void build() {
        index.resize(left.size());
        iota(begin(index), end(index), 0);
        sort(begin(index), end(index), [&](int a, int b) {
            if(left[a] / window != left[b] / window) return left[a] < left[b];
            return right[a] < right[b];
        });
    /*
        sort(begin(index), end(index), [&](int a, int b)
             {
                 if(left[a] / window != left[b] / window) return left[a] < left[b];
                 if(right[a] / window != right[b] / window) return bool((right[a] < right[b]) ^ (left[a] / window % 2));
                 return bool((index[a] < index[b]) ^ (right[a] / window % 2));
             });
    */
    }
    
    /* extend-shorten */
    void extend_shorten(int id) {
        v[id].flip();
        if (v[id]) insert(id);
        else erase(id);
    }
    
    /* next id of interval */
    int next() {
        if (ptr == index.size()) return -1;
        int id = index[ptr];
        while (nl > left[id]) extend_shorten(--nl);
        while (nr < right[id]) extend_shorten(nr++);
        while (nl < left[id]) extend_shorten(nl++);
        while (nr > right[id]) extend_shorten(--nr);
        return index[ptr++];
    }
    
    /* insert, erase (to be set appropriately) */
    void insert(int id);
    void erase(int id);
};
 
 
int N;
int A[1000001];
int cnt[1000001];
int num_kind = 0;
 
void Mo::insert(int id) {
    int val = A[id];
    if (cnt[val] == 0) ++num_kind;
    ++cnt[val];
}
 
void Mo::erase(int id) {
    int val = A[id];
    --cnt[val];
    if (cnt[val] == 0) --num_kind;
}
 
 
 
int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    
    int N, M;
    while (cin >> N >> M) {
        vector<int> a(M);
        for (int i = 0; i < M; ++i) scanf("%d", &a[i]), --a[i];
 
        vector<bool> exist(N, false);
        for (int i = 0; i < M; ++i) {
            exist[a[i]] = true;
        }
 
        vector<vector<int>> pls(N);
        for (int i = 0; i < N; ++i) pls[N-1-i].push_back(i), A[i] = N-1-i;
        for (int i = 0; i < M; ++i) pls[a[i]].push_back(i+N), A[i+N] = a[i];
 
        vector<int> left, right, ids;
        vector<int> res(N, 0);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < pls[i].size(); ++j) {
                left.push_back(pls[i][j] + 1);
                right.push_back(j+1 < pls[i].size() ? pls[i][j+1] : N+M);
                ids.push_back(i);
            }
        }
 
        //for (int i = 0; i < N+M; ++i) cout << A[i] << ","; cout << endl;
 
        Mo mo(N+M + 10);
        memset(cnt, 0, sizeof(cnt));
        num_kind = 0;
        int Q = left.size();
        for (int i = 0; i < Q; ++i) {
            mo.push(left[i], right[i]);
        }
        mo.build();
 
        for (int q = 0; q < Q; ++q) {
            auto moid = mo.next();
            auto kind = num_kind;
 
            //cout << moid << ": " << left[moid] << ", " << right[moid] << " (" << ids[moid] << "): " << kind << endl;
 
            int id = ids[moid];
            chmax(res[id], kind+1);
        }
 
        for (int i = 0; i < N; ++i) {
            if (exist[i]) printf("1 ");
            else printf("%d ", i+1);
            printf("%d\n", res[i]);
        }
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Educational Codeforces 80 E. Messenger Simulator (R2100)

問題概要

制約

考えたこと

コード (1)： BIT

コード (2)： Mo 法