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;
}