結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー 👑 potato167
提出日時 2024-10-14 09:21:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 412 ms / 5,000 ms
コード長 2,548 bytes
コンパイル時間 2,316 ms
コンパイル使用メモリ 207,168 KB
最終ジャッジ日時 2025-02-24 19:24:45
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N), C(N);
    rep(i, 0, N) cin >> A[i];
    const int D = 3;
    const int M = 100'001;
    vector<vector<int>> G(M);
    vector<int> ind(M, 3);
    rep(i, 0, M) rep(j, 0, D) G[i].push_back(-1);
    rep(i, 0, N){
        G[A[i]].push_back(i);
    }
    rep(i, 0, M) rep(j, 0, D) G[i].push_back(N);
    const int B = 2048;
    vector<int> div_val(N + 1);
    vector<int> div_left(B + 1, INF);
    rep(i, 0, N + 1){
        div_val[i] = (i * B) / N;
        chmin(div_left[div_val[i]], i);
    }
    for (int i = B; i > 0; i--) chmin(div_left[i - 1], div_left[i]);
    vector pre(D, vector(B + 1, vector<int>(B + 1, INF)));
    vector val(D, vector<int>(B + 1, INF));
    rep(i, 0, D) rep(j, 0, M){
        chmin(val[i][div_val[G[j][3 + i]]], j);
    }
    int div_ind = 0;
    rep(i, 0, N + 1){
        while (div_ind != B + 1 && div_left[div_ind] == i){
            rep(j, 0, 3){
                pre[j][div_ind] = val[j];
                for (int k = B; k > 0; k--){
                    chmin(pre[j][div_ind][k - 1], pre[j][div_ind][k]);
                }
            }
            div_ind++;
        }
        if (i == N) break;
        C[i] = ind[A[i]];
        ind[A[i]]++;
        rep(j, 0, D){
            chmin(val[j][div_val[G[A[i]][ind[A[i]] + j]]], A[i]);
        }
    }
    int Q;
    cin >> Q;
    ll F = 0;
    rep(rp, 0, Q){
        ll l, r;
        cin >> l >> r;
        l ^= F, r ^= F;
        l--;
        vector<int> ans(3);
        rep(i, 0, 3){
            ans[i] = pre[i][div_val[l]][div_val[r - 1] + 1];
        }
        int L = div_left[div_val[l]];
        int R = div_left[div_val[r - 1] + 1];
        while (L < l){
            rep(j, 0, D){
                if (G[A[L]][C[L] + j + 1] >= R){
                    chmin(ans[j], A[L]);
                }
            }
            L++;
        }
        while (r < R){
            R--;
            rep(j, 0, D){
                if (G[A[R]][C[R] - j - 1] < L){
                    chmin(ans[j], A[R]);
                }
            }
        }
        F = 0;
        int tmp = 0;
        rep(i, 0, 3){
            F += ans[i];
            if (ans[i] == 0) tmp++;
        }
        chmin(F, r - l - tmp);
        cout << F << "\n";
    }
}
0