*Hilbert order
1 Like
If in this question we were having xor instead of and operation then also we can use the fenwick tree approach or we need to use MO algo then?
As most of the time i am bit confused that BIT can be used only if we have to perform the inverse operations so if we have xor in place of and can we use BIT approach.
Here you should apply the concept. Fenwick tree was used only for a simple range update. The concept of AND was used in preprocessing part. That thing sadly doesnt hold for XOR, so the preprocessing part fails for XOR, but if you can come up with something for that, then fenwick tree can be used in next step.
what does the editor mean my constant bit in pre-processing part.
if the and j th bit is 0 then why and is changing .itās all messy and why initialaizing with n+1
LL fsu[31][N];
for(i=0;i<31;i++)//Initialize
fsu[i][n]=n+1;
for(i=n-1;i>=1;i--)
{
for(j=0;j<31;j++)
{
if((1<<j)&a[i+1])//If the bit is set
fsu[j][i]=fsu[j][i+1];
else //If the bit changes
fsu[j][i]=i+1;
}
}
somebody explain it bit easier as of level pf beginner
We are interested in places where AND changes. We hence dont care about bits which are 0. And why n+1? Thats depends on implementation and definition you used. This guy used āLet it store beginning of next group w.r.t that bit.ā so it makes sense.
You can look at the model solution shared for full code.
whenever 0 is encounter in any of j th bit then thatās the case when And changes as set bit might get off ; yep it might be case that it might be off before we didnāt need to worry about this case.
Really great question. I didnāt even think of using lazy prop segment trees of fenwick trees. I saw the N \leq 10^5 and the 3 second time limit thought this must be a square root decomposition problem. I was able to get my square root decomposition solution to work after I figured out how to calculate an answer for the query [l,r] using the precomputed answers and additional information about queries [l,x) and [x,r]. Then it was a matter of picking \sqrt{N} special values of x so that either a query will have a small distance (O(\sqrt{N})) between l and r and can be calculated directly or l \leq x and r \geq x for some special value x. I did sort the queries by their l value but is was more to deal with space complexity than time complexity since with sorting you only ever need the store the results of the precomputations for one value of x at a time.
If you still have doubt, remember that in the code snippet given above the setterās and the testerās codes, the ith value in the fenwick tree at any instance tells us the no. of subarrays starting at cl and ending at i which have an AND that is a perfect square.
Notice that there are at most O(N*LogN) values of AND possible in total. Now, either of the 2 approaches are possible-
It should be -
Notice that there are at most O(N*Log(MaxA_i)) values of AND possible in total. Now, either of the 2 approaches are possible-