题面

Solution

发现题目要求三个数据，， ，

  • 要求 满足在区间 都有 ，那么不就是让 最大吗？发现整个区间不需要修改，用线段树维护一下最大值和对应的编号即可

  • 接下来让我们求 , 一段区间的 ，emmm，想必大家都知道，一个数异或他自己等于 ，那么我们可以开个 数组用前缀和预处理一下，那么区间 的异或和就是 ，在把前面找到的 异或掉， 多异或一个 即可

  • 最后看一下 怎么求，暴力找太容易T掉了，让我们想一想怎么优化它。我们知道 的运算法则是相异为一相同为零，那么是不是说，相异的越多，答案也就越优？是的！

    现在是怎么求相异最多的 的问题,数据范围只有 ，那么 的二进制长最多也只有 位，让我们从高位向低位枚举，看看能不能添加上那个相异的数即可

为什么是从高往低呢？因为高位上的数对答案贡献更大，且低位的数更加灵活，如果先确定低位，可能一些更优的高位就找不到了。

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
#define lson i << 1
#define rson i << 1 | 1

using namespace std;
const int MAXN = 1e6+6;
const int INF = 1;
const int mod = 1;

int n, q, s, w;
int a[MAXN], sum[MAXN]; 

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace getK{//建立一棵线段树，维护区间最大值及其编号 
    struct Tree{
        int len, max, bh;
    }tree[MAXN << 2];
    void push_up(int i){//上传 
        tree[lson].max >= tree[rson].max ? (tree[i].max = tree[lson].max, tree[i].bh = tree[lson].bh) : (tree[i].max = tree[rson].max, tree[i].bh = tree[rson].bh);
    }
    void build(int i, int l, int r){
        tree[i].len = r - l + 1;
        if(l == r){
            tree[i].max = a[l], tree[i].bh = l;//建树 
            return ;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
        push_up(i);
    }
    Tree get_max(int i, int l, int r, int L, int R){//取最大值 
        if(L <= l && r <= R){
            return tree[i];
        }
        int mid = (l + r) >> 1;
        Tree ans;
        if(mid < L) return get_max(rson, mid + 1, r, L, R);//如果全在右边，就搜索右边的 
        else if(mid >= R) return get_max(lson, l, mid, L, R);//如果全在左边，就搜索左边的 
        else {//否则，两段都选，并且将这两段合并 
            Tree ansl = get_max(lson, l, mid, L, mid), ansr = get_max(rson, mid + 1, r, mid + 1, R);
            ansl.max >= ansr.max ? (ans.max = ansl.max, ans.bh = ansl.bh) : (ans.max = ansr.max, ans.bh = ansr.bh);
            return ans;
        }
    }
}

int getW(int S){//找到最大的W，根据xor的规则，与S同位相异的数越多越好，越大越好 
    S ^= ((1 << 30) - 1);
//    cout<<"S:"<<(((S >> 2) % 2) << 2)<<endl;
    int res = 0;
    for(int i = 31; i >= 0; --i){//从大到小查找 
        if((res ^ (((S >> i) % 2)) << i) <= w)    res ^= (((S >> i) % 2) << i);
    }
    return res;
}

int b[MAXN];
#undef int

int main()
{
#define int long long
    n = read(), q = read(), s = read(), w = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read(); //读入 
        b[i] = a[i];//存到b数组里 
        sum[i] = sum[i - 1] ^ a[i];//做一个前缀和 ，方便求S 
        a[i] = a[i] ^ s;// 提前异或好 
    }
//    cout<<cnt<<endl;
//    cout<<(sum[5] ^ sum[0] ^ b[4])<<" "<<(6 ^ 1)<<endl;;
//    for(int i = 1; i <= n; ++i) cout<<a[i]<<" ";
//    cout<<endl;
//    for(int i = 1; i <= n; ++i) cout<<sum[i]<<" ";
//    cout<<endl;
    getK::build(1, 1, n);//建树 
    for(int i = 1, l, r; i <= q; ++i){
        l = read(), r = read();
        int k = getK::get_max(1, 1, n, l, r).bh;
        int S = sum[r] ^ sum[l - 1] ^ b[k];
        int W = getW(S);
//        cout<<"k:"<<k<<" S:"<<S<<" W:"<<W<<endl<<"ans:"; 
        printf("%lld\n", (S ^ W));
    }
    return 0;
}

鄙人不才，如果有什么问题请随便提问。