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 n n courses available. For the i i i-th distance learning course, a student can receive a grade ranging from x i x_i xi​ to y i y_i yi​.

However, not all courses may be available to each student. Specifically, the j j j-th student is only given courses with numbers from l j l_j lj​ to r j r_j rj​, meaning the distance learning courses with numbers l j , l j + 1 , … , r j l_j,l_{j+1},…,r_j lj​,lj+1​,…,rj​.

The creators of the distance learning courses have decided to determine the final grade in a special way. Let the j j j-th student receive grades c l j , c l j + 1 , … , c r j c_{l_j},c_{l_{j+1}},…,c_{r_j} clj​​,clj+1​​,…,crj​​ for their distance learning courses. Then their final grade will be equal to c l j ∣   c l j + 1 ∣   …   ∣ c r j c_{l_j} |\ c_{l_{j+1}} |\ …\ | c_{r_j} clj​​∣ clj+1​​∣ … ∣crj​​, 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 q 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 ≤ t ≤ 2 ⋅ 1 0 4 ) t (1\le t\le 2⋅10^4) t(1≤t≤2⋅104) — 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 ≤ n ≤ 2 ⋅ 1 0 5 ) n (1\le n\le 2⋅10^5) n(1≤n≤2⋅105) — the number of distance learning courses.

Each of the following n n n lines contains two integers x i x_i xi​ and y i y_i yi​ ( 0 ≤ x i ≤ y i 1 c>1，至少有2个数第 k k k位为1，因为下限 x i = 0 x_i=0 xi​=0，所以我们可以将其中一个数的第 k k k位置为0，剩下的 k − 1 k-1 k−1位全置为1，即 2 k 2^k 2k变为 2 k − 1 2^k-1 2k−1，另一个数不变，则答案可以加上 2 k + ( 2 k − 1 ) 2^k+(2^k-1) 2k+(2k−1)，则此时答案剩下的 k k k位已经全部变为1了，无需再向低位统计了。

所以我们只要去掉 x i x_i xi​的限制，就可以利用前缀和统计每个二进制位1的个数，并根据上面规则算出最大答案。

如何去掉 x i x_i xi​的限制呢，统计每对 ( x i , y i ) (x_i,y_i) (xi​,yi​)从高位到低位二进制的最长公共前缀值记为 w i w_i wi​，并将 w i w_i wi​从 ( x i , y i ) (x_i,y_i) (xi​,yi​)中减去变为 ( x i − w i , y i − w i ) (x_i-w_i,y_i-w_i) (xi​−wi​,yi​−wi​)即 ( x i ′ , y i ′ ) (x_i',y_i') (xi′​,yi′​)，则此时就无需考虑 x i x_i xi​的限制了，因为我们将 w i w_i wi​从 ( x i , y i ) (x_i,y_i) (xi​,yi​)中减去以后，此时 y i ′ y_i' yi′​最高位为 1 1 1， x i ′ x_i' xi′​对应的最高位必为 0 0 0（ y i ′ ≥ x i ′ + 1 y_i'\ge x_i'+1 yi′​≥xi′​+1），所以无论我们将 y i ′ y_i' yi′​中的任何为 1 1 1的第 k k k位置为0，剩下的 k − 1 k-1 k−1位置为1，都能保证 y i ′ ≥ x i ′ y_i'\ge x_i' yi′​≥xi′​。

#include
#define lson (k
    int n;
    scanf("%d",&n);
    for(int i=1;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
        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
                ans|=(2
    int T;
    cinT;
    while(T--)solve();
    return 0;
}