Ciallo codeforces! In today's div3 I was not able to solve G :( So now I am writing a solution for people who don't know how to solve G.
Let's consider the nature of the problem:
If the subarray $$$a_{[l,r]}$$$ is beautiful, then both $$$a_{[l-1,r]}$$$ and $$$a_{[l,r+1]}$$$ are also beautiful.
If the subarray $$$a_{[l,r]}$$$ is not beautiful, then both $$$a_{[l+1,r]}$$$ and $$$a_{[l,r-1]}$$$ are also not beautiful.
This insight suggests using the two-pointer technique to maintain the answer. The problem then reduces to determining whether, within the interval $$$[l, r]$$$, there exists a pair of indices $$$l \le i \le j \le r$$$ such that $$$a_i \oplus a_j \ge k$$$ (which is exactly the problem discussed in this blog post).
That problem isn’t trivial to maintain (or maybe I just don’t know how yet, haha), but it does exhibit some elegant properties: during the two-pointer process, we only move the pointers $$$l$$$ and $$$r$$$ to the right.
When moving $$$r$$$ to the right, we know that the interval $$$[l, r-1]$$$ does not contain any pair of indices $$$l \le i \le j \le r-1$$$ such that $$$a_i \oplus a_j \ge k$$$. Therefore, if the interval $$$[l,r]$$$ satisfies the condition, there must exist some $$$l \le i \le r$$$ such that $$$a_i \oplus a_r \ge k$$$. This problem becomes simple: just find the element in the current Trie that maximizes the XOR with $$$a_r$$$.
When moving $$$l$$$ to the right, we can consider backtracking to the point when $$$r$$$ was last moved to the right (it can be proven that such a point always exists). At that time, the interval $$$[l', r-1]$$$ did not contain any pair $$$l' \le i \le j \le r$$$ such that $$$a_i \oplus a_j \ge k$$$, but there existed some $$$l \le i \le r$$$ such that $$$a_i \oplus a_r \ge k$$$. Therefore, as the pointer $$$l$$$ moves to the right, we only need to remove the contribution of $$$a_l$$$ from the Trie and compute the current maximum XOR with $$$a_r$$$ in the Trie.
The time complexity of this algorithm is $$$O(n \log V)$$$, and it can be solved using this approach.
Code(LANG = C++)
#pragma GCC optimize(3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100;
struct Node{
int son[2],cnt;
Node(){cnt=son[0]=son[1]=0;}
}tree[N<<5];
int idx;
void ins(int x,int v){
int now=0;tree[0].cnt+=v;
for(int i=29;~i;--i){
if(!tree[now].son[x>>i&1])tree[now].son[x>>i&1]=++idx;
now=tree[now].son[x>>i&1];
tree[now].cnt+=v;
}
}
int query(int x){
int now=0,val=0;
for(int i=29;~i;--i){
if(tree[now].son[~x>>i&1]&&tree[tree[now].son[~x>>i&1]].cnt)now=tree[now].son[~x>>i&1],val|=(1<<i);
else now=tree[now].son[x>>i&1];
}
return val;
}
int a[N];
signed main(){
int T;cin>>T;
while(T--){
for(int i=0;i<=idx+1;++i)tree[i]=Node();
idx=0;
int n,k;cin>>n>>k;
for(int i=1;i<=n;++i)cin>>a[i];
int l=1,r=1,mi=1e18;
while(l<=n&&r<=n){
ins(a[r++],1);
while(l<r&&query(a[r-1])>=k)mi=min(mi,r-l),ins(a[l++],-1);
}
if(mi>1e17)mi=-1;
cout<<mi<<'\n';
}
}
Submission.
