C++(g++ 7.5.0) 解法, 执行用时: 967ms, 内存消耗: 250636K, 提交时间: 2023-04-02 09:45:45

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=(a); i<=(b); i++)
#define uf(i,a,b) for(int i=(a); i>=(b); i--)
int n, q, s, w,l,r;
pair<int, int>f[(int)1e6+9][30];
int pre[(int)1e6];
int arr[(int)1e6];
int main() {
	scanf("%d%d%d%d",&n,&q,&s,&w);
	f(i,1,n){
		 scanf("%d",arr+i);
		f[i][0] = { arr[i] ^ s,-i };
		pre[i] = pre[i - 1] ^ arr[i];
	}
	for (int j = 1; (1 << j) <= n; j++) {
		for (int i = 1; i +(1<<j) - 1 <= n; i++) {
			f[i][j] = max(f[i][j - 1], f[i + ( 1 << (j - 1))][j - 1]);
		}
	}
	while (q--) {
		scanf("%d%d",&l,&r);
		int len = __lg(r-l+1);
		auto it = max(f[l][len], f[r - (1 << len)+1][len]);
		int  ss = (pre[r] ^ pre[l - 1] ^ arr[-it.second]);
		int ww = 0;
		uf(i,33,0){
			if ((ss>> i) & 1)continue;
			if(ww+((long)1<<i)>w) continue;
			ww |= 1 << i;
        }
		printf("%d\n",ss^ww);
	}

	return 0;
}

C++(clang++11) 解法, 执行用时: 721ms, 内存消耗: 99132K, 提交时间: 2020-12-28 17:59:45

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a,ss[N],n,m,s,w,lg[N],f[N][21];
int getmax(int l,int r){int k=lg[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&w),lg[0]=-1;
    for(int i=1;i<=n;i++)scanf("%d",&a),f[i][0]=a^s,ss[i]=ss[i-1]^a,lg[i]=lg[i/2]+1;
	for(int j=1;(1<<j)<=n;++j)for(int i=1;i+(1<<(j-1))<=n;++i)
	f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    while(m--)
	{
		int l,r;scanf("%d%d",&l,&r);
	    int ans=ss[r]^ss[l-1]^getmax(l,r)^s,res=0;
	    for(int k=29;~k;--k)if(!(ans&(1<<k))&&res+(1<<k)<=w)res+=(1<<k);
        printf("%d\n",ans^res);
    }
    return 0;
}