結果
| 問題 |
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 |
ソースコード
#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;
}