Benny and Queries
Benny and Queries
Probably, you have already read some problems but you still have not met any problems with queries on segments. Therefore Benny wants to fix it.
She gives you an array A of N elements. And then you have to answer Q queries.
Each query consists of three integers L, R, X. Your task is to find such Ai, that L ≤ i ≤ R and Ai xor X is maximal. For each query output the maximum of Ai xor X.
Input format
The first line contains two integers N and Q. The next line contains N integers Ai. The next Q lines contain three integersL, R, X.
Output format
For each query output the maximum of Ai xor X in a single line.
Constraints
- 1 ≤ N, Q ≤ 5 * 105
- 0 ≤ Ai < 220
- 1 ≤ L ≤ R ≤ N
- 0 ≤ X < 220
- 1 ≤ N, Q ≤ 3 * 103 holds for test cases worth 15% of the problem's score.
- 1 ≤ N, Q ≤ 105 holds for test cases worth 60% of the pro
- 1 ≤ N, Q ≤ 105 holds for test cases worth 60% of the problem's score.
- INPUT
5 3 1 7 3 8 2 1 5 10 3 4 6 2 5 8
OUTPUT
13 14 15
----------------------------------------EDITORIAL-------------------------------------------------------------------------- ON EACH NODE OF TRIE KEEP A SET BUT IT WILL GIVE TLE , BUT AS WE ARE INSERTING INDEX IN INCREASING ORDER OF INDEX SO WE CAN USE VECTOR ON EACH NODE ALSO ....
- How to solve this problem if l = 1 and r = n in all queries? We can consider every number as binary string of length 20. For example, 47 equals 00000000000000101111. Let's build a trie on all this strings. You can read about trie here orhere. How can we answer a query when? Let's find the same binary string of X. Now the largest bit of X xor Ai will be 1 iff the largest bit of X differs from the largest bit of Ai. So we can check if there exist an edge from the root with label equals to opposite of the largest bit of X. Then we can try next bit and so on.Now we have queries with l and r. Let's keep in every node of the trie a sorted array of indices of all number that passes through this node. When we want to check if there exist a number with given prefix and index in range [l, r] we need to binary search it in sorted array of appropriate node.Complexity of such solution will be O(n log2n).Also this problem can be solved with segment tree of tries or persistent trie.You can check solutions by setter and tester for implementation details.
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
void calc(int val[])
{
val[0]=1;
for(int i=1;i<=31;i++)
{
val[i]=val[i-1]*2;
}
// cout<<" generation done "<<endl;
return;
}
class node
{
public:
node * ll,*rr;
vector<int> s;
node()
{
ll=NULL;
rr=NULL;
}
};
int join(node * head,int val[],int num,int index)
{
node *var=head;
for(int i=21;i>=0;i--)
{
if(num&val[i])
{
if(head->rr!=NULL)
{
// cout<<" join existing "<<endl;
head=head->rr;
// cout<<" ins "<<index<<endl;
head->s.push_back(index);
}
else
{
// cout<<" create"<<endl;
head->rr= new node();
head=head->rr;
// cout<<" ins "<<index<<endl;
head->s.push_back(index);
}
}
else
{
// cout<<" off "<<endl;
// int f=0;
if(head->ll!=NULL)
{
// cout<<"join "<<endl;
head=head->ll;
// cout<<" ins "<<index<<endl;
head->s.push_back(index);
}
else
{
// cout<<" create "<<endl;
head->ll= new node();
head=head->ll;
// cout<<" ins "<<index<<endl;
head->s.push_back(index);
}
}
}
}
int find(node * head,int v[],int l,int r,int num)
{
//cout<<" find for "<<num<<" in "<<l<<" "<<r<<endl;
node *var=head;
int ans=0;
for(int i=21;i>=0;i--)
{
if(!(num&v[i]))
{
//cout<<" at index "<<i<<" need "<<1<<endl;
int f=0;
if(head->rr!=NULL)
{
var=head->rr;
vector<int>:: iterator it1,it2;
it1=lower_bound(var->s.begin(),var->s.end(),l);
it2=lower_bound(var->s.begin(),var->s.end(),r+1);
// if(it!=var->s.end() && *it1>r) it1--;
it2--;
if(it1!=var->s.end() && *it1<=r && *it1>=l && *it2<=r && *it2>=l)
{
// cout<<" yah fine "<<endl;
ans=ans|v[i];
// cout<<ans<<endl;
head=head->rr;
f=1;
}
}
if(f==0)
{
// cout<<" no "<<endl;
head=head->ll;
}
}
else
{
// cout<<" at index "<<i<<" need "<<0<<endl;
int f=0;
if(head->ll!=NULL)
{
var=head->ll;
vector<int>:: iterator it1,it2;
it1=lower_bound(var->s.begin(),var->s.end(),l);
it2=lower_bound(var->s.begin(),var->s.end(),r+1);
it2--;
if(it1!=var->s.end() && *it1<=r && *it1>=l && *it2<=r && *it2>=l)
{
// cout<<" yah fine "<<endl;
ans=ans|v[i];
// cout<<ans<<endl;
head=head->ll;
f=1;
}
}
if(f==0)
{
//cout<<" no "<<endl;
head=head->rr;
}
}
}
return ans;
}
int main()
{
int n,q;
cin>>n>>q;
int arr[n+10];
int val[100];
calc(val);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
node *head1=new node();
for(int i=0;i<n;i++)
{
join(head1,val,arr[i],i+1);
}
for(int i=0;i<q;i++)
{
int px,py,x;
scanf("%d %d %d",&px,&py,&x);
int ans=find(head1,val,px,py,x);
cout<<ans<<endl;
}
}
