跳转至

P4062 Yazid 的新生舞会 题解

题目大意

给定长为 \(n\) 的序列，求包含绝对众数的区间个数。

题解

我们可以分别考虑每个数字为绝对众数时产生的贡献。考虑一个数字 \(x\)，根据摩尔投票法的思想，我们可以将序列中所有 \(a_i=x\) 的位置赋值为 \(1\)，其余位置赋值为 \(-1\)，问题转化为求区间和大于 \(0\) 的区间数量。

技巧

区间绝对众数首先考虑摩尔投票法的思路。

因为是区间和，所以考虑前缀和转化，即求在前缀和数组上的顺序对 \((s_i,s_j)\)（\(i<j,s_i<s_j\)）的数量。如果不考虑时间复杂度，可以使用权值树状数组，通过单修区查实现。

但是因为我们枚举了众数的值，所以对于数字 \(x\) 只能枚举该 \(x\) 所在的那些位置（即不枚举其他位置），才能保证均摊时间复杂度的正确性。

容易发现，\(x\) 出现的一个位置到下一次出现之前，中间的一段的前缀和 \(s\) 数组，是一段公差为 \(-1\) 的等差数列。等差数列的修改对应在值域上是一段区间修改，其查询可以表示为 \(\sum_{i=l}^r{sum(i-1)}\)，这是一个二阶前缀和。我们可以通过爆改树状数组，实现区间加，区间二阶前缀和查询。推一下公式即可。

AC 代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N = 5E5 + 10;

vector<int> pos[N];

int n, tp;
int a[N];

namespace BIT {

    int sum1[2 * N], sum2[2 * N], sum3[2 * N];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p + N; i <= 2 * N - 1; i += lowbit(i)) {
            sum1[i] += v;
            sum2[i] += p * v;
            sum3[i] += p * p * v;
        } 
    }
    inline void modify(int l, int r, int v) {
        modify(l, v);
        modify(r + 1, -v);
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p + N; i > 0; i -= lowbit(i)) {
            res += (p * p + 3 * p + 2) * sum1[i];
            res -= (2 * p + 3) * sum2[i];
            res += sum3[i];
        }
        res /= 2;
        return res;
    } 
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }

}

signed main() {

    cin >> n >> tp;
    for(int i = 0; i <= n - 1; i++) pos[i].push_back(0);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for(int i = 0; i <= n - 1; i++) pos[i].push_back(n + 1);

    int ans = 0;

    for(int i = 0; i <= n - 1; i++) {
        int cur = -1;
        for(int j = 0; j < (int)pos[i].size() - 1; j++) {
            cur++;
            int l = cur - (pos[i][j + 1] - pos[i][j]) + 1, r = cur;
            ans += BIT::query(l - 1, r - 1);
            BIT::modify(l, r, 1);
            cur = l;
        }
        cur = -1;
        for(int j = 0; j < (int)pos[i].size() - 1; j++) {
            cur++;
            int l = cur - (pos[i][j + 1] - pos[i][j]) + 1, r = cur;
            BIT::modify(l, r, -1);
            cur = l;
        }
    }

    cout << ans << endl;

    return 0;
}