[CF1935E] Distance Learning Courses in MAC
难度正常的一道题。
首先我们发现 “挑选若干个区间” 就是一句废话，因为按位或只会贡献答案而不会减小答案。所以我们需要在 \([L,R]\) 的每个区间都挑一个数，使得最终的按位或最大。
想办法让尽可能多的二进制位都变成 \(1\)，且越是高位越好。但题目允许我们 \(O(n\log n)\) 的复杂度，直接想复杂度会出问题况且此题无部分分。所以考虑发现一些性质。比如这道题里，每个区间的数连续就是一个能很好配合按位或的性质。
因为数连续，不难想到对于每个区间 \([l_i,r_i]\)，有且仅有两种情况：
- \(\lfloor\log_2l_i\rfloor<\lfloor\log_2r_i\rfloor\)，也就是说，在 \(l_i\) 和 \(r_i\) 之间存在一个 \(2\) 的整数次幂的数，设为 \(2^k\)。那么一定存在一个数 \(2^k-1\)，这个数的二进制下的 \(0\sim\lfloor\log_2r_i\rfloor-1\) 位全部为 \(1\)，且一定有若干个数满足第 \(\lfloor\log_2r_i\rfloor\) 位是 \(1\)；
- \(\lfloor\log_2l_i\rfloor=\lfloor\log_2r_i\rfloor\)，则对于这个区间的所有数，第 \(\lfloor\log_2r_i\rfloor\) 位都是 \(1\)。
试将此结论推广到多个区间，对于任意编号为 \([L,R]\) 的区间和任意的区间最高位 \(F\in[0,\log_2V]\)，设 \(l_i,r_i\) 的第 \(F\) 位均为 \(1\) 的区间个数为 \(\mathit{sm}_1\)，而 \(l_i\) 的第 \(F\) 位是 \(0\)、\(r_i\) 的第 \(F\) 位是 \(1\) 的区间个数为 \(\mathit{sm}_2\)。则：
- 若 \(\mathit{sm}_1>0\land\mathit{sm}_2=0\)，则答案的第 \(F\) 位一定是 \(1\)；
- 若 \(\mathit{sm}_1=0\land\mathit{sm}_2=1\)，则答案的第 \(F\) 位也一定是 \(1\)；
- 否则，答案的第 \(0\sim F\) 位都是 \(1\)。
- 最后非常重要的一点，上述情况的必要条件是 \(\boldsymbol{\mathit{sm}_1>0\lor\mathit{sm}_2>0}\)。
到这里思路已经出来了：上文的 \(\mathit{sm}\) 数组可以前缀和处理区间和，然后从高到低遍历答案的每一位，按照上文的逻辑统计答案即可。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=2e5+5;
int T,F,n,q,sm1[MAXN][31],sm2[MAXN][31];
struct P{
int l,r;
}p[MAXN];
int lss(int x){
return 1<<__lg(x);
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i){
memset(sm1[i],0,sizeof(int)*(F+1));
memset(sm2[i],0,sizeof(int)*(F+1));
}
for(int i=1;i<=n;++i){
p[i]={read(),read()};
if(lss(p[i].l)^lss(p[i].r)) p[i].l=0;
F=max(F,__lg(p[i].r));
}
for(int i=1;i<=n;++i)
for(int j=0;j<=F;++j){
sm1[i][j]=sm1[i-1][j],sm2[i][j]=sm2[i-1][j];
if(p[i].l&(1<<j)&&p[i].r&(1<<j)) ++sm1[i][j];
if(!(p[i].l&(1<<j))&&p[i].r&(1<<j)) ++sm2[i][j];
}
q=read();
while(q--){
int l=read(),r=read(),ans=0;
for(int j=F;~j;--j)
if(sm1[r][j]-sm1[l-1][j]||sm2[r][j]-sm2[l-1][j]){
if(sm1[r][j]-sm1[l-1][j]&&!(sm2[r][j]-sm2[l-1][j]))
ans|=1<<j;
else if(!(sm1[r][j]-sm1[l-1][j])&&sm2[r][j]-sm2[l-1][j]==1)
ans|=1<<j;
else {
ans|=(1<<(j+1))-1;
break;
}
}
write(ans,' ');
}
putchar('\n');
}
return fw,0;
}