結果
問題 |
No.3251 kthmex
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }