2021暑假 HDU中超 第五场 1009

被这个题折磨了好几天
从比赛中的奇怪思路绕到洛谷原题，从分治绕到树状数组，还先去搞了半天模板题，可谓是曲线救国

2021暑假 HDU中超 第五场 1009

Array

Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 235 Accepted Submission(s): 48

题意

给你一个序列\(a[1...n]\)?，求存在绝对众数的子区间个数。

绝对众数指：区间中出现次数最多的那个数，出现次数严格大于区间长度的一半。

Sample Input

1
10
3303 70463 3303 3303 3303 70463 3303 3303 70463 70463

Sample Output

47

考场思路：

玄学而虚假的主席树乱搞做法

曲线救国：

首先注意到这是洛谷原题（RNM退钱）

分治做法：（只能过洛谷过不了比赛题）

对于区间 \([l,r]\)?，中间值 \(mid\)?， 我们需要统计经过 \(mid\)? 的所有合法区间 \([l', r']\)?

而如果 \([l',r']\)?? 拥有绝对众数，那么 \([l', mid]\) 和 \([mid+1, r']\) 中至少有一个有绝对众数

那么可以从 \(mid\) 往两边搜，统计每种数出现的次数，如果搜到某个位置时，当前数出现次数大于区间长度的一半，则这个数有可能成为绝对众数?。我们首先 \(O(r-l)\) 地找到所有可能的结果

再依次枚举这些众数，对于众数 \(X\)??，我们可以按投票的思想，把所有的 \(X\)??? 记为1，其他数记为-1，计算前缀和，这样可以判断任意区间是否满足条件。

若区间 \([l',r']\) 满足 \(sum[r'] - sum[l'-1] > 0\)，则这个区间有绝对众数 \(X\)

也就是说需要在 \(mid\)? 左右找到满足 \(sum[r'] > sum[l'-1]\)? 的点对个数

至此问题转化为了一个比较经典的模型，用树状数组搞即可。

代码复杂度 \(O(nlog^3n)\) 洛谷能过

但这题直接从1e5加强到1e6，直接T飞

AC做法：

首先记录每一种数字出现的位置，然后枚举每一种数字，设当前枚举到 \(X\)

然后还是按投票的思想，把所有的 \(X\)?? 记为1，其他数记为-1，计算前缀和 \(sum\)

若区间 \([l',r']\) 满足 \(sum[r'] - sum[l'-1] > 0\)，则这个区间有绝对众数 \(X\)（和上面做法一样）

考虑从左到右遍历，对于当前位置的前缀和 \(sum\)?? ，我们需要求出它左边比它小的前缀和个数

记录每个前缀和出现的次数为 \(cnt[x]\)，用树状数组维护?和查询

复杂度大概是 \(O(n^2logn)\)

想到我们记录了每个数字出现的位置，那么是不是可以在遍历的时候直接跳过一串连续的-1？

跳的时候面临两个问题：

1. 如何把这一串-1位置上的前缀和计入 \(cnt\) 数组
2. 如何计算这些-1位置对答案的贡献

对于问题二：

? 首先回忆一下：位置 \(p\)?????? 的贡献，就是 \(p\)? 前面比 \(sum[p]\)????? 小的前缀和个数

? 也就是 \(cnt\)?? 数组从最小值加到 \(sum[p]\)??? 为止的前缀和，设这个前缀和为 \(ssum\)?

? \(ssum[p]\)? 是位置 \(p\)? 上的答案

? 而我们需要知道这一连串-1的答案之和

? 显然再搞一遍前缀和就行了。。。设 \(sssum\) 是这个东西。。。

现在问题被转化成了：我们要维护 \(cnt\)? 数组的前缀和的前缀和

别急 还没完

对于问题一，其实很简单，对 \(cnt\) 数组搞个差分数组 \(d\)? 就好了，做到 \(O(1)\) 插入

那么只需要维护 \(d\)???? 数组的前缀和的前缀和的前缀和。。。

其实写起来没那么麻烦

我们只需要一个支持单点修改，三阶前缀和查询的数据结构

还是树状数组！

打包起来会比较好写一点

struct BitTree{//4行普通树状数组
    ll t[2*maxn];
    int lb(int x) {return x&-x;}
    void add(int p, ll ad){for(int i=p;i<=2*n+20;i+=lb(i)) t[i]+=ad;}
    ll sum(int p){ return p?t[p] + sum(p-lb(p)):0ll;}
};

struct BitTree3{//三阶前缀和的树状数组
    BitTree bt1, bt2, bt3;
    void add(int p, ll ad){
        bt1.add(p, ad);
        bt2.add(p, ad * p);
        bt3.add(p, ad * p * p);
    }
    ll sum(ll p){ return ((p+1)*(p+2) * bt1.sum(p) - (2*p+3) * bt2.sum(p) + bt3.sum(p)) / 2;}
    void modify(int l, int r, int dt = 1){
        add(l + bs, dt);
        add(r + 1 + bs, -dt);
    }
    ll query(int l, int r){
        if(l > r) return 0;
        return sum(r - 1 + bs) - sum(l - 2 + bs);
    }
};

AC代码：

#include
using namespace std;
#define ll long long
#ifdef ACM_LOCAL
const int maxn = 1000040;
#else
const int maxn = 1000040;
#endif

int n; ll bs;
vector pos[maxn];

struct BitTree{//4行树状数组
    ll t[2*maxn];
    int lb(int x) {return x&-x;}
    void add(int p, ll ad){for(int i=p;i<=2*n+20;i+=lb(i)) t[i]+=ad;}
    ll sum(int p){ return p?t[p] + sum(p-lb(p)):0ll;}
};

struct BitTree3{//三阶前缀和的树状数组
    BitTree bt1, bt2, bt3;
    void add(int p, ll ad){
        bt1.add(p, ad);
        bt2.add(p, ad * p);
        bt3.add(p, ad * p * p);
    }
    ll sum(ll p){ return ((p+1)*(p+2) * bt1.sum(p) - (2*p+3) * bt2.sum(p) + bt3.sum(p)) / 2;}
    void modify(int l, int r, int dt = 1){
        add(l + bs, dt);
        add(r + 1 + bs, -dt);
    }
    ll query(int l, int r){
        if(l > r) return 0;
        return sum(r - 1 + bs) - sum(l - 2 + bs);
    }
};

BitTree3 t;
void solve(){
    cin >> n >> bs;
    for(int i=1;i<=n;i++){
        int xx;
        cin >> xx;
        pos[xx].push_back(i);
    }
    ll ans = 0;
    bs = n + 10;
    for(int i=0;i<=1e6;i++){
        if(!pos[i].size()) continue;
        ll sum = 2 - pos[i][0];
        t.modify(1-pos[i][0], 0);
        t.modify(sum, sum);
        ans++;

        for(int j=1;j