RMQ问题-526互联

#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;
}