题解 | #小红的双排列查询#

link

这里考虑维护的信息。

考虑维护区间众数出现次数，维护区间最值。

这里使用了 Mo's algorithm 和 SparseTable。

。

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 2.5E5;
int sum[N + 1], z[N + 1];

template <class T, typename F = function<T(T, T)>>
struct SparseTable {
    int n;
    vector<vector<T>> a;
    F func;
    SparseTable(const vector<T> &init, const F f) : n(init.size()), func(f) {
        int lg = __lg(n);
        a.assign(lg + 1, vector<T>(n));
        a[0] = init;
        for (int i = 1; i <= lg; i++) {
            for (int j = 0; (1 << (i - 1)) + j < n; j++) {
                a[i][j] = func(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
            }
        }  	    
    }
    T get(int l, int r) { // [l, r)
        int lg = __lg(r - l);
        return func(a[lg][l], a[lg][r - (1 << lg)]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    SparseTable<int> mx(a, [&](int x, int y) {
        return max(x, y);
    });
    SparseTable<int> mn(a, [&](int x, int y){
        return min(x, y);
    });
    vector<array<int, 3>> qry(q);
    for (int i = 0; i < q; i++) {
        auto &[l, r, j] = qry[i]; 
        cin >> l >> r;
        l--, j = i; // [l, r)
    }

    int bk = n / sqrt(q);
    sort(qry.begin(), qry.end(), [&](const auto &a, const auto &b) {
        return ((a[0] / bk) ^ (b[0] / bk))
                ? a[0] < b[0]
                : (((a[0] / bk) & 1) ? a[1] < b[1] : a[1] > b[1]);
    });
    int l = 0, r = 0, res = 0;
    vector<string> ans(q);
    auto add = [&](int j) {
        int x = a[j];
        sum[z[x]]--, z[x]++, sum[z[x]]++;
        res = max(res, z[x]);    
    };
    auto del = [&](int j) {
        int x = a[j];
        if (z[x] == res && sum[z[x]] == 1) {
            res--;
        }
        sum[z[x]]--, z[x]--, sum[z[x]]++;
    };
    for (int i = 0; i < q; i++) {
        auto &[ql, qr, qi] = qry[i];
        while (r < qr) add(r++);
        while (l > ql) add(--l);
        while (l < ql) del(l++);
        while (r > qr) del(--r);
        int mx0 = mx.get(ql, qr), mn0 = mn.get(ql, qr), len = qr - ql;
        ans[qi] = "Yes";
        if (len % 2 || mx0 != len / 2 || mn0 != 1 || res != 2) {
            ans[qi] = "No";
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}