 # Alohomora 2022 Problem Spidey Editorial

Problem D : SPIDEY
SETTER : lamda_cdm_10
TESTER :vishaaaal
Editorialist : lamda_cdm_10

Medium

# PREREQUISITES

SOS-DP , Bit Manipulation

# PROBLEM

You are given an array and you are given queries in the form [ L ,R , X ] you need to find the sum of elements in the indexes (i) of the array where i|X=X where | is bit wise OR operator. The value of X for current query is (X+PREV) where PREV is the answer of the previous query PREV=0 for first query.

# EXPLANATION

Let’s define a function F(R) which gives us the sum of values in the range [0-R] we can find the answer for this query by F(R)-F(L-1).
Let’s try to understand the implementation of F(R).
Check that the value of X can be very high but we require the bits which are at the right of MSB of (2*N) . so for each X can be take mod by (2*N) everytime.
We create the SOS dp table.
Now we go through the following conditions • If R is less than 0 we simply return 0
• If X is less than or equal to R we simply return dp[R]
Now comes the condition where X is larger than R we need to analyze the cases carefully
• We form 2 vectors that contain the binary representation of X and R+1 namely A and B respectively for each of the conditions we find the cases where the submask of X is strictly less than R+1.
What we do now is try to traverse through from the MSB of X and analyze the conditions.
For this we take a Variable pref = X and move from 0 to 20 .
• if we find A[i] = 0 and B[i] = 1 that means we have to break from the loop as B is no longer the submask of A and add dp[pref][20-i] to result.
• if we find A[i] = 1 and B[i] = 1 then we add dp[pref^(1<<(20-i))][20-i] to the result , what we have done here is find all the submask such that A[i] is 0 .
• if we find A[i] = 1 and B[i] = 0 set pref^=(1<<(20-i)) because this bit needs to be 0 for A[i]

# TIME-COMPLEXITY

The time complexity is O(Q*log(N)) as we expend log(N) time to answer each query.

# CODES

SETTER'S SOLUTION

e1oU1m - Online C++ Compiler & Debugging Tool - Ideone.com

TESTER'S SOLUTION

2z98Gc - Online C++ Compiler & Debugging Tool - Ideone.com

Any other solution or feedback can be posted in the comments. We are always open for them . 