All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Rahul's Lucky ID Number

Data Structures


Rahul will be assigned his college id number soon. 

He considers the id number to be lucky for himself if it can be expressed in the form-

                                 \(2^x+2^y\) ( \(x \neq y , x \geq 0 , y \geq 0\)). 

He plays a game in which he decides to make N guesses for his id number and wants you to perform some queries on his guesses, which fall in either of the two categories- 

Category 1:

Given p,q change his p-th guess to q 

Category 2:

Given p,q find how many lucky id numbers exist from his p-th guess to q-th guess.(both inclusive).

If p > q then print 0.

Input Format: 

The first line contains T, the number of testcases. 

For each testcase,

 A separate line contains N, the number of guesses Rahul makes.

The next line contains N space separated integers denoting the guesses for his id number. 

The next line contains Q, the number of queries. 

Each query contains three space separated integers m, p, q.  

m denotes the category of the query (1 or 2) and p, q are the parameters to be used by each of the query. 

Output Format:

Answer category 2 of the query by printing the required integer on a new line. 

For Instance- Using 1-based indexing, category 2 asks you to count the number of lucky guesses among the guess at p-th index, guess at (p+1)-th index and so on till the guess at q-th index.

If m=2 and p > q then print 0.


0<=Rahul’s Guess(id number)<= (10^9+1) 

0 < T <= 2 

0 < N <= 10^5 

0 < Q <= 10^5 

m is either 1 or 2 

1 <= p <= N 

0 <= q <= (10^9+1) (if m is 1) 

1 <= q<= N (if m is 2) 

3 1
1 2 6
2 1 2
1 1 2
2 1 1


The N = 2 guesses are as below: 

1st guess 3 

2nd guess 1 


1st query-(category 1)

p=2 q=6 

Change p th guess i.e 2nd guess to 6 

Therefore, 2nd guess becomes 6 

2nd query-(category 2)

p=1 q=2 

We find number of lucky id numbers from 1st guess to 2nd guess (both inclusive)

1st guess is 3=2^1+2^0 (lucky) 

2nd guess is 6=2^1+2^2 (lucky) 

So, we print 2 as the answer to this query. 

3rd query-(category 1)

Similarly, this query makes 1st guess as 2 


4th query-(category 2)

 we find the number of lucky guesses from 1st guess to 1st guess- 

1st guess is 2 (can't be expressed as 2^x+2^y where x!=y,x>=0,y>=0) 

So this guess is unlucky and we print 0. 

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications