摘要
Title: 4645. 选数异或
Tag: dp、st表
Memory Limit: 64 MB
Time Limit: 1000 ms

4645. 选数异或

题意

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x，给定 m 次查询，每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x。
思路
1. st表
  w[i] 表示第i个数 $A_i$ 与 $k$ 的异或值的下标最近（右）是多少
  pre[x] 表示 $x$ 这个数自身的最新的下标是多少
  举例: k = 1
  A: 1 2 3 4
  w: 0 0 2 0
  w[3] = 2, 代表 2(3^1 = 2)最近出现在A数组的第2个位置
  那么一个区间内，是否存在满足的数，就是查询区间内的最大值是否大于等于l
  （如果有大于l的数，证明[l,r]区间内存在一个数，和k异或后的结果，在A数组中出现过，且下标大于等于l）
2. dp
  其实和st表思路相同，只不过相当于不用数据结构动态维护数组
  dp[r]的实际意义: 就是当查询区间[l, r], 右边界为r时，至少包含一个数对时的左边界最大值, 所以如果l小于等于这个左边界最大值， [l, r]区间内就至少有一个数对
$dp[i] = max(dp[i - 1], pre[x ⊕ k])$

代码

st表

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-02 19:41:09
* @FilePath: \Acwing\4645\4645.cpp
* @LastEditTime: 2023-01-02 19:56:00
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

#undef N
// const int N = 1e5 + 10;

// #undef int

const int N = 200010, M = 18;

int n, m, k;
int w[N], f[N][M], Log[N]; // 用来求log的
unordered_map<int, int> pre;

void init()
{
    for (int j = 0; j < M; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if (!j)
                f[i][j] = w[i];
            else
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
    Log[1] = 0;
    for (int i = 2; i <= n; i++)
        Log[i] = Log[i / 2] + 1;
}

int query(int l, int r)
{
    int k = Log[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

signed main()
{
    IOS;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        w[i] = pre[x ^ k];
        pre[x] = i; // 记录x自己的最右位置
    }
    init();
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        if (query(l, r) >= l)
            puts("yes");
        else
            puts("no");
    }

    return 0;
}

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-03 12:40:32
* @FilePath: \Acwing\4645.1\4645.1.cpp
* @LastEditTime: 2023-01-03 12:42:01
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

#undef N
const int N = 1e5 + 10;
int dp[N], n, m, k;

// #undef int

signed main()
{
    IOS;
    cin >> n >> m >> k;
    unordered_map<int, int> pre;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        dp[i] = max(dp[i - 1], pre[x ^ k]);
        pre[x] = i;
    }

    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << (dp[r] >= l ? "yes" : "no") << '\n';
    }

    return 0;
}

4645. 选数异或

题意

思路

代码