区间查询异或最大值——cf1100F,hdu6579

亦凉 2023-10-11 09:10 7阅读 0赞

cf1100F是静态区间查询最大值，有离线的解法，我感觉线段树或者莫队应该都能过

更优秀的解法可以在线并支持修改，可以解决hdu6579,即依次插入每个数，pos\[i\]\[j\]表示在插第i个数时第j个基出现的最靠右的位置，然后p\[i\]\[j\]来表示插第i个数时第j个基的值

考虑普通的线性基插入值x的过程，在做这题时**使用贪心策略来插入，即找到最靠右的同阶的基，将其和x进行替换**，更新pos\[i\]\[j\]，然后循环进行这个步骤即可

查询区间时贪心从高位到低位进行查询，如果第j个基满足条件（用pos\[r\]\[j\]来判是否在\[l,r\]区间里出现过），那么就用其去更新res

/*
    给定数组a[],要求在O(logn)内求出区间[l,r]的最大异或值
    pos[i][j]表示凑出第j位的最靠右的位置 
    查询最大值的时候就要从高到低贪心查询 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define ll int
    #define maxn 500005
    ll n,x,q,pos[maxn][35],p[maxn][35];
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            for(int j=0;j<=20;j++)pos[i][j]=pos[i-1][j],p[i][j]=p[i-1][j];
            ll nowpos=i;
            for(int j=20;j>=0;j--)if(x>>j & 1){
                if(!p[i][j]){
        //如果没有可以替换的，等价于新插入了一个基j 
                    p[i][j]=x;pos[i][j]=nowpos;
                    break;
                }
                if(pos[i][j]<nowpos){
        //有更靠右的位置可以更新第j个基 
                    swap(p[i][j],x);
                    swap(pos[i][j],nowpos);//第j个基的位置被更新，但是nowpos被往前推,因为只有到对应的位置x才能被更新 
                } 
                x^=p[i][j];//对应地x^第j个基 
            }
        }
        
        int m;cin>>m;
        while(m--){
            ll res=0,l,r;
            scanf("%d%d",&l,&r);
            for(int j=20;j>=0;j--)
                if(pos[r][j]>=l)res=max(res,res^p[r][j]);
            cout<<res<<'\n';
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11271100.html