PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yahor Dubovik
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
3087
PREREQUISITES:
XOR
PROBLEM:
You are given an array A, consisting of N integers and Q queries. Each query is of the type:
- L R: Given L and R, (1 \le L < R \le N), your task is to output minimum XOR of any two elements from the subarray A[L, R] of array A.
More formally, for each query L, R, your task is to calculate minimum value of A_i \oplus A_j over L \le i < j \le R, where \oplus denotes bitwise XOR.
EXPLANATION:
One possible way to do this problem is to first sort the queries by increasing R. We then loop through each pair (A_l, A_r) by increasing r, each time updating the answer for queries spanning the segment [l, r], then finally find the answer for queries with R = r. Obviously, this method is super slow (since there are O(N^2) such pairs (A_l, A_r)), but what if we can reduce the number of pairs by only picking out “important pairs” to update?
Suppose we have the pair (A_l, A_r), and we take its xor to be X. Suppose again that X's largest bit is P. This means the most significant 30 - P bits of A_l and A_r are the same. We have this following observation:
- If between A_l and A_r, there exists another element A_m with the same first 30 - P bits, then (A_l, A_r) is a useless pair. This is because P-th bit of A_l and A_r is different, which means the P-th bit of A_m equals to either one of A_l's or A_r's, which means either (A_l, A_m) or (A_m, A_r) is strictly better (both in range and value) to (A_l, A_r).
This observation immediately cuts down the number of important pairs. We loop over the number of bits X, we categorize the elements of A_i into buckets, where in each bucket are the elements with the same first X bits. The important pairs are then the adjacent elements in each bucket. This generates O(N \log \max(A)) pairs (since each bit loop we add at most N pairs). The problem can be then solved easily with the help with a Fenwick tree: Loop over the endpoint r. For each such endpoint, we first get all candidate pairs (A_l, A_r), then update the answer in the range [1, l] to be at most A_l \oplus A_r. After that, loop over the queries L, R such that R = r, then simply get the answer at position L.
TIME COMPLEXITY:
Time complexity is O(N \log N \log \max(A)).
SOLUTION:
Setter's Solution
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 2e5 + 10;
int n, q;
int a[maxN];
int l[maxN], r[maxN];
int ans[maxN];
vector<int> query[maxN];
vector<pair<int,int>> upd[maxN];
int fenw[maxN];
void do_upd(int v, int by) {
while (v <= n) {
fenw[v] = min(fenw[v], by);
v = (v | (v - 1)) + 1;
}
}
int do_get(int r) {
int mn = (1 << 30);
while (r > 0) {
mn = min(mn, fenw[r]);
r &= (r - 1);
}
return mn;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
ans[i] = (1 << 30);
query[r[i]].emplace_back(i);
}
//x0000
//
for (int bit = 30; bit >= 0; bit--) {
vector<pair<int,int>> all;
for (int i = 1; i <= n; i++) {
int f = (a[i] >> bit) << bit;
all.emplace_back(f, i);
}
sort(all.begin(), all.end());
for (int it = 0; it + 1 < all.size(); it++) {
if (all[it].first == all[it + 1].first) {
int D = a[all[it].second] ^ a[all[it + 1].second];
upd[all[it + 1].second].emplace_back(all[it].second, D);
}
}
}
for (int i = 0; i <= n; i++) {
fenw[i] = (1 << 30);
}
//n + 1 - l[it] >= n + 1 - it
for (int i = 1; i <= n; i++) {
for (auto& it : upd[i]) {
do_upd(n + 1 - it.first, it.second);
}
for (auto& it : query[i]) {
ans[it] = do_get(n + 1 - l[it]);
}
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+1;
const int iu=30;
ll a[N];
pair<ll,int>b[N];
int n,q;
vector<int>fr[N];
vector<pair<int,int> >qr[N];
int bit[N];
int ans[N];
void upd(int id,int v){
for(int i=id; i<=n ;i+=i&-i) bit[i]=min(bit[i],v);
}
int qry(int id){
int res=1<<iu;
for(int i=id; i>=1 ;i-=i&-i) res=min(res,bit[i]);
return res;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> q;
for(int i=1; i<=n ;i++) cin >> a[i];
for(int i=iu; i>=0 ;i--){
for(int j=1; j<=n ;j++){
b[j].fi=a[j]&((1<<iu)-(1<<i));b[j].se=j;
}
sort(b+1,b+n+1);
for(int i=1; i<n ;i++){
if(b[i].se<b[i+1].se) fr[b[i].se].push_back(b[i+1].se);
}
}
for(int i=1; i<=n ;i++) bit[i]=(1<<iu)-1;
for(int i=1; i<=q ;i++){
int l,r;cin >> l >> r;
qr[l].push_back({r,i});
}
for(int i=n; i>=1 ;i--){
for(auto c:fr[i]){
upd(c,a[i]^a[c]);
}
for(auto c:qr[i]){
ans[c.se]=qry(c.fi);
}
}
for(int i=1; i<=q ;i++) cout << ans[i] << '\n';
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
struct fenwick_tree {
vector<int> bit;
int n;
fenwick_tree(int _n) : n(_n) {
bit.resize(n + 1, numeric_limits<int>::max());
}
void update(int u, int v) {
for (u++; u > 0; u -= u & -u) {
bit[u] = min(bit[u], v);
}
}
int query(int u) {
int ans = numeric_limits<int>::max();
for (u++; u <= n; u += u & -u) {
ans = min(ans, bit[u]);
}
return ans;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> a(n);
vector<vector<int>> lst(n);
vector<vector<pair<int, int>>> que(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int b = 0; b <= 30; b++) {
vector<pair<int, int>> pref;
for (int i = 0; i < n; i++) {
pref.push_back({a[i] >> b, i});
}
sort(pref.begin(), pref.end());
for (int i = 1; i < n; i++) {
if (pref[i].first == pref[i - 1].first) {
lst[pref[i].second].push_back(pref[i - 1].second);
}
}
}
vector<int> ans(q);
for (int i = 0; i < q; i++) {
int l, r; cin >> l >> r; l--; r--;
que[r].push_back({l, i});
}
fenwick_tree fen(n);
for (int i = 0; i < n; i++) {
for (int v : lst[i]) {
fen.update(v, a[v] ^ a[i]);
}
for (auto [l, ind] : que[i]) {
ans[ind] = fen.query(l);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}