[Solution] MinimizOR solution codeforces

MinimizOR solution codeforces – You are given an array 𝑎a of 𝑛n non-negative integers, numbered from 11 to 𝑛n.

Let’s define the cost of the array 𝑎a as min𝑖𝑗𝑎𝑖|𝑎𝑗mini≠jai|aj, where || denotes the bitwise OR operation.

There are 𝑞q queries. For each query you are given two integers 𝑙l and 𝑟r (𝑙<𝑟l<r). For each query you should find the cost of the subarray 𝑎𝑙,𝑎𝑙+1,,𝑎𝑟al,al+1,…,ar.

[Solution] MinimizOR solution codeforces

Each test case consists of several test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains an integer 𝑛n (2𝑛1052≤n≤105) — the length array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖<2300≤ai<230) — the elements of 𝑎a.

The third line of each test case contains an integer 𝑞q (1𝑞1051≤q≤105) — the number of queries.

Each of the next 𝑞q lines contains two integers 𝑙𝑗lj𝑟𝑗rj (1𝑙𝑗<𝑟𝑗𝑛1≤lj<rj≤n) — the description of the 𝑗j-th query.

It is guaranteed that the sum of 𝑛n and the sum of 𝑞q over all test cases do not exceed 105105.

Output

For each test case print 𝑞q numbers, where the 𝑗j-th number is the cost of array 𝑎𝑙𝑗,𝑎𝑙𝑗+1,,𝑎𝑟𝑗alj,alj+1,…,arj.

[Solution] MinimizOR solution codeforces

Example
input

Copy
2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4
output

Copy
7
3
3
1
2
3
1
1073741823

MinimizOR solution codeforces

In the first test case the array 𝑎a is

1102,0012,0112,0102,00121102,0012,0112,0102,0012.

That’s why the answers for the queries are:

  • [1;2][1;2]𝑎1|𝑎2=1102|0012=1112=7a1|a2=1102|0012=1112=7;
  • [2;3][2;3]𝑎2|𝑎3=0012|0112=0112=3a2|a3=0012|0112=0112=3;
  • [2;4][2;4]𝑎2|𝑎3=𝑎3|𝑎4=𝑎2|𝑎4=0112=3a2|a3=a3|a4=a2|a4=0112=3;
  • [2;5][2;5]𝑎2|𝑎5=0012=1a2|a5=0012=1.

In the second test case the array 𝑎a is

002,102,012,111230002,102,012,11…12⏟30 (𝑎4=2301a4=230−1).

That’s why the answers for the queries are:

  • [1;2][1;2]𝑎1|𝑎2=102=2a1|a2=102=2;
  • [2;3][2;3]𝑎2|𝑎3=112=3a2|a3=112=3;
  • [1;3][1;3]𝑎1|𝑎3=012=1a1|a3=012=1;
  • [3;4][3;4]𝑎3|𝑎4=012|111230=2301=1073741823a3|a4=012|11…12⏟30=230−1=1073741823.

For Solution

Click here

Leave a Comment