PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
2870
PREREQUISITES:
PROBLEM:
You have an array A. Process Q independent queries of the following type:
- Given u and x, set A_u = x. Then, compute the maximum possible value of
across all 1 \leq i \lt N.
EXPLANATION:
The given expression is a bit weird, so let’s try to simplify it a bit.
For a fixed i, let x = A_1 \oplus \ldots \oplus A_i and y = A_{i+1} \oplus \ldots \oplus A_N.
Our expression is (x\mid y) - (x \&\neg y). This simply equals y.
Proof
First, it’s clear that (x \& \neg y) is a submask of x\mid y (since it’s a submask of x), so the subtraction operation is really just bitwise xor.
Now that we have a bunch of bitwise operations, we can look at bits one by one; in other words it’s enough to look at what happens when x and y take the values 0 and 1.
Simple case analysis tells us that:
- x = 0 and y = 0 evaluates to 0
- x = 0 and y = 1 evaluates to 1
- x = 1 and y = 0 evaluates to 0
- x = 1 and y = 1 evaluates to 1
You’ll notice the result is simply y.
So, the answer for a fixed array is the maximum value of A_{i+1} \oplus \ldots \oplus A_N across all 1 \leq i \lt N, i.e, the maximum suffix xor of the array (except A_1 \oplus \ldots \oplus A_N).
That is, if B_i = A_i \oplus \ldots \oplus A_N, then the answer is \max(B_2, B_3, \ldots, B_N).
Processing updates
Now we need to process updates on A. Let’s see how setting A_u := x changes the answer.
Suppose y is the original value of A_u. Then,
- For any i \gt u, B_i remains unchanged.
- For every i \leq u, B_i changes to B_i \oplus x \oplus y
- In particular, if we set k = x \oplus y, then B_i changes to B_i \oplus k.
So, the answer is the maximum of two quantities:
-
\max(B_{u+1}, B_{u+2}, \ldots, B_N)
- This is simply a suffix maximum of the B array and can be precomputed.
- \max(B_2\oplus k, B_3\oplus k, \ldots, B_u\oplus k)
Computing the second part is a rather standard exercise using tries (if you don’t know what these are, a tutorial is linked at the start), and can be done in \mathcal{O}(b) where b is the number of bits in the numbers we’re dealing with (here, b = 30).
However, this requires us to insert B_2, \ldots, B_u into the trie and nothing else, and u changes every query. Continually erasing and reinserting elements would obviously be too expensive.
The simplest way to overcome this is to solve the queries offline.
That is, read all the queries, then we’ll process them in increasing order of u.
Let T be a trie, initially empty. Iterate over u from 2 to N.
When at a position u,
- Insert B_u into T
- Then, for each query (u, x), query the trie for the maximum value when xor-ed with y\oplus A_u.
This gives us a solution in \mathcal{O}((N+Q)\cdot b), where b = 30 for this task.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\cdot b) per testcase.
CODE:
Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int n,q;
int a[N],XOR[N],MX[N],ans[N];
vector<pair<int,int> >query[N];
struct nod
{
nod *ch[2];
};
struct Trie
{
nod *root;
Trie()
{
root=NULL;
}
void newnod(nod **p)
{
*p=new nod;
(*p)->ch[0]=(*p)->ch[1]=NULL;
}
void insert(int x)
{
_insert(&root,x,29);
}
void _insert(nod **p,int x,int b)
{
if(*p==NULL) newnod(p);
if(b==-1) return ;
_insert(&(*p)->ch[(x&(1<<b))!=0],x,b-1);
}
int getmx(int x)
{
return _getmx(root,x,29,0);
}
int _getmx(nod *p,int x,int b,int cur)
{
if(b==-1) return cur;
int t=(x&(1<<b))!=0;
if(p->ch[t^1]) return _getmx(p->ch[t^1],x,b-1,cur+(1<<b));
else return _getmx(p->ch[t],x,b-1,cur);
}
};
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i;i--) XOR[i]=XOR[i+1]^a[i],MX[i]=max(XOR[i],MX[i+1]);
for(int i=1;i<=q;i++)
{
int p,x;
scanf("%d%d",&p,&x);
ans[i]=MX[p+1];
query[p-1].push_back(make_pair(XOR[1]^a[p]^x,i));
}
int t=0;
Trie T;
for(int i=1;i<n;i++)
{
t^=a[i];
T.insert(t);
for(int j=0;j<query[i].size();j++)
{
int x=query[i][j].first,id=query[i][j].second;
ans[id]=max(ans[id],T.getmx(x));
}
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Trie {
vector<int> v;
vector<array<int, 2>> ch;
int id = 0;
Trie() : v(1, 0), ch(1, {-1, -1}) {}
void create() {
v.push_back(0);
ch.push_back({-1, -1});
++id;
}
void add(int x) {
int node = 0;
for (int bit = 30; bit >= 0; --bit) {
int b = (x >> bit) & 1;
++v[node];
if (ch[node][b] == -1) {
create();
ch[node][b] = id;
}
node = ch[node][b];
}
++v[node];
}
int query (int x) { // Maximum value of a^x for a in the trie
int node = 0, ret = 0;
for (int bit = 30; bit >= 0; --bit) {
int b = (x >> bit) & 1;
if (ch[node][b^1] == -1) node = ch[node][b];
else {
ret += 1 << bit;
node = ch[node][b^1];
}
}
return ret;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> suf(n), sufmax(n+1);
for (int i = n-1; i >= 0; --i) {
suf[i] = a[i];
if (i < n-1) suf[i] ^= suf[i+1];
sufmax[i] = suf[i];
if (i < n-1) sufmax[i] = max(sufmax[i], sufmax[i+1]);
}
vector<vector<array<int, 2>>> queries(n);
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int pos, val; cin >> pos >> val;
queries[--pos].push_back({val, i});
ans[i] = sufmax[pos+1];
}
Trie T;
for (int i = 1; i < n; ++i) {
T.add(suf[i]);
for (auto [val, id] : queries[i]) {
ans[id] = max(ans[id], T.query(val ^ a[i]));
}
}
for (auto x : ans) cout << x << '\n';
}
,they usually set some very nice adhocish algorithmic problems. Waiting for next starters 
.