結果

問題 No.3251 kthmex
コンテスト
ユーザー V_Melville
提出日時 2025-08-29 23:02:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,421 bytes
コンパイル時間 3,882 ms
コンパイル使用メモリ 297,508 KB
実行使用メモリ 21,628 KB
最終ジャッジ日時 2025-08-29 23:02:47
合計ジャッジ時間 8,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    int D = max<int>(1, sqrt(n/2));
    int nb = (n+D-1)/D;
    
    vector<unordered_map<int, int>> cnt(nb);
    vector<vector<int>> keys(nb);
    vector<int> L(nb), R(nb);
    
    rep(b, nb) {
        L[b] = b*D;
        R[b] = min(n, L[b]+D);
        auto& mp = cnt[b];
        for (int i = L[b]; i < R[b]; ++i) mp[a[i]]++;
        for (auto& p : mp) keys[b].push_back(p.first);
    }
    
    auto ekinb = [&](int b, int x) {
        if (cnt[b].count(x) and cnt[b][x] > 0) {
            auto& vs = keys[b];
            bool f = false;
            for (int v : vs) {
                if (v == x) {
                    f = true;
                    break;
                }
            }
            if (!f) vs.push_back(x);
        }
    };
    auto rkfb = [&](int b, int x) {
        if (!cnt[b].count(x) or cnt[b][x] == 0) {
            auto& vs = keys[b];
            rep(i, vs.size()) {
                if (vs[i] == x) {
                    vs[i] = vs.back();
                    vs.pop_back();
                    break;
                }
            }
        }
    };
    
    rep(qi, q) {
        int type, l, r;
        cin >> type >> l >> r;
        --l; --r;
        int bl = l/D, br = r/D;
        
        if (type == 1) {
            int x, y;
            cin >> x >> y;
            
            if (x == y) continue;
            if (bl == br) {
                for (int i = l; i <= r; ++i) {
                    if (a[i] == x) {
                        int b = i/D;
                        auto it = cnt[b].find(x);
                        if (it != cnt[b].end()) {
                            it->second--;
                        }
                        cnt[b][y]++;
                        a[i] = y;
                    }
                }
                ekinb(bl, y);
                rkfb(bl, x);
            }
            else {
                int lend = R[bl]-1;
                for (int i = l; i <= lend; ++i) {
                    if (a[i] == x) {
                        int b = i/D;
                        cnt[b][x]--;
                        cnt[b][y]++;
                        a[i] = y;
                    }
                }
                ekinb(bl, y);
                rkfb(bl, x);
                
                int rs = L[br];
                for (int i = rs; i <= r; ++i) {
                    if (a[i] == x) {
                        int b = i/D;
                        cnt[b][x]--;
                        cnt[b][y]++;
                        a[i] = y;
                    }
                }
                ekinb(br, y);
                rkfb(br, x);
                
                for (int b = bl+1; b < br; ++b) {
                    auto it = cnt[b].find(x);
                    if (it == cnt[b].end() or it->second == 0) break;
                    int c = it->second;
                    it->second = 0;
                    cnt[b][y] += c;
                    ekinb(b, y);
                    rkfb(b, x);
                }
            }
        }
        else {
            int k;
            cin >> k;
            unordered_set<int> s;
            if (bl == br) {
                for (int i = l; i <= r; ++i) s.insert(a[i]);
            }
            else {
                for (int i = l; i < R[bl]; ++i) s.insert(a[i]);
                for (int i = L[br]; i <= r; ++i) s.insert(a[i]);
                for (int b = bl+1; b < br; ++b) {
                    for (int v : keys[b]) {
                        if (cnt[b].count(v) and cnt[b][v] > 0) s.insert(v);
                    }
                }
            }
            
            vector<int> vs;
            for (int v : s) if (v > 0) vs.push_back(v);
            sort(vs.begin(), vs.end());
            int pre = 0;
            int ans = -1;
            for (int v : vs) {
                if (v == pre) continue;
                int gap = v-pre-1;
                if (k <= gap) {
                    ans = pre+k;
                    break;
                }
                k -= gap;
                pre = v;
            }
            if (ans == -1) ans = pre+k;
            cout << ans << '\n';
        }
    }
    
    return 0;
}
0