Codeforces-1935E：Distance Learning Courses in MAC（思维）

E. Distance Learning Courses in MAC
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
The New Year has arrived in the Master’s Assistance Center, which means it’s time to introduce a new feature!

Now students are given distance learning courses, with a total of $n$ courses available. For the $i$-th distance learning course, a student can receive a grade ranging from $x_i$ to $y_i$.

However, not all courses may be available to each student. Specifically, the $j$-th student is only given courses with numbers from $l_j$ to $r_j$, meaning the distance learning courses with numbers $l_j,l_{j+1},\dots ,r_j$.

The creators of the distance learning courses have decided to determine the final grade in a special way. Let the $j$-th student receive grades $c_{l_j},c_{l_{j+1}},\dots ,c_{r_j}$ for their distance learning courses. Then their final grade will be equal to $c_{l_j}|c_{l_{j+1}}|\dots |c_{r_j}$, where | denotes the bitwise OR operation.

Since the chatbot for solving distance learning courses is broken, the
students have asked for your help. For each of the $q$ students, tell them the maximum final grade they can achieve.

Input
Each test consists of multiple test cases. The first line contains a single integer $t(1\le t\le 2\cdot 10^4)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n(1\le n\le 2\cdot 10^5)$ — the number of distance learning courses.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ $(0\le x_i\le y_i<2^{30})$ — the minimum and maximum grade that can be received for the $i$-th course.

The next line contains a single integer $q(1\le q\le 2\cdot 10^5)$ — the number of students.

Each of the following $q$ lines contains two integers $l_j$ and $r_j$ $(1\le l_j\le r_j\le n)$ — the minimum and maximum course numbers accessible to the $j$-th student.

It is guaranteed that the sum of $n$ over all test cases and the sum of $q$ over all test cases do not exceed $2\cdot 10^5$.

Output
For each test case, output $q$ integers, where the $j$-th integer is the maximum final grade that the $j$-th student can achieve.

Example
input
3
2
0 1
3 4
3
1 1
1 2
2 2
4
1 7
1 7
3 10
2 2
5
1 3
3 4
2 3
1 4
1 2
6
1 2
2 2
0 1
1 1
3 3
0 0
4
3 4
5 5
2 5
1 2
output
1 5 4
15 11 15 15 7
1 3 3 3

思路：按二进制位从高到低计算，假设所有$x_i=0$，此时只需考虑$y_i$的上限，设$c$为二进制第$k$为$1$的$y_i$个数，则有

1. $c=0$，没有任何一个数第$k$位为1，答案不变。
2. $c=1$，只有一个数第$k$位为1，则答案加上$2^k$。
3. $c>1$，至少有2个数第$k$位为1，因为下限$x_i=0$，所以我们可以将其中一个数的第$k$位置为0，剩下的$k-1$位全置为1，即$2^k$变为$2^k-1$，另一个数不变，则答案可以加上$2^k+(2^k-1)$，则此时答案剩下的$k$位已经全部变为1了，无需再向低位统计了。

所以我们只要去掉$x_i$的限制，就可以利用前缀和统计每个二进制位1的个数，并根据上面规则算出最大答案。
如何去掉$x_i$的限制呢，统计每对$(x_i,y_i)$从高位到低位二进制的最长公共前缀值记为$w_i$，并将$w_i$从$(x_i,y_i)$中减去变为$(x_i-w_i,y_i-w_i)$即$(x_i^{\prime },y_i^{\prime })$，则此时就无需考虑$x_i$的限制了，因为我们将$w_i$从$(x_i,y_i)$中减去以后，此时$y_i^{\prime }$最高位为$1$，$x_i^{\prime }$对应的最高位必为$0$（$y_i^{\prime }\ge x_i^{\prime }+1$），所以无论我们将$y_i^{\prime }$中的任何为$1$的第$k$位置为0，剩下的$k-1$位置为1，都能保证$y_i^{\prime }\ge x_i^{\prime }$。

#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const int MAX=2e5+10;
const int MOD=998244353;
const int INF=1e9;
const double PI=acos(-1.0);
const double eps=1e-9;
typedef int64_t ll;
int s[30][MAX];
int c[30][MAX];
int solve()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        for(int j=29;j>=0;j--)
        {
            s[j][i]=s[j][i-1];
            c[j][i]=c[j][i-1];
            if((y&(1<<j))==0)continue;
            if(x<((y>>j)<<j))c[j][i]++;
            else s[j][i]++;
        }
    }

    int q;
    scanf("%d",&q);
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;
        for(int i=29;i>=0;i--)
        {
            int cnt=c[i][y]-c[i][x-1]+(s[i][y]-s[i][x-1]>0);
            if(cnt==1)ans|=1<<i;
            if(cnt>1)
            {
                ans|=(2<<i)-1;
                break;
            }
        }
        printf("%d ",ans);
    }
    return puts("");
}
int main()
{
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63