Luogu P4062 [Code+#1]Yazid 的新生舞会

题目描述

https://www.luogu.com.cn/problem/P4062

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间存在绝对众数

$n\le 5\times 10^6$

Solution

首先我们考虑一个 $O(n\log n)$ 的做法

我们考虑数字 $v$ 作为绝对众数出现的区间，我们令 $v$ 所在的位置都是 $1$，其它位置都是 $-1$，那么显然区间和大于 $0$ 的区间都是 $v$ 作为绝对众数出现的区间

那么现在我们考虑前缀和，也就是说对于每个位置的前缀和我们只需要查询它前面有多少前缀和比它小即可

那么对于每个 $1/-1$ 序列，显然一堆连续的 $-1$ 之间是没有贡献的，那么我们只需要考虑 $1$ 即可

对于两个临近的 $1$，设第一个 $1$ 的前缀和为 $pre$，位置为 $l$，第二个 $1$ 的位置为 $r$，两个 $1$ 之间有 $d$ 个 $-1$，$less_k$ 表示$[1,l-1]$ 前缀和小于 $k$ 的个数，那么 $[l,r-1]$ 的贡献和就是 $\sum_{i=pre-d}^{pre}less_i$

然后我们考虑使用数据结构来维护这个东西，容易发现可以使用树状数组维护三阶前缀和来做到，由于只需要考虑 $1$ 的位置，所以总的时间复杂度 $O(n\log n)$，常数比较大，但总比线段树小的多

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 2000010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int n, type;

struct Fenwick {
    ll B1[maxn], B2[maxn], B3[maxn]; int n;
    void init(int _n) { n = _n; }
    
    void add(int x, ll v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += v * x, B3[i] += v * x * x;
    }

    ll get_sum(int x) {
        ll s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += B1[i] * (x + 1) * (x + 2) - B2[i] * (2 * x + 3) + B3[i];
        return s / 2;
    }

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

    ll query(int l, int r) { return get_sum(r) - get_sum(l - 1); } 
} Bit;

vector<int> A[maxn];

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

    cin >> n >> type; Bit.init(2 * n + 1); 
    for (int i = 1, x; i <= n; ++i) cin >> x, A[x].push_back(i);
    for (int i = 0; i < n; ++i) A[i].push_back(n + 1);
    ll ans = 0; 
    for (int i = 0; i < n; ++i) {
        int last = 0, pre = n + 2; Bit.update(pre, pre, 1); 
        for (auto t : A[i]) {
            int d = t - last - 1; 
            ans += Bit.query(pre - d - 1, pre - 1);
            Bit.update(pre - d, pre - 1, 1); pre += 1 - d;
            Bit.update(pre, pre, 1); last = t;
        }
        last = 0; pre = n + 2; Bit.update(pre, pre, -1);
        for (auto t : A[i]) {
            int d = t - last - 1; 
            Bit.update(pre - d, pre - 1, -1); pre += 1 - d; 
            Bit.update(pre, pre, -1); last = t; 
        }
    } cout << ans << "\n";
    return 0;
}

现在我们考虑一个 $O(n)$​ 的做法，实际上就是对 $O(n\log n)$​ 做法的修改，注意到序列只有 $+1/-1$​​，且 $1$​ 的数量是 $O(n)$​

我们考虑前缀和的形状

容易发现，我们不需要统计红线以外的点，且红线上方的点的个数也是 $O(n)$ 的

$+1/-1$ 序列求前缀和顺序对可以轻松做到 $1$ 的数量 的时间复杂度，大概就是我们维护 $f_i$ 表示前缀和为 $i$​ 的点的个数，那么我们连续的 $-1$ 对于 $f$ 的修改相当于是区间修改，这个时候我们可以打一个向后走的标记来进行维护

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define maxn 1000010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int n, type, a[maxn];

vector<int> A[maxn];

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

    cin >> n >> type; 
    for (int i = 1, x; i <= n; ++i) cin >> a[i], A[a[i]].push_back(i);
    for (int i = 0; i < n; ++i) A[i].push_back(n + 1);
    ll ans = 0;
    for (int v = 0; v < n; ++v) {
        unordered_map<int, int> s, d;
        int Min = 0, k = 0, pre = 0; ll res = 0;
        for (int i = 1; i <= n; ++i) {
            if (i > A[v][k]) ++k;
            if (a[i] != v && pre == Min) {
                ll len = A[v][k] - i - 1;
                --d[pre + 1]; ++d[pre - len];
                i += len; pre -= len + 1; 
            }
            else if (a[i] == v) {
                s[pre] += d[pre]; ++s[pre];
                d[pre + 1] += d[pre]; d[pre] = 0;
                res += s[pre++]; ans += res;
            }
            else ++s[pre--], res -= s[pre], ans += res;
            Min = min(Min, pre);
        }
    } cout << ans << "\n"; 
    return 0;
}