問題

問題概要

長さ $n$ の数列 $a$ がある。次のようなクエリを考える：

クエリ 1 $(l,r)$ : 区間 $[ l, r ]$ について、数字 $i$ が現れる回数を $c_i$ として、集合 ${c_0 , c_1 , \ldots , c_{10^9} }$ のmexを答える。
クエリ 2 $(p,x)$ : $a_p$ の値を $x$ に変更する。

以上のクエリが合計で $q$ 個与えられるので、順に処理せよ。

$1 \le n,q \le 100000$
$1 \le a_i \le 10^9$
$1 \le l \le r \le n$
$1 \le p \le n$
$1 \le x \le 10^9$

アイデア

愚直な処理はTLEしてしまう(submission)。

まず、クエリ1で出力すべき値がそこまで大きくない。なぜなら、xを答えにさせるには、最低限の現れる回数をを考えると $1,2, \ldots , x-1$ 回現れる数字がそれぞれあるということなにで、答えは $O(\sqrt{n})$ で抑えられている。

そこで、もし変更がなければMoが出来るなーと思いが巡った(その数字が現れる回数を配列 $ct$ に、現れる回数の個数を配列 $sz$ で管理することにすると、区間を1伸ばしたり縮めたりするのは $O(1)$ で出来、クエリに対しては上の考察から $O(\sqrt{n})$ で答えられる)。

今回は、2種類のクエリが来ると考えるのではなく、クエリ1しか来ないと考えて、クエリ1を次のように3つの数で与えられるクエリということにする：

クエリ $(t,l,r)$ : 既にクエリ2を $t$ 個実行した状態で、区間 $[ l, r ]$ について、数字の出現頻度のmexを答える。

クエリをこの形に言い換えると、状態としてこの3変数を持ち、いずれかの変数を+1,-1したときに $ct,sz$ がどうなるかの更新は $O(1)$ で行うことが可能である。この事実を踏まえて、 $t$ と $l$ に関してはブロックサイズ $S$ ごとに組にして分けることにする。このとき、クエリ毎に $t,l$ は $O(S)$ だけ変化するので、全体として $O(qS)$ 、 $r$ は $\frac{n}{S}$ 回だけ $O(n)$ の変化するので、全体として $O(\frac{n^2}{S})$ の変化をする。 $q$ と $n$ のオーダーが等しいことも考慮すると、ブロックサイズ $S$ として適切なのは $S = n^{\frac{2}{3}}$ であり、このとき全体は $O(n^{\frac{5}{3}})$ となる。

あとは、Moをする時の頻度のカウントにmapなどを使うと計算量が悪くなってしまうので、予め登場する数字をチェックして座圧しとくと良い。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct Query{
    int t,x,y;
};

// 既にch_queryをt個,区間[x,y]
vector<Query> mex_query;
// t番目の要素をxからyに変更
vector<Query> ch_query;

const int N = 200000;
int ct[N]={}, sz[N]={};

const int SZ = 2100;
const int B = 60;

using pi = pair<int,int>;
set<pi> mx[B][B]={};
int a[N]={};

int L=0,R=-1;
int T=-1;

inline void pr(){
    ++R;
    --sz[ct[a[R]]];
    ++ct[a[R]];
    ++sz[ct[a[R]]];
}

inline void pl(){
    --sz[ct[a[L]]];
    --ct[a[L]];
    ++sz[ct[a[L]]];
    ++L;
}

inline void mr(){
    --sz[ct[a[R]]];
    --ct[a[R]];
    ++sz[ct[a[R]]];
    --R;
}

inline void ml(){
    --L;
    --sz[ct[a[L]]];
    ++ct[a[L]];
    ++sz[ct[a[L]]];
}

inline void pt(){
    ++T;
    int idx = ch_query[T].t;

    if(L<=idx && idx<=R){
        --sz[ct[a[idx]]];
        --ct[a[idx]];
        ++sz[ct[a[idx]]];
    }

    assert(a[idx] == ch_query[T].x);
    a[idx] = ch_query[T].y;

    if(L<=idx && idx<=R){
        --sz[ct[a[idx]]];
        ++ct[a[idx]];
        ++sz[ct[a[idx]]];
    }
}

inline void mt(){
    int idx = ch_query[T].t;

    if(L<=idx && idx<=R){
        --sz[ct[a[idx]]];
        --ct[a[idx]];
        ++sz[ct[a[idx]]];
    }

    assert(a[idx] == ch_query[T].y);
    a[idx] = ch_query[T].x;

    if(L<=idx && idx<=R){
        --sz[ct[a[idx]]];
        ++ct[a[idx]];
        ++sz[ct[a[idx]]];
    }
    --T;
}

inline int calc(){
    int ret = 1;
    while(sz[ret]!=0) ++ret;
    return ret;
}

int main(){
    int n,Q;
    scanf(" %d %d", &n, &Q);
    rep(i,n) scanf(" %d", &a[i]);

    vector<int> ta(n);
    rep(i,n) ta[i] = a[i];

    rep(i,Q){
        int t,l,r;
        scanf(" %d %d %d", &t, &l, &r);
        if(t==1){
            --l;
            --r;
            mex_query.pb({(int)ch_query.size(), l, r});
        }
        else{
            --l;
            ch_query.pb({l, ta[l], r});
            ta[l] = r;
        }
    }

    // クエリ全体で現れる値を列挙
    vector<int> v;
    rep(i,n) v.pb(a[i]);
    for(const auto &q:ch_query) v.pb(q.y);
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    // 変換
    rep(i,n) a[i] = lower_bound(all(v), a[i]) - v.begin();
    rep(i,ch_query.size()){
        ch_query[i].x = lower_bound(all(v), ch_query[i].x) - v.begin();
        ch_query[i].y = lower_bound(all(v), ch_query[i].y) - v.begin();
    }

    // ブロックごとにクエリを分類
    int M = mex_query.size();
    rep(i,M) mx[mex_query[i].t/SZ][mex_query[i].x/SZ].insert({mex_query[i].y, i});

    // 実際にクエリを処理
    vector<int> ans(M);
    rep(i,B)rep(j,B){
        for(const auto &p:mx[i][j]){
            int ID = p.se;

            // 区間を動かす
            while(R < mex_query[ID].y) pr();
            while(mex_query[ID].y < R) mr();
            while(mex_query[ID].x < L) ml();
            while(L < mex_query[ID].x) pl();

            // ch_queryを動かす
            while(T+1 < mex_query[ID].t) pt();
            while(mex_query[ID].t < T+1) mt();

            // 答えを求める
            ans[ID] =  calc();
        }
    }

    rep(i,M) printf("%d\n", ans[i]);
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 940 F - Machine Learning

問題

問題概要

アイデア

実装(C++)