[分治] [众数] P8313 Izbori

_Cheems · 2023-11-08 20:28:49 · 个人记录

题意

定义绝对众数为出现次数大于序列大小一半的数。给定一个序列 a，求出具有绝对众数的连续子序列数量。

思路

众所周知众数并不具有很好的性质。但对此题而言，有一美妙性质：

• 固定一端点拓展区间，则可能取到的不同众数数量是 \log n 级别。

可这样理解：切换绝对众数需满足其次数 > 上一个，且 > 区间大小一半。模拟一下便能发现其次数呈 *2 的趋势上升，故为 \log n 级别。

又能发现：

• 考虑将区间分为两部分，则 l,r 的绝对众数必定取自这两个子区间。

由此可以想到序列分治。虽然之前我还不会。

考虑计算跨过中点的合法区间。由性质 \rm 1，不妨枚举众数 x。那么只需计算绝对众数为 x 的区间数。

而这一步可借鉴特殊性质 \rm 3 的做法。只需把式子拆成独立的两部分，枚举其一计算贡献（一维偏序）。随便拿个树状数组之类的东西实现即可。

然后注意统计时不要出现负数，没了。

代码

第一次打序列分治，纪念一下。

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

const int N = 2e5 + 5;

#define int long long
int n, a[N], nn, b[N], ans;
int buc[N], S, k[N << 1], ks;
int maxn, t[N * 5];

inline void upd(int k, int c) {k += n + 1; while(k <= maxn) {t[k] += c, k += k & -k;}}
inline int sum(int k) {k += n + 1; int res = 0; while(k > 0) {res += t[k], k -= k & -k;} return res;}
inline void solve(int l, int r){
    if(l == r) {++ans; return ;}

    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);

    ks = 0;
    for(int i = mid; i >= l;--i) if(++buc[a[i]] * 2 > mid - i + 1) k[++ks] = a[i];
    for(int i = mid; i >= l;--i) --buc[a[i]];
    for(int i = mid + 1; i <= r;++i) if(++buc[a[i]] * 2 > i - mid) k[++ks] = a[i];
    for(int i = mid + 1; i <= r;++i) --buc[a[i]];

    sort(k + 1, k + 1 + ks);
    int kss = unique(k + 1, k + 1 + ks) - k - 1;

    for(int i = 1; i <= kss;++i){
        int x = k[i];

        S = 0; upd(1 - l, 1);
        for(int j = l; j < mid;++j) S += (a[j] == x), upd(2 * S - j, 1);
        S += (a[mid] == x);
        for(int j = mid + 1; j <= r;++j) S += (a[j] == x), ans += sum(2 * S - j - 1); 

        S = 0; upd(1 - l, -1);
        for(int j = l; j < mid;++j) S += (a[j] == x), upd(2 * S - j, -1);
    }
} 
signed main(){
    cin >> n; maxn = 3 * n + 2;
    for(int i = 1; i <= n;++i) scanf("%lld", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n); int nn = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n;++i) a[i] = lower_bound(b + 1, b + 1 + nn, a[i]) - b;
    solve(1, n);
    cout << ans;
    return 0;
}