GEHA1806 - Editorial

editorial
,
1

PROBLEM LINKS:

Practice

Contest

DIFFICULTY:

Medium

PREREQUISITES:

  • Binary search
  • Range queries without any updates (Segment tree/Sparse table/Fenwick Tree/etc.)

PROBLEM:

Given an array A of n integers & m queries.In every query an integer x is given.Let S be the set of all the subarrays Si of array A such that the bitwise and of all elements in Si results to x.Let |Si| represent number of elements in subarray Si.

Your task is to find (\displaystyle\sum_{S_i \in S} \mid S_i \mid) for every query.

EXPECTED COMPLEXITY : 

O(n.logn) / O(n.(logn)2)

DISCUSSED COMPLEXITY : 

O(n.(logn)2)

CORE IDEA BEHIND THE PROBLEM :

Bitwise & of a number x is a non-increasing function & it can change only logx times at most.

EXPLANATION :

Let us solve simpler problem first.What if we only had to deal with prefix subarrays instead of all subarrays?

Let us take a random array a of integers.

a1 a2 a3 a4 ... an
x1=a1 x2=x1&a2 x3=x2&a3 x4=x3&a4 ... xn=xn-1&an

Now,let us take an array x where xi = bitwise & of all elements between index 1 & i. . It is obvious that xi+1<=xi.But the important thing to notice is that if xi+1 < xi ,then the decrement(xi-xi+1) must be sum of powers of 2(some bits of xi which were set(1),now they would be unset(0) in xi+1).

Now,how many distinct xi can we possibly have?

For maximum distinct xi , we can suppose anytime x decreases,it decreases by a single power of 2 (only a single set bit of xi becomes unset in xi+1) & finally xn becomes 0 (zero).So,maximum times value of x can decrease is equal to count of set bits in x1.Hence,we can conclude that value of x can change at most log x1(or say log a1)times.

Let us define a function f(i) which gives bitwise & of all elements between index 1 & i in O(1).

We can observe that f(i) is a non-increasing function i.e.it will either remain same or decrease with increasing i.So,binary search can be used to find i corresponding to some y=f(i). Binary search on a function (geeksforgeeks)

There will be many indice range for which xi will remain same.So,we know xi & we just have to find corresponding i.Suppose we are at index l & value of x is xl. then we could binary search for last index r such that xl=xl+1=…=xr in O(log(n-l+1)).Let us see how.

Let us define some things for ease of understanding:

f(i) : BItwise & of all elements between index 1 & i.

map<int,int> cnt

cnt[i] : how many subarrays have bitwise & value i.

```
int start=i,end=i;
int l=start,r=n;
while(l<=r)
{
	int mid=(l+r)/2;
	if(f(mid)==f(start))
		end=mid,l=mid+1;
	else
		r=mid-1;
}
cnt[f(start)]=(end-start+1);
```




Suppose we that  are at index i.Let us call start=i. To find the right end (the last index end in the array such that f(start)==f(end) ),we use binary search as above.We fix the right end at index i only and start extending it to the right by using binary search on f(i). We take the range [start,n] into consideration and start dividing it further into smaller ranges.Ultimately,we find the rightmost index end such that f(start)==f(end) & no other index j>end exists which satisfies this condition.After finding the right end, we can say that all the subarrays (1,start),(1,start+1),...(1,end) have same bitwise & value which is f(start).Also we can say that (end-start+1) prefix subarrays(subarrays with left end at index 1) exist which have bitwise & value=f(start).So,cnt[f(start)]=(end-start+1).





Now we can extend this solution to find all the distinct values that f(i) can take along with their start & end points in the following way:




```
int start=1,end=1;
while(start<=n)
{
	int l=start,r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(f(mid)==f(start))
			end=mid,l=mid+1;
		else
			r=mid-1;
	}
	cnt[f(start)]=(end-start+1);
	start=end+1;
	end=start;
}
```




We start at starting index 1.Then we try to find the right end for x1.Suppose right end is at index end.Then,we know that f(1)=f(2)=...=f(end-1)=f(end).We increment our new starting index to end+1.New required x is f(start).Similarly,we find end points and continue this process till we reach the end.





We know that f(i) can take at max log(a[1]) values.So start index will be updated log(a[1]) times.For every starting index,we do binary search to find the right end which takes log(n-start+1) time.We can see that the total complexity for calculating all prefix subarrays is (log(n))2(avoiding exact values inside log).This solution is only for prefix subarrays.





Now we further extend this for all subarrays.We declared start ing index as 1 in above code.Now,we would take every index in the array as starting index and follow the same process as above.





f(i,j) : Bitwise & of all elements between index i & j.





Note:For calculating f(i,j) we can use any datastructure which can query a range in O(1)/O(logn).Sparse table is used in my solution as it can answer a range query in O(1).





map cnt,mp.





cnt[i]-count of subarrays whose bitwise & value is i.





mp[i]-sum of sizes of all subarrays whose bitwise & value is i.




```
for(int i=1;i<=n;i++)
{
	int start=i,end=i;
	while(start<=n)
	{
		int l=start,r=n;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(f(i,mid)==f(i,start))
				end=mid,l=mid+1;
			else
				r=mid-1;
		}
		cnt[f(i,start)]=(end-start+1);
        int l1=start-idx,l2=end-idx+1;
		mp[cur]+=( ((l2*(l2+1))/2) ) - ( ((l1*(l1+1))/2) );
		start=end+1;
		end=start;
	}
}
```




We consider every index between 1 & n as the starting index.Calculation of mp[i] is just simple maths.Since we are calculating for entire array,new complexity is O(n.(logn)2).





SOLUTION LINK: