Range Subrange Middle Equal Mode Query

pystraf11 · 2026-04-25 13:46:10 · 题解

Description

给定序列 a_1\sim a_n，q 次查询区间 [l,r]，求有几个子区间 [L,R] 满足长为奇数，且 x=\frac{L+R}{2} 是 a_L\sim a_R 的众数。

Limitations

Solution

视 n,q 同阶，设 x 在 a 中出现次数为 c_x。考虑以每个 x 为中心，不断增加半径 R，此时众数和 x 的出现次数递增，两者相等时 R 合法。枚举 k 设使得 x 出现 k 次的 R\in [l,r]，则可以找到一个 p 使得 R\in[l,p] 合法（区间可能为空）。因此可以算出若干组 (x_i,l_i,r_i) 表示 x_i 为中心，R\in [l_i,r_i] 的区间都合法，显然只有 O(n) 组。

考虑如果求出了这些组，每组对查询的贡献，其为 [x_i-r_i,x_i-l_i],[x_i+l_i,x_i+r_i] 分别与 [l,r] 的交集长度的 \min。设 \text{mid}=\frac{l+r}{2}，则 x_i\le \text{mid} 的贡献为前者，否则为后者，两遍扫描线统计即可，复杂度 O(n\log n)。

现在只需要求出这些组，一个暴力是二分 p 然后用分块查区间 [x-p,x+p] 的众数是否出现超过 k 次，由于要二分 O(n) 个区间，复杂度为 O(n\sqrt n\log n)，显然过不了。考虑对 c_x 根号分治，设阈值为 B。

由于 c_x \ge B 的 x 只有 O(\frac{n}{B}) 种，对每种 x 直接枚举 R 扩展即可。对于 c_x<B 的 x，显然 k<B，考虑每种 k 做一遍，套上面的二分算法，则需要 O(1) check。求出 \text{nxt}_i 表示 i 往右第 k+1 个 a_i 出现位置，然后设 \text{dp}_l 为使得 [l,r] 内众数出现超过 k 次的最小 r，可以证明 \text{dp} 就是 \text{nxt} 的后缀 \min，O(n) 求两个数组是容易的，check 时直接看是否 \text{dp}_{x-p}>x+p。

那么复杂度 O(nB+\frac{n^2}{B})，取 B=O(\sqrt n) 得 O(n\sqrt n)。实际上由于跑不满，B 要开得较小。

::::info[code]

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

namespace Fastio {}
using Fastio::qin;
using Fastio::qout;

int lowbit(int x) {
    return x & (-x);
}

struct Bit {
    int n;
    vector<i64> c1, c2;

    Bit() {}
    Bit(int _n): n(_n) {
        c1.resize(n);
        c2.resize(n);
    }

    void add(int x, i64 k) {
        for (int i = x + 1; i <= n; i += lowbit(i)) {
            c1[i - 1] += k;
            c2[i - 1] += k * x;
        }
    }

    i64 ask(int x) {
        i64 res = 0;
        for (int i = x + 1; i; i -= lowbit(i)) {
            res += c1[i - 1] * (x + 1) - c2[i - 1];
        }
        return res;
    }

    void update(int l, int r, i64 v) {
        add(l, v);
        add(r + 1, -v);
    }

    i64 sum(int l, int r) {
        return ask(r) - ask(l - 1);
    }
};

struct Query {
    int x, l, r, id;
    Query() {}
    Query(int x, int l, int r, int id) : x(x), l(l), r(r), id(id) {}
};

constexpr int B = 80, inf = 1e9;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    qin >> n >> q;

    vector<int> a(n), c(n), idx(n);
    vector<basic_string<int>> pos(n), v(n);
    for (int i = 0; i < n; i++) {
        qin >> a[i], a[i]--, c[a[i]]++;
        pos[a[i]] += abs(i - a[i]);
        v[a[i]] += i;
        idx[i] = v[a[i]].size() - 1;
    }

    vector<Query> qry;
    for (int i = 0, l, r; i < q; i++) {
        qin >> l >> r;
        l--, r--;
        qry.emplace_back((l + r) / 2, l, r, i);
    }

    vector<int> cnt;
    auto init_large = [&](int x) {
        cnt.assign(n, 0);
        int mx = 0, flag = 0, st = 0;
        for (int i = 0; x - i >= 0 && x + i < n; i++) {
            chmax(mx, ++cnt[a[x - i]]);
            if (i) chmax(mx, ++cnt[a[x + i]]);
            if (cnt[x] == mx && !flag) st = i;
            if (cnt[x] != mx && flag) qry.emplace_back(x, st, i - 1, -1);
            if (cnt[x] == mx) flag = 1;
            else flag = 0;
        }
        if (flag) qry.emplace_back(x, st, min(x, n - x - 1), -1);
    };

    vector<int> f(n), suf(n + 1);
    auto init_small = [&](int x) {
        for (int i = 0; i < n; i++) {
            if (idx[i] + x < (int)v[a[i]].size()) f[i] = v[a[i]][idx[i] + x];
            else f[i] = inf;
        }

        suf[n] = inf;
        for (int i = n - 1; i >= 0; i--) suf[i] = min(suf[i + 1], f[i]);
        for (int i = 0; i < n; i++)
            if (c[i] < B && c[i] >= x) {
                int L = pos[i][x - 1];
                int R = min((c[i] > x ? pos[i][x] - 1 : inf), min(i, n - i - 1));
                if (L > R) continue;
                int l = L - 1, r = R;
                while (l < r) {
                    const int mid = (l + r + 1) / 2;
                    if (suf[i - mid] > i + mid) l = mid;
                    else r = mid - 1;
                }
                if (l >= L) qry.emplace_back(i, L, l, -1);
            }
    };

    for (int i = 0; i < n; i++)
        if (c[i] >= B) init_large(i);

    for (int i = 0; i < n; i++) sort(pos[i].begin(), pos[i].end());
    for (int x = 1; x < B; x++) init_small(x);

    sort(qry.begin(), qry.end(), [&](auto a, auto b) {
        if (a.x != b.x) return a.x < b.x;
        return a.id < b.id;
    });

    vector<i64> ans(q);
    Bit ds(n);
    for (auto it : qry) {
        if (it.id != -1) ans[it.id] += ds.sum(it.l, it.r);
        else ds.update(it.x - it.r, it.x - it.l, 1);
    }

    ds = Bit(n);
    reverse(qry.begin(), qry.end());
    for (auto it : qry) {
        if (it.id != -1) ans[it.id] += ds.sum(it.l, it.r);
        else ds.update(it.x + it.l, it.x + it.r, 1);
    }

    for (int i = 0; i < q; i++) qout << ans[i] << '\n';

    return 0;
}