All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Xor sum
Tag(s):

Advanced Data Structures, Bitmask, Data Structures, Easy, Segment Trees, segtree

Problem
Editorial
Analytics

You are given an array $$A[]$$ of size $$N$$. Now you are given $$Q$$ queries to be performed over this array. In each query, you are given $$2$$ space separated integers $$L$$ and $$R$$. For each query, you need to you need to find the summation of the xor-sum of all triplets $$(i,j,k)$$ of the sub-array $$L...R$$ , where $$ L \le  i < j < k \le R $$.

In short, you need to find $$ \sum (A[i] \oplus A[j] \oplus A[k]) $$, over all triplets $$ (i,j,k)$$ , such that $$ L \le i < j < k  \le R $$ . Print the answer for each query , Modulo $$10^9+7$$

Input Format

The first line contains a single integer $$N$$.

The next line contains  array $$A[]$$ of $$N$$ integers.

The next line contains $$2$$ space separated integers $$Q$$ and $$2$$.

Each of the next $$Q$$ lines contains two space separated integers $$L$$ and $$R$$

Output Format :

Print $$Q$$ lines, the $$i^{th}$$ line denoting the answer to the $$i^{th}$$ query, Modulo $$10^9+7$$

Input Constraints :

\(1 \le N,Q \le 10^5 \)

\(1 \le A[i] \le 10^{12} \)

\(1 \le L \le R \le N \)

SAMPLE INPUT
4
1 2 3 4
1 2
1 4
SAMPLE OUTPUT
18
Explanation

$$ (1 \oplus 2 \oplus 3)+(2 \oplus 3 \oplus 4)+(1 \oplus 2 \oplus 4)+(1 \oplus 3 \oplus 4)=18 $$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Redlock India Pvt. Ltd.

Challenge Name

Redlock Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?