Kilonova
Toggle theme

RoAlgo Contest #9 | Bit Showdown

This was the problem page during the contest. Access the current page here.
Time limit: 2s Memory limit: 64MB Input: Output:

Task

The two Runtime Terror teams met up in a fierce robot match-up, which is going to decide who is the best Runtime Terror team!

In order to quickly settle the fight, the members of the two teams decided to test these robots in a somewhat unusual event, namely summing numbers up! Now you are helping the members of the 22105 Runtime Terror team win this fight, but there is a catch -- you have to get this done fast.

Namely, you are given an array vv of nn integers and qq queries. In each of the qq queries, you will have to find the sum of the following values, depending on the type:

  • 1 L R1 \ L \ R -- find the sum of the bitwise AND for all unordered pairs of integers in that given subarray. In other words, find ∑i=LR∑j=i+1Rvi&vj\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i \& v_j.
  • 2 L R2 \ L \ R -- find the sum of the bitwise XOR for all unordered pairs of integers in that given subarray. In other words, find ∑i=LR∑j=i+1Rvi⊕vj\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i \oplus v_j.
  • 3 L R3 \ L \ R -- find the sum of the bitwise OR for all unordered pairs of integers in that given subarray. In other words, find ∑i=LR∑j=i+1Rvi∣vj\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i | v_j.

Help your favorite team win the round so that they can show the world they are the best Runtime Terrors out there.

Input data

On the first line you will find nn, the number of integers in the array. On the next line you will find the nn integers forming the array vv.

On the third line you will have qq, the number of queries. On each of the next qq lines you will have three integers t L Rt \ L \ R, where tt is the type of the query, LL and RR are the ends of the subarray in question.

Output data

The output will contain qq lines, representing the answers for each query.

Constraints and clarifications

  • 1≤n,q≤5⋅1051 \leq n, q \leq 5 \cdot 10^5;
  • 0≤vi<2200 \leq v_i < 2^{20};
  • 1≤t≤31 \leq t \leq 3;
  • 1≤L<R≤n1 \leq L < R \leq n;
# Score Constraints
0 0 Example
1 14 1≤n,q≤1001 \leq n, q \leq 100
2 12 1≤n,q≤10001 \leq n, q \leq 1000
3 16 0≤vi≤10 \leq v_i \leq 1
4 21 0≤vi≤150 \leq v_i \leq 15
5 37 No additional constraints

Example

stdin

9
8 1 9 4 7 9 4 9 3
14
1 7 8
2 1 4
1 5 6
3 1 7
2 2 8
3 2 3
2 3 6
3 5 7
1 1 9
2 1 9
3 1 9
1 2 5
2 2 9
1 4 6

stdout

0
48
1
210
166
9
57
35
77
278
355
7
216
5

Log in or sign up to be able to send submissions!