Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
A normal Mo's algorithm almost works: when an endpoint vertex enters or leaves the interval, only and its neighbors can be affected.
Maintain over currently active neighbors . If vertex is toggled, scan all neighbors of and do . Also insert/delete active vertices' values from a multiset.
The multiset order statistic is easy because every XOR value is below . Use counts by value plus sqrt-decomposition buckets: update in , find -th in .
The real issue is that toggling vertex costs , not . So sorting queries by raw Mo blocks can repeatedly cross one huge-degree vertex and get cooked.
Run Mo's algorithm in weighted coordinates. Let , , and . Moving between intervals costs Manhattan distance in , so ordinary Mo on these transformed coordinates gives the needed behavior.
The obvious plan is Mo's algorithm on intervals. The less obvious part is that raw Mo is a trap: moving across vertex costs , so one celebrity vertex can nuke the runtime. The fix is to make Mo aware of that cost.
Maintaining One Interval
For the current interval , keep
This is maintained for all vertices, active or inactive. Also keep a multiset containing only for active vertices .
When a vertex is added to the interval:
Removal is the same idea in reverse: erase from the multiset, mark inactive, then XOR into all its neighbors' values again.
Why does this work? XOR is its own inverse. Adding neighbor contributes ; removing neighbor also means XORing by .
So one endpoint move costs
The matters. Even an isolated vertex still has to be inserted or removed from the active set. Ignoring that is how you get a very educational TLE. The bad kind of educational.
Getting The -th Value
The largest label is at most , so every XOR value is below .
Maintain:
cnt[value]: how many active vertices currently have this value;bucket[b]: total count inside a block of values.Then insertion/deletion of one value is , and the -th smallest value is found by scanning value-buckets, then scanning inside one bucket. This is where .
Weighted Mo's Algorithm
Raw Mo sorts queries by roughly . But here moving from to does not cost ; it costs toggling vertex , i.e.
Define prefix weights:
Represent interval as the point
Now look at two intervals and . The cost of changing the left endpoint is exactly the sum of over crossed vertices, which is
The right endpoint is similar:
So the real movement cost is Manhattan distance in weighted coordinates:
That means we can run normal Mo ordering, but on instead of raw .
Use block size around
Sort by block of , and inside each block sort by , alternating direction between blocks.
The total weighted movement is
which becomes
Since
and the total input size is bounded, this is fast enough.
Complexity
Let over one test group. The weighted Mo movement costs
and each query asks for a -th value in
Overall this is comfortably within the intended
shape.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MAXV = 1 << 18;
const int VBS = 512;
const int VNB = MAXV / VBS;
struct ValueBag {
int cnt[MAXV]{};
int bucket[VNB]{};
bool used[MAXV]{};
vector<int> touched;
void clear() {
for (int x : touched) {
cnt[x] = 0;
used[x] = false;
}
touched.clear();
fill(bucket, bucket + VNB, 0);
}
inline void add(int x, int delta) {
if (!used[x]) {
used[x] = true;
touched.push_back(x);
}
cnt[x] += delta;
bucket[x >> 9] += delta;
}
int kth(int k) const {
int b = 0;
while (bucket[b] < k) {
k -= bucket[b];
++b;
}
int x = b << 9;
while (true) {
if (cnt[x] >= k) return x;
k -= cnt[x];
++x;
}
}
} bag;
struct Query {
int l, r, k, id;
int x, y;
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
bag.clear();
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + (int)adj[i].size() + 1;
}
int totalWeight = pref[n];
int q;
cin >> q;
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
int l, r, k;
cin >> l >> r >> k;
queries[i] = {l, r, k, i, pref[l - 1], pref[r]};
}
int block = max(1, (int)(totalWeight / sqrt((double)q)) + 1);
sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b) {
int ba = a.x / block;
int bb = b.x / block;
if (ba != bb) return ba < bb;
if (ba & 1) return a.y > b.y;
return a.y < b.y;
});
vector<int> val(n + 1, 0), ans(q);
vector<char> active(n + 1, false);
auto addVertex = [&](int v) {
active[v] = true;
bag.add(val[v], +1);
for (int u : adj[v]) {
if (active[u]) bag.add(val[u], -1);
val[u] ^= v;
if (active[u]) bag.add(val[u], +1);
}
};
auto removeVertex = [&](int v) {
bag.add(val[v], -1);
active[v] = false;
for (int u : adj[v]) {
if (active[u]) bag.add(val[u], -1);
val[u] ^= v;
if (active[u]) bag.add(val[u], +1);
}
};
int L = 1, R = 0;
for (const Query &qq : queries) {
while (L > qq.l) addVertex(--L);
while (R < qq.r) addVertex(++R);
while (L < qq.l) removeVertex(L++);
while (R > qq.r) removeVertex(R--);
ans[qq.id] = bag.kth(qq.k);
}
for (int x : ans) cout << x << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MAXV = 1 << 18;
const int VBS = 512;
const int VNB = MAXV / VBS;
struct ValueBag {
int cnt[MAXV]{};
int bucket[VNB]{};
bool used[MAXV]{};
vector<int> touched;
void clear() {
for (int x : touched) {
cnt[x] = 0;
used[x] = false;
}
touched.clear();
fill(bucket, bucket + VNB, 0);
}
inline void add(int x, int delta) {
if (!used[x]) {
used[x] = true;
touched.push_back(x);
}
cnt[x] += delta;
bucket[x >> 9] += delta;
}
int kth(int k) const {
int b = 0;
while (bucket[b] < k) {
k -= bucket[b];
++b;
}
int x = b << 9;
while (true) {
if (cnt[x] >= k) return x;
k -= cnt[x];
++x;
}
}
} bag;
struct Query {
int l, r, k, id;
int x, y;
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
bag.clear();
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + (int)adj[i].size() + 1;
}
int totalWeight = pref[n];
int q;
cin >> q;
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
int l, r, k;
cin >> l >> r >> k;
queries[i] = {l, r, k, i, pref[l - 1], pref[r]};
}
int block = max(1, (int)(totalWeight / sqrt((double)q)) + 1);
sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b) {
int ba = a.x / block;
int bb = b.x / block;
if (ba != bb) return ba < bb;
if (ba & 1) return a.y > b.y;
return a.y < b.y;
});
vector<int> val(n + 1, 0), ans(q);
vector<char> active(n + 1, false);
auto addVertex = [&](int v) {
active[v] = true;
bag.add(val[v], +1);
for (int u : adj[v]) {
if (active[u]) bag.add(val[u], -1);
val[u] ^= v;
if (active[u]) bag.add(val[u], +1);
}
};
auto removeVertex = [&](int v) {
bag.add(val[v], -1);
active[v] = false;
for (int u : adj[v]) {
if (active[u]) bag.add(val[u], -1);
val[u] ^= v;
if (active[u]) bag.add(val[u], +1);
}
};
int L = 1, R = 0;
for (const Query &qq : queries) {
while (L > qq.l) addVertex(--L);
while (R < qq.r) addVertex(++R);
while (L < qq.l) removeVertex(L++);
while (R > qq.r) removeVertex(R--);
ans[qq.id] = bag.kth(qq.k);
}
for (int x : ans) cout << x << '\n';
}
return 0;
}