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

<

2

30

)

(0\le x_i\le y_i\lt2^{30})

(0≤xi​≤yi​<230) — the minimum and maximum grade that can be received for the

i

i

i-th course.

The next line contains a single integer

q

(

1

≤

q

≤

2

⋅

1

0

5

)

q (1\le q\le2⋅10^5)

q(1≤q≤2⋅105) — the number of students.

Each of the following

q

q

q lines contains two integers

l

j

l_j

lj​ and

r

j

r_j

rj​

(

1

≤

l

j

≤

r

j

≤

n

)

(1\le l_j\le r_j\le n)

(1≤lj​≤rj​≤n) — the minimum and maximum course numbers accessible to the

j

j

j-th student.

It is guaranteed that the sum of

n

n

n over all test cases and the sum of

q

q

q over all test cases do not exceed

2

⋅

1

0

5

2⋅10^5

2⋅105.

Output For each test case, output

q

q

q integers, where the

j

j

j-th integer is the maximum final grade that the

j

j

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

x_i=0

xi​=0，此时只需考虑

y

i

y_i

yi​的上限，设

c

c

c为二进制第

k

k

k为

1

1

1的

y

i

y_i

yi​个数，则有

c

=

0

c=0

c=0，没有任何一个数第

k

k

k位为1，答案不变。

c

=

1

c=1

c=1，只有一个数第

k

k

k位为1，则答案加上

2

k

2^k

2k。

c

>

1

c>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<<1)

#define rson (k<<1)+1

#define mid ((l+r)/2)

#define sz(x) int(x.size())

#define pii pair

#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<

if(x<((y>>j)<

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<

if(cnt>1)

{

ans|=(2<

break;

}

}

printf("%d ",ans);

}

return puts("");

}

int main()

{

int T;

cin>>T;

while(T--)solve();

return 0;

}

好文链接

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：