結果

問題 No.3251 kthmex
ユーザー yukicoder
提出日時 2025-08-08 00:14:46
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,647 bytes
コンパイル時間 3,110 ms
コンパイル使用メモリ 180,184 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-12 19:06:32
合計ジャッジ時間 8,915 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 2 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;

const int MAX_Q = 300010;
const int B = 20000;
const int WS = (MAX_Q + 63) / 64;

struct Op {
    int t, l, r;
    long long x, y;
};

int get_root(vector<int>& parent, vector<int>& used_keys, int v) {
    int root = v;
    while (parent[root] != 0) root = parent[root];
    int cur = v;
    while (cur != root) {
        int nxt = parent[cur];
        parent[cur] = root;
        cur = nxt;
    }
    return root;
}

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

    int n, m;
    cin >> n >> m;
    vector<int> A(n + 1);
    vector<long long> all_vals;
    vector<Op> ops(m);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        all_vals.push_back(A[i]);
    }
    for (int i = 0; i < m; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        ops[i].t = t;
        ops[i].l = l;
        ops[i].r = r;
        if (t == 1) {
            long long x, y;
            cin >> x >> y;
            ops[i].x = x;
            ops[i].y = y;
            all_vals.push_back(x);
            all_vals.push_back(y);
        } else {
            long long k;
            cin >> k;
            ops[i].x = k;
        }
    }
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    int Q_ = all_vals.size();
    map<long long, int> rank_map;
    for (int i = 0; i < Q_; i++) {
        rank_map[all_vals[i]] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        A[i] = rank_map[A[i]];
    }
    for (int i = 0; i < m; i++) {
        if (ops[i].t == 1) {
            ops[i].x = rank_map[ops[i].x];
            ops[i].y = rank_map[ops[i].y];
        }
    }
    int num_block = (n + B - 1) / B;
    vector<vector<uint64_t>> block_bit(num_block, vector<uint64_t>(WS, 0));
    vector<vector<int>> block_parent(num_block, vector<int>(Q_ + 1, 0));
    vector<vector<int>> block_used(num_block);
    vector<int> block_size(num_block);
    for (int b = 0; b < num_block; b++) {
        int start = b * B + 1;
        int end = min(n, (b + 1) * B);
        block_size[b] = end - start + 1;
        auto& bb = block_bit[b];
        for (int i = start; i <= end; i++) {
            int idx = A[i];
            bb[idx / 64] |= (1ULL << (idx % 64));
        }
    }
    for (int oi = 0; oi < m; oi++) {
        Op op = ops[oi];
        if (op.t == 1) {
            int l = op.l, r = op.r, x = op.x, y = op.y;
            if (x == y) continue;
            int lb = (l - 1) / B;
            int rb = (r - 1) / B;
            for (int b = lb; b <= rb; b++) {
                int start = b * B + 1;
                int end = min(n, (b + 1) * B);
                vector<int>& parent = block_parent[b];
                vector<int>& used = block_used[b];
                auto& bb = block_bit[b];
                if (l <= start && end <= r) {
                    // full
                    int rx = x;
                    if (parent[rx] != 0) rx = get_root(parent, used, rx);
                    int ry = y;
                    if (parent[ry] != 0) ry = get_root(parent, used, ry);
                    if (rx == ry) continue;
                    parent[rx] = ry;
                    used.push_back(rx);
                    int wx = rx / 64, bx = rx % 64;
                    int wy = ry / 64, by = ry % 64;
                    if (bb[wx] & (1ULL << bx)) {
                        bb[wx] &= ~(1ULL << bx);
                        bb[wy] |= (1ULL << by);
                    }
                } else {
                    // partial
                    // First, apply existing lazy to A[]
                    for (int i = start; i <= end; i++) {
                        int val = A[i];
                        if (parent[val] != 0) {
                            A[i] = get_root(parent, used, val);
                        }
                    }
                    // Clear lazy
                    for (auto v : used) parent[v] = 0;
                    used.clear();
                    // Now apply the update
                    int pl = max(l, start);
                    int pr = min(r, end);
                    for (int i = pl; i <= pr; i++) {
                        if (A[i] == x) A[i] = y;
                    }
                    // rebuild bitset
                    fill(bb.begin(), bb.end(), 0);
                    for (int i = start; i <= end; i++) {
                        int idx = A[i];
                        bb[idx / 64] |= (1ULL << (idx % 64));
                    }
                }
            }
        } else {
            int l = op.l, r = op.r;
            long long k = op.x;
            // binsearch M
            long long low = 1, high = 2000000000LL + 1000000000LL;
            vector<uint64_t> unionb(WS, 0);
            int lb = (l - 1) / B;
            int rb = (r - 1) / B;
            for (int b = lb; b <= rb; b++) {
                int start = b * B + 1;
                int end = min(n, (b + 1) * B);
                auto& bb = block_bit[b];
                if (l <= start && end <= r) {
                    for (int wi = 0; wi < WS; wi++) {
                        unionb[wi] |= bb[wi];
                    }
                } else {
                    vector<int>& parent = block_parent[b];
                    vector<int>& used = block_used[b];
                    int pl = max(l, start);
                    int pr = min(r, end);
                    for (int i = pl; i <= pr; i++) {
                        int val = A[i];
                        if (parent[val] != 0) {
                            val = get_root(parent, used, val);
                        }
                        int idx = val;
                        unionb[idx / 64] |= (1ULL << (idx % 64));
                    }
                }
            }
            // build prefix pop
            vector<int> prefix_pop(WS + 1, 0);
            for (int i = 0; i < WS; i++) {
                prefix_pop[i + 1] = prefix_pop[i] + __builtin_popcountll(unionb[i]);
            }
            while (low < high) {
                long long mid = (low + high) / 2;
                auto it = upper_bound(all_vals.begin(), all_vals.end(), mid);
                int p = it - all_vals.begin();
                int w = p / 64;
                int bit = p % 64;
                uint64_t mask = (1LL << bit) - 1;
                int cnt = prefix_pop[w] + __builtin_popcountll(unionb[w] & mask);
                if (mid - cnt >= k) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            cout << low << '\n';
        }
    }
    return 0;
}
0