#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//这里要开2e6 + 10因为我们用到了Ai当下表,Ai是1 << 20 > 1e6 + 10,在这被卡了好久
const int N = 2e6 + 10;
int last[N], g[N], a[N];
int f[N][30], logn[N];
int n, m, x;
void prework()
{
logn[1] = 0;
//预处理出来log方便后来直接查表
for(int i = 2; i <= n; ++ i) logn[i] = logn[i / 2] + 1;
//初始化递推条件,即从第i个元素开始长度为1的区间内的最大值就是这个数本身
for(int i = 1; i <= n; ++ i) f[i][0] = g[i];
//长度为一个已经初始化过了,直接从长度为2的地方开始递推
for(int j = 1; j <= 20; ++ j)
for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
{
// cout << i << ' ' << j << ' ' << f[i][j] << endl;
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
//查询操作,查询区间l,r的最大值
int query(int l, int r)
{
int k = logn[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
cin >> n >> m >> x;
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
//从前往后找到每个数和他配对并且离他最近的那个数的下表
for(int i = 1; i <= n; ++ i)
{
g[i] = last[x ^ a[i]];
last[a[i]] = i;
}
prework();
while(m --)
{
int l ,r;
scanf("%d%d",&l, &r);
if(query(l, r) < l) puts("no");
else puts("yes");
}
return 0;
}
标签:10,RMQ,int,2e6,问题,logn,include
From: https://www.cnblogs.com/cxy8/p/17275097.html