题解：CF1935E Distance Learning Courses in MAC

· · 题解

一拍桌子，两眼放光，直接 ST 表维护 y 的或和，输出！

然后你就假了。

某个反面教材，我不说是谁。

思路

定义舍弃为把一个数 y 的某一位 p 从 1 改为 0，且 p 位以下全变为 1。

假设每个位置选了 q，那么要么 q=y，要么 q 是 y 舍弃一位得到的数。

我们不知道舍弃哪个位置，所以很难不预处理哪些位置可以被舍弃。显然地，y_i 的这一位必须是 1，且舍弃后不小于 x_i。

设 f_{i,j} 表示前 j 个数第 i 位一共有多少个 1，g_{i,j} 表示前 j 个数中可以在第 i 位舍弃的数量。不难发现这两个东西都可以差分。

每次询问时，肯定要从高位开始贪心。只有 f_{i,r}-f_{i,l-1}>1，且 g_{i,r}-g_{i,l-1}>0 时，才考虑舍弃第 i 位，牺牲“有余力”的 1，这样答案的第 i 位及以下就全是 1 了。

代码

#include<cstdio>
int T,n,x[200001],y[200001],f[30][200001],g[30][200001],q,l,r,ans;
int read(){
    int x=0;
    char c=getchar();
    while(c<48||c>57)c=getchar();
    while(c>47&&c<58)x=x*10+c-48,c=getchar();
    return x;
}
int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;++i)x[i]=read(),y[i]=read();
        for(int i=0;i<30;++i){
            for(int j=1;j<=n;++j){
                f[i][j]=f[i][j-1]+(y[j]>>i&1),g[i][j]=g[i][j-1];
                if(y[j]>>i&1&&(y[j]^1<<i|((1<<i)-1))>=x[j])++g[i][j];
            }
        }
        q=read();
        while(q--){
            l=read(),r=read(),ans=0;
            for(int i=29;~i;--i){
                if(f[i][r]-f[i][l-1])ans|=1<<i;
                if(f[i][r]-f[i][l-1]>1&&g[i][r]-g[i][l-1]){ans|=(1<<i)-1;break;}
            }
            printf("%d ",ans);
        }
        printf("\n");
    }
    return 0;
}