PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums
PROBLEM:
An array is called good if its prefix XORs are non-decreasing.
You’re given an array A of length N. Answer Q queries on it: each query gives you a subarray, and you must report whether it’s good or not.
EXPLANATION:
Let’s try to compute the answer for a single subarray [L, R].
Define B_i := A_L \oplus A_{L+1} \oplus \cdots \oplus A_{i}, so that B becomes the prefix XOR array of this subarray (note that indexing of B starts from L).
We want B_i \leq B_{i+1} to hold.
Note that each element of B is a subarray XOR of A, so we can rewrite it in terms of the prefix XORs of A.
Let P denote the prefix XOR array of A, so that P_i := A_1 \oplus A_{2} \oplus \cdots \oplus A_{i}.
With this, we obtain B_i = P_{i} \oplus P_{L-1}.
So, what we want to check is whether P_i\oplus P_{L-1} \leq P_{i+1} \oplus P_{L-1} for each L \leq i \lt R.
Analyzing this in binary, it means that at the highest bit where P_i\oplus P_{L-1} and P_{i+1} \oplus P_{L-1} differ, the bit must be set in P_{i+1} \oplus P_{L-1}.
Now, both sides are XOR-ed by P_{L-1}.
So, the highest bit where P_i\oplus P_{L-1} and P_{i+1}\oplus P_{L-1} differ, is also the highest bit where P_i and P_{i+1} differ!
Now, let b be the highest bit where P_i and P_{i+1} differ.
Then,
- If P_i has it set but P_{i+1} does not, then P_i\oplus P_{L-1} \leq P_{i+1} \oplus P_{L-1} is possible if and only if P_{L-1} has the bit set.
- Conversely, if P_i has it unset but P_{i+1} has it set, P_i\oplus P_{L-1} \leq P_{i+1} \oplus P_{L-1} is possible if and only if P_{L-1} has the bit unset.
This gives us a condition on each adjacent pair of indices of the array, where each condition is either of the form “bit b must be set in P_{L-1}”, or “bit b must be unset in P_{L-1}”.
These conditions can be precomputed for every index, since they’re independent of the queries.
Let’s now return to answering a query.
Fix a bit b. Then,
- If both “b must be set in P_{L-1}” and “b must be unset in P_{L-1}” are present as conditions in the subarray, it’s clearly impossible to satisfy both, so the subarray is not good.
- If only one type of condition is present, check if P_{L-1} satisfies it.
- If both types are absent then this bit isn’t going to affect sortedness so it can be safely skipped.
All that’s left is actually checking, for a fixed bit b, which conditions exist within the queried subarray.
This can be done quickly in various ways. A simple one is to note that there are only 60 types of conditions (two for each bit), so you can simply precompute the next occurrence of each type from every index, and then just look these up.
This takes \mathcal{O}(N\log\max(A)) precomputation and \mathcal{O}(1) per bit per query so it’s quite fast.
There are other approaches too - instead of looking at each bit separately, all their results can be accumulated with bitwise OR so one way is to use a data structure that supports range OR queries (which can be seen in the editorialist’s code below).
TIME COMPLEXITY:
\mathcal{O}(N\log \max(A)) or \mathcal{O}(N\log N) precomputation, and \mathcal{O}(\log\max(A)) or \mathcal{O}(1) time per query.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, q; cin >> n >> q;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
vector<vector<array<int, 2>>> constrain(31, vector<array<int, 2>>(n + 1));
vector<vector<int>> ps(31, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++){
int b = 0;
while (a[i] >= (1 << (b + 1))) ++b;
for (int j = 0; j <= 30; j++){
constrain[j][i] = constrain[j][i - 1];
ps[j][i] = ps[j][i - 1] + (a[i] >> j & 1);
}
if (a[i] == 0){
continue;
}
int v = ps[b][i];
constrain[b][i][v % 2]++;
}
vector <int> p(n + 1, 0);
for (int i = 1; i <= n; i++){
p[i] = p[i - 1] ^ a[i];
}
while (q--){
int l, r; cin >> l >> r;
bool good = true;
for (int j = 0; j <= 30; j++){
int g0 = constrain[j][r][0] - constrain[j][l - 1][0];
int g1 = constrain[j][r][1] - constrain[j][l - 1][1];
if (g0 > 0 && g1 > 0){
good = false;
}
if (g0 > 0 && !(p[l - 1] >> j & 1)){
good = false;
}
if (g1 > 0 && (p[l - 1] >> j & 1)){
good = false;
}
}
if (good) cout << "1";
else cout << "0";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n,q; cin >> n >> q;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<pll> queries(q+5);
rep1(i,q){
ll l,r; cin >> l >> r;
queries[i] = {l,r};
}
vector<ll> msb(n+5,-1);
rep1(i,n){
if(a[i]){
msb[i] = 63-__builtin_clzll(a[i]);
}
}
vector<pll> here[n+5];
rep1(i,q) here[queries[i].ff].pb({queries[i].ss,i});
vector<ll> ans(q+5,1);
rep(bit,30){
ll first_zero = n+1, first_one = n+1;
rev(i,n,1){
if(a[i]&(1<<bit)){
swap(first_zero,first_one);
}
if(msb[i] == bit){
first_zero = i;
}
for(auto [r,id] : here[i]){
if(first_one <= r){
ans[id] = 0;
}
}
}
}
rep1(i,q) cout << ans[i];
cout << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
class RangeQuery:
def __init__(self, data, func=min):
self.func = func
self._data = _data = [list(data)]
i, n = 1, len(_data[0])
while 2 * i <= n:
prev = _data[-1]
_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
i <<= 1
def query(self, start, stop):
"""func of data[start, stop)"""
depth = (stop - start).bit_length() - 1
return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])
def __getitem__(self, idx):
return self._data[0][idx]
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for x in a: p.append(x ^ p[-1])
yes, no = [0]*(n+1), [0]*(n+1)
for i in range(1, n):
x = p[i] ^ p[i+1]
if x == 0: continue
msb = x.bit_length() - 1
if p[i] & 2**msb: yes[i] = 2**msb
else: no[i] = 2**msb
s1 = RangeQuery(yes, lambda x, y: x|y)
s2 = RangeQuery(no, lambda x, y: x|y)
ans = []
for i in range(q):
l, r = map(int, input().split())
if l == r:
ans.append(1)
continue
x, y = s1.query(l, r), s2.query(l, r)
if x & y or (x & p[l-1]) != x or (y & p[l-1]): ans.append(0)
else: ans.append(1)
print(''.join(map(str, ans)))