Solved it online just using Segment tree and handy observation that 0,1, and any 2^(2*k) give square number after AND with any number. See solution: https://www.codechef.com/viewsolution/20031934
A bit tricky combine function, but nothing special…
I think this blog is currently the best explanation of Hilbert’s order for Mo’s algorithm, which can be used to solve this problem. Although it was not the expected solution, I think it is a great improvement of Mo’s algorithm, which can be used in many problems.
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.
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
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-
The AND sum of, assume any K, can change at most LogN times before reaching 0. Check the proof in bonus section for why part.
the value N at the start of the range has LogN bits, at most LogN set ({=}1). AND with subsequent values will only reset bits (\to 0), never set them.
Thanks a lot dear. A lot of time goes into writing this (which is partly the reason I couldnt complete selina, factorize and lost story in time.). This editorial, counting time needed for observing contestant’s solution, decoding algos used and finally writing the editorial took 8.5 hours roughly XD.
3 Likes
Thanks dear <33333333333
…agree 
It should be N log (max(A[i])) instead of N log N.
Aah, yup XD. My bad.
me too…
An alternative sorting order for Mo's algorithm - Codeforces - here is it, an improvement of Mo’s algorithm
*Hilbert order
1 Like
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.
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.