题解 | 线性做法

考虑 sum hash

给每一个 n/2 以内的数一个随机权值，预处理所有双排列 sum hash 以及前缀 sum hash，根据长度判断是哪个双排列即可

#include <chrono>
#include <iostream>
#include <random>
using namespace std;

using ull = unsigned long long;

mt19937_64 myRand64(chrono::steady_clock::now().time_since_epoch().count());

int n;
int q;
ull has[125001];
ull pre[250001];

void Solve() {
    cin >> n >> q;
    for (int i = 1; i <= 125000; i++) {
        has[i] = myRand64();
    }
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (a > n / 2) {
            pre[i] = pre[i - 1];
        } else {
            pre[i] = pre[i - 1] + has[a];
        }
    }
    for (int i = 1; i <= 125000; i++) {
        has[i] += has[i - 1] + has[i];
    }
    while (q--) {
        int l;
        int r;
        cin >> l >> r;
        l--;
        int len = r - l;
        cout << (!(len & 1) && pre[r] - pre[l] == has[len / 2] ? "Yes\n" : "No\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}
// 64 位输出请用 printf("%lld")