PROBLEM LINK:Setter ShavelV DIFFICULTY:MEDIUM PREREQUISITES:Fenwick Tree supporting range updates and range query, or segment tree with lazy propagation, Properties of AND, Observations PROBLEM:Given an array $A$, answer $Q$ queries which ask the number of subsequences in range $[L,R]$ whose bitwise AND is a perfect square. QUICKEXPLANATION:Key to AC AND of numbers can change no more than $LogN$ time, and hence there are at most $O(NLogN)$ different values possible. It is hence possible to update answer over a group or range, which can be done via segment tree or fenwick tree. Notice that there are at most $O(NLogN)$ values of AND possible in total. Now, either of the $2$ approaches are possible
EXPLANATION:The editorial will focus on one of the $2$ solutions, and that will be the most popular solution used by the participants  simply because the solution is pretty crisp and simple :). Setter's solution has been very briefly described in quick explanation, and setter's notes will be provided for people interested in his approach. His solution has been made commented so things are clear. We will discuss only one because difference between both solutions isnt very much, except for the fact that the participant's solution is quite intuitive and easy to understand :) As usual, answers to all the (Why?)'s and proofs will be given in my corner  along with extra resources and related problems. Lets run through first subtask quickly. Sine $N \le 100$, you could brute force. Take the range $[l,r]$ in input, and then iterate over all subarrays in this range, i.e. over all $i$ from $l$ to $r$ as starting point of subarray, and for each starting point, over $j$ from $i$ to $r$ as ending point of the subarray. If the AND of the subarray satisfies the condition, increment the answer by $1$. This works in $O(Q*N^2)$. Lets move over to the meaty party now :D Most Popular Solution Let me break this into 3 parts  Intuition, Preprocessing, and answering Queries. 1. Intuition This solution uses the observation that the AND value can change at most $LogN$ times. (Why? P1). It is easy to see that AND is a nonincreasing function. If we AND the current ANDsum received so far (of the subarray) with next element, it will either remain constant or decrease. We know that it can decrease only at most $Log_2N$ times, and if it remains constant, then we can do range operations on the group as a whole instead of doing it individually. This was the intuition a participant can pick up to at least gain a direction of how to solve this problem. 2. PreProcessing  Now, moving on the the most popular question, how to solve this problem :). Since total number of AND values are $NLog_2N$, we can make a $2D$ array to store the positions of (atmost) $Log_2N$ distinct values of AND for all subarrays starting from index $i$. In other words, array $P[i][j]$ will store the location of $j'th$ change in AND sum for subarrays beginning at index $i$. One of the ways by which many contestants and red coders did it was, by checking the location when the $j'th$ bit changed. If $j'th$ bit remains constant, then we are assured that at least that bit wont change during AND, else if that bit changes, then we found a location where the AND is changing. The location closest to $i$ among all the bits will be the location upto which this group has same AND. There are multiple implementations possible, but for sake of completeness I have given this above described implementation in tab below for those who arent able to come up with the implementations. 3. Querying Do yourself a favor and sort the queries. So MANY contestants underestimate this! Sort the queries on basis of their beginning and/or ending points. If you want to measure how effective it can be, it can change "iterating over the array every time we have to answer a query" to "iterating once to answer all queries collectively." This step is the heart of square root decomposition and Mo's algorithm's. Now, look at what we have in preprocessed array. We have positions of next change of AND. This means we can quickly jump forward over groups in array. What does this mean? It means if we iterate backwards, from $N1$ to $0$ (0based indexing), then for every index we have to do calculations for at most $Log_2N$ groups ahead of it. Good! Keep a main pointer pointing at end of array, or in simpler words, iterate from $i=N1$ to $0$ now :p. Now, since AND of one element is that element itself, initialize current AND (say currand) as $A_i$ and starting position of this AND (say, st) as $st=i$. Now, use the preprocessed array to directly jump to the beginning of next group, and find new value of currand. If this AND value satisfies the condition, then we do a increment by 1 the values in range $[st,ed]$ where we define $ed$ as ending point of the old group. Update the values of currand, and set st to point at starting element of new group as this is where the new currand begins. Once main pointer arrives at the beginning point, or $l$ value of current query, its time to answer it! To get the solution for a query, we simply find sum of range $[L,R]$ given in query. As simple as it is! Now, how do we do it? We can use segment tree with lazypropagation. But I want you guys to explore another data structure, fenwick tree. Initially my plan was to make this editorial like my other segment tree ones, telling parent child relation, what to store in node and other stuff, but this time I decided to simply describe the idea and leave the how part to you guys. Almost all the good coders used Fenwick tree. BIT, or Fenwick tree, can be at least $4$ times faster than and efficient than segment tree, both in terms of memory and speed. The best part is, which allowed me to leave this part for you guys, is that the operation involved is simply standard range update and range query operation with almost no twist. Nothing can be a better chance to explore and master a data structure than this. I have searched thoroughly to get the bestest resources for you guys to see and hence implement and see the data structure yourself, so buckle up! A wind of change is blowing :). A minor spoiler for the process We maintain $2$ fenwick trees, and use updating concept similar to difference array. Like, in difference array, to update the range $[L,R]$ by $K$, we did $A[L]+=K$ and $A[R+1]=K$. Similarly we will break our query of updating in range $[L,R]$ into $2$ parts and execute it. Also, a term "linear" function will be involved at the tutorials, dont let it get to you, its just simple stuff like $(ab)x=axbx$. You'll see this yourself when you read the tutorials :) Now, do you think you get the idea? If yes, then answer this What does our update represent? (in case your ans was no, hop on to my corner to understand this! :D) Another interesting question, we see that we are updating in range of the group. How does it prevent overcounting, or counting only subarrays inside range $[L,R]$? As in, say my array is $[2,2,1,1]$. I will do an update on range $[3,4]$ (1based indexing) for $1$ at index $2$ and then another update over same range for $1$ at index $1$. If I give query $[2,4]$, how will the above algorithm give correct answer? Refer to the code in tab below and then to the explanation SOLUTIONThe solutions are pasted here for your convenience in case the links arent activated by @admin yet :) Editorialist will be put on demand. But till then, take this solution for reference. Shoutout to @abdullah768 for being a good boi writing clean codes :) $Time$ $Complexity=O(QLogN+N*LogA *LogN)$ (setter's solution) CHEF VIJJU'S CORNER :D1. Why AND changes at most $Log_2N$ times? 2. What does update over the range represent? 3. How does the above algo not count subarrays outside the range if its simple sum 4. Setter's Notes 5. Resources 6 Hall of fame for Noteworthy Solutions
7. Related Problems
This question is marked "community wiki".
asked 16 Sep '18, 01:00

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... answered 18 Sep '18, 21:31

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. answered 18 Sep '18, 22:39

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. answered 21 Sep '18, 12:33

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. answered 01 Oct '18, 20:23

Can someone please post some reference to Gilbert's Order. Can't find it anywhere. answered 18 Sep '18, 01:34
http://codeforces.com/blog/entry/61203  here is it, an improvement of Mo's algorithm
(19 Sep '18, 12:38)
1
*Hilbert order
(19 Sep '18, 20:43)

What are the groups here exactly refer to, this is where I am getting stuck. The pre processing part is nice and I also get how 'st' is changing but stuck with 'ed'. What is initial value of 'ed' and it would be great if anyone here can explain this with an example. answered 18 Sep '18, 14:54

Groups in setter's solution is a collection of subarrays with same AND. Stuck at ed? Even after reading notes 2 and 3 in my bonus corner? $ed$ starts from end of current group, like $st$ at start of this group. $ed's$ next value will be end of next group. Group, beginning at $i$ and ending at $j$, here refers to subarray whose AND sum doesnt change in range $[i,j]$. When I say AND sum in range $[i,j]$ , take andsum at $[i,i]$ to be $A_i$ and make sure it doesnt change till we reach $j$. Consider subarrays beginning at $i$ where $i$ goes from $[N1,0]$. Now, of course, since we are considering subarrays beginning at current $i$, then by the time we reach $st$ our current ANDSUM would be $(A_i,..,A_{st1})$. AND sum of the entire group of $[st,ed]$ doesnt change anywhere in between $st$ and $ed$. One such case is if the group comprises of same elements. Now, take AND sum of group and current AND sum. If it satisfies condition, then it means, "For subarrays beginning at $i$, we have suitable endpoints in range $[st,ed]$." Increment values in that range to denote that "We found $1$ more index $i$ such that AND sum of subarray from $i$ to $[st,ed]$ satisfy our condition." If its still unclear, refer to code and work it out! Thats the best way :) answered 18 Sep '18, 18:57

if anyone can tell what is wrong with my solution i have followed editorial ://www.codechef.com/viewsolution/20230890 answered 18 Sep '18, 20:27

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 answered 21 Nov '18, 11:12

It should be N log (max(A[i])) instead of N log N.
Aah, yup XD. My bad.