颓废

鲤鱼江 · 2025-08-02 19:20:13 · 个人记录

记录碰到的题。（是颓废记录所以你不能期望它们有多难）。

常回来看看，填坑练码力。

大家看到我一直不补这些题的代码可以直接在犇犇 diss 我。

P4062

P7882 的全局版本，P4062 存在 polylog 做法。

两个做法我都写！

polylog

考虑分治，常规 trick 之：

1. 将一个存在严格众数的序列任意分成两半，肯定存在一个序列其拥有严格众数且恰好为原序列的严格众数。
2. 一个序列的本质不同前缀众数只有 O(\log n) 种。

易证，且一个序列的绝对众数不超过一个。

直接分治统计即可，O(n\log^2 n) 是容易做到的。

懒得写了，搞个 O(n\log^3 n)，常数很小。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5e5+10;
int n,a[N],typ,b[N],cnt,sum[N],tot,ct[N];ll ans;

inline void Solve(int l,int r){
    if(l==r){++ans;return ;}
    int mid=(l+r)>>1,now=0;cnt=tot=sum[mid+1]=0;
    for(int i=mid+1;i<=r;++i){++ct[a[i]];b[++cnt]=now=(ct[a[i]]>ct[now]?a[i]:now);}
    for(int i=mid+1;i<=r;++i) ct[a[i]]=0;
    for(int i=mid;i>=l;--i){++ct[a[i]];b[++cnt]=now=(ct[a[i]]>ct[now]?a[i]:now);}
    for(int i=l;i<=mid;++i) ct[a[i]]=0;
    sort(b+1,b+1+cnt);cnt=unique(b+1,b+1+cnt)-b-1;
    for(int d=1;d<=cnt;++d){
        int x=b[d];
        for(int i=mid;i>=l;--i) sum[i]=sum[i+1]+(a[i]==x?1:-1);
        for(int i=mid;i>=l;--i) sum[i]=-sum[i];
        sort(sum+l,sum+mid+1);now=-1;
        for(int i=mid+1;i<=r;++i){
            now+=(a[i]==x?1:-1);
            ans+=upper_bound(sum+l,sum+mid+1,now)-sum-l;
//          cout<<x<<' '<<i<<' '<<ans<<' '<<now<<'\n';
        }
    }
//  cout<<l<<' '<<mid<<' '<<mid+1<<' '<<r<<' '<<ans<<'\n';
    Solve(l,mid);Solve(mid+1,r);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>typ;for(int i=1;i<=n;++i) cin>>a[i];
    Solve(1,n);cout<<ans<<'\n';
    return 0;
}

sqrt

不要忘了做这个题的初衷！

考虑阈值分治，设阈值为 B。

对于长度小于 2B 的子区间直接暴力求出来，是 O(nB) 的。

对于长度大于等于 2B 的子区间，其众数至少出现了 B 次，所以这种数不会超过 \frac{n}{B} 暴力枚举统计即可。

考虑怎么统计，考虑怎么判定一个区间的绝对众数是否是 x，将 a_i=x 的位置视作 1，否则视作 -1。那么一个区间的绝对众数是 x 当且仅当区间和大于零。

也就是：sum_r-sum_{l-1}>0，其中 r-l+1\ge 2B。

看上去这是一个二维数点问题，但是可以发现 |sum_{r+1}-sum_r|=1，维护一个桶 t_i 表示 sum_{l-1}=t_i 的数量。每次 sum_r 变化的时候可以 O(1) 维护出取值。

块长开到 27 之后把 O(n\log^2 n) 的代码按在地上打，出题人有好好造数据吗？

#include<bits/stdc++.h>

using namespace std;

const int B=27;
const int N=5e5+5;
const int Max=1e6+10;
typedef long long ll;
int n,a[N],cnt[N],C,b[N],typ,sum[N];ll ans;

struct Bucket{
    int t[Max];
    inline void push(int x){++t[x+N];}
    inline int get(int x){return t[x+N];}
    inline void clear(){for(int i=N-n;i<=N+n;++i) t[i]=0;}
}t;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>typ;for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) if((++cnt[a[i]])==B) b[++C]=a[i];
    for(int i=1;i<=n;++i) cnt[a[i]]=0;
    for(int i=1;i<=n;++i){
        int ed=min(i+2*B-2,n),c=0;
        for(int j=i;j<=ed;++j){
            c=max(c,++cnt[a[j]]);
            ans+=(2*c>(j-i+1));
        }
        for(int j=i;j<=ed;++j) cnt[a[j]]=0;
    }
    for(int i=1;i<=C;++i){
        int x=b[i],res=0;
        for(int j=1;j<=n;++j){
            sum[j]=sum[j-1]+(a[j]==x?1:-1);
            if(a[j]==x) res+=t.get(sum[j]-1);
            else res-=t.get(sum[j]);
            if(j>=2*B){int k=j-2*B;t.push(sum[k]);res+=(sum[j]>sum[k]);}
            ans+=res;
        }
        t.clear();
    }
    cout<<ans<<'\n';
    return 0;
}

超级钢琴

很厉害的 trick，现在才写是不是没救了（哭）。

考虑区间和可以表示为 sum_{r}-sum_{l-1}，发现 k 只有 5\times 10^5，做法肯定是直接找出前 k 大的区间。