rsrams

pystraf11 · 2026-04-26 22:18:47 · 题解

Description

给定序列 a_1\sim a_n，q 次查询求 [l,r] 的所有子区间的绝对众数之和（没有的不计）。

Limitations

Solution

视 n,q 同阶。考虑对于每种 x，把等于 x 的点视为 1，其它点视为 -1，那么要求区间和 >0，前缀和一下变成顺序对数，但是对所有 x 做一遍是不现实的。

考虑找出每种 x 可能成为绝对众数的大区间 [L_i,R_i]，顺序枚举 x 出现的位置，选择它左边第一个未选的异色点，再反过来做一遍，得出 x 出现位置和被选位置的所有连通块，它们就是答案。这些区间的总长为 O(n)，且一个点只会和 O(\log n) 个异色的 [L_i,R_i] 有关。

一个询问 [l,r] 只与和它有交的 [L_i,R_i] 有关，考虑分类它们的关系。

::::info[Case 1：[L_i,R_i]\in [l,r]]{open} 就是一个二维数点，把每个 [L_i,R_i] 的答案算出来，然后做扫描线，BIT 维护一下即可，复杂度 O(n\log n)。 ::::

::::info[Case 2：[l,r]\in [L_i,R_i]]{open} 把每个 [L_i,R_i] 的前后缀答案算出来，对于一个询问，在询问的 l,r 端枚举一下可能的 [L_i,R_i] 去查预算好的贡献即可，复杂度 O(n\log n)。 ::::

::::info[Case 3：无包含关系]{open} 对每种 [L_i,R_i] 把有关的询问拉出来，直接跑莫队统计顺序对即可，所有复杂度加起来是 O(n\sqrt n)。 ::::

这里由于值的变化是 \pm 1，所以直接开一个桶 \text{cnt}_x 就能维护出全局及前后缀的答案，是 O(n) 的。对于莫队部分同理，可以规避掉二次离线，常数会小很多。

那么时间复杂度 O(n\sqrt n)，实际不用卡常就过了。

::::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;

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

template<class T>
struct fenwick {
    int n;
    vector<T> c;

    inline fenwick() {}
    inline fenwick(int _n): n(_n) { c.resize(n + 1); }

    inline fenwick(const vector<T> &a): n(a.size()) {
        c.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            c[i] = c[i] + a[i - 1];
            int j = i + lowbit(i);
            if (j <= n) c[j] = c[j] + c[i];
        }
    }

    inline void add(int x, const T& v) {
        for (int i = x + 1; i <= n; i += lowbit(i)) c[i] = c[i] + v;
    }

    inline T ask(int x) {
        T ans{};
        for (int i = x + 1; i; i -= lowbit(i)) ans = ans + c[i];
        return ans;
    }

    inline T ask(int l, int r) { return l > r ? T{} : ask(r) - ask(l - 1); }
};

struct Query {
    int l, r, id;
    Query() {}
    Query(int l, int r, int id) : l(l), r(r), id(id) {}
};
using pii = pair<int, int>;

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

    int n, q; qin >> n >> q; vector<int> a(n); vector<vector<int>> vec(n);
    for (int i = 0; i < n; i++) qin >> a[i], a[i]--, vec[a[i]].push_back(i);

    vector<Query> S; vector<pii> rg; vector<int> ind;
    for (int i = 0; i < n; i++) {
        if (vec[i].empty()) continue;
        int siz = vec[i].size();

        int las = -1; rg.clear(), ind.clear();
        for (int j = 0; j < siz; j++) {
            int x = vec[i][j];
            if (x > las + 1) rg.emplace_back(las + 1, x - 1); las = x;
            if (!rg.empty()) ind.push_back(rg.back().second), rg.back().second--;
            if (!rg.empty() && rg.back().second < rg.back().first) rg.pop_back();
            ind.push_back(x);
        }

        las = n; rg.clear();
        for (int j = siz - 1; j >= 0; j--) {
            int x = vec[i][j];
            if (x < las - 1) rg.emplace_back(x + 1, las - 1); las = x;
            if (!rg.empty()) ind.push_back(rg.back().first), rg.back().first++;
            if (!rg.empty() && rg.back().first > rg.back().second) rg.pop_back();
        }

        sort(ind.begin(), ind.end());
        ind.erase(unique(ind.begin(), ind.end()), ind.end());
        vec[i].clear();

        for (int l = 0, r; l < ind.size(); l = r + 1) {
            r = l;
            while (r < ind.size() - 1 && ind[r + 1] - ind[l] == r - l + 1) r++;
            S.emplace_back(ind[l], ind[r], i);
        }
    }

    sort(S.begin(), S.end(), [&](auto x, auto y) {
        return x.r < y.r;
    });

    vector<int> bg(S.size()), ed(S.size());
    for (int i = 0; i < S.size(); i++) {
        bg[i] = (i ? ed[i - 1] + 1 : 0);
        ed[i] = bg[i] + S[i].r - S[i].l;
    }
    const int m = ed[S.size() - 1] + 1;

    vector<vector<int>> vp(n);
    vector<i64> pre(m), suf(m), sum(S.size());
    vector<int> cnt(n * 2 + 1);
    for (int i = 0; i < S.size(); i++) {
        int nw = n, dn = n, up = n, now = 0, dt = S[i].id;
        cnt[n]++;
        for (int j = bg[i], k = S[i].l; j <= ed[i]; j++, k++) {
            if (a[k] == dt) now += cnt[nw];
            else now -= cnt[nw - 1];
            nw += (a[k] == dt ? 1 : -1);
            cnt[nw]++;
            if (j == bg[i]) pre[j] = 1LL * (dt + 1) * now;
            else pre[j] = pre[j - 1] + 1LL * (dt + 1) * now;
            chmin(dn, nw), chmax(up, nw);
        }

        for (int j = dn; j <= up; j++) cnt[j] = 0;
        sum[i] = pre[ed[i]];

        now = 0, dn = up = nw = n, cnt[n]++;
        for (int j = ed[i], k = S[i].r; j >= bg[i]; j--, k--) {
            if (a[k] == dt) now += cnt[nw];
            else now -= cnt[nw - 1];
            nw = nw + (a[k] == dt ? 1 : -1);
            cnt[nw]++;
            if (j == ed[i]) suf[j] = 1LL * (dt + 1) * now;
            else suf[j] = suf[j + 1] + 1LL * (dt + 1) * now;
            chmin(dn, nw), chmax(up, nw);
        }

        for (int j = dn; j <= up; j++) cnt[j] = 0;
        for (int j = S[i].l; j <= S[i].r; j++) vp[j].push_back(i);
    }

    vector<Query> qry(q);
    vector<i64> ans(q);
    vec.resize(S.size());

    for (int i = 0, l, r; i < q; i++) {
        qin >> l >> r;
        l--, r--;
        qry[i] = {l, r, i};

        int sizl = vp[l].size(), sizr = vp[r].size();
        for (int j = 0; j < sizl; j++) {
            int x = vp[l][j];
            if (S[x].r <= r) ans[i] += suf[bg[x] + l - S[x].l];
            else vec[x].push_back(i);
        }

        for (int j = 0; j < sizr; j++) {
            int x = vp[r][j];
            if (S[x].l > l) ans[i] += pre[bg[x] + r - S[x].l];
        }
    }

    sort(qry.begin(), qry.end(), [&](auto x, auto y) {
        return x.r < y.r;
    });

    vector<int> ord(q);
    fenwick<i64> bit(n);
    for (int i = 0; i < q; i++) ord[qry[i].id] = i;
    for (int i = 0, j = 0, k = 0; i < n; i++) {
        while (k < q && qry[k].r <= i) ans[qry[k].id] += bit.ask(qry[k].l + 1, n - 1), k++;
        while (j < S.size() && S[j].r <= i) bit.add(S[j].l, sum[j]), j++;
    }

    vector<Query> d;
    vector<int> val(n + 1); 
    for (int i = 0; i < S.size(); i++) {
        if (vec[i].empty()) continue;

        int siz = vec[i].size(), up = n, dn = n;
        d.resize(siz);
        for (int j = 0; j < siz; j++) d[j] = qry[ord[vec[i][j]]];
        int B = sqrt(S[i].r - S[i].l + 1);

        sort(d.begin(), d.end(), [&](auto x, auto y) {
            if (x.l / B == y.l / B) return (x.l / B & 1) ? x.r > y.r : x.r < y.r;
            return x.l < y.l;
        });

        int L = S[i].l, R = S[i].l - 1, nowl = 0, nowr = 0;
        i64 now = 0; cnt[n]++; val[S[i].l] = n;
        for (int j = S[i].l; j <= S[i].r; j++) {
            val[j + 1] = val[j] + (a[j] == S[i].id ? 1 : -1);
            chmax(up, val[j + 1]), chmin(dn, val[j + 1]);
        }

        for (int j = 0; j < siz; j++) {
            int l = d[j].l, r = d[j].r;
            while (R < r) {
                if (val[R + 2] > val[R + 1]) nowr += cnt[val[R + 1]]; else nowr -= cnt[val[R + 2]];
                now += nowr; R++; if (val[L] < val[R + 1]) nowl++; cnt[val[R + 1]]++;
            }

            while (L > l) {
                if (val[L] > val[L - 1]) nowl += cnt[val[L]]; else nowl -= cnt[val[L - 1]];
                now += nowl; L--; if (val[L] < val[R + 1]) nowr++; cnt[val[L]]++;
            }

            while (R > r) {
                now -= nowr; cnt[val[R + 1]]--;
                if (val[R] > val[R + 1]) nowr += cnt[val[R + 1]]; else nowr -= cnt[val[R]];
                if (val[L] < val[R + 1]) nowl--; R--;
            }

            while (L < l) {
                now -= nowl; cnt[val[L]]--;
                if (val[L] > val[L + 1]) nowl += cnt[val[L]]; else nowl -= cnt[val[L + 1]];
                if (val[L] < val[R + 1]) nowr--; L++;
            }
            ans[d[j].id] += 1LL * (S[i].id + 1) * now;
        }

        for (int j = dn; j <= up; j++) cnt[j] = 0;
        for (int j = S[i].l; j <= S[i].r + 1; j++) val[j] = 0;
    }

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

    return 0;
}

::::