题解：CF2056D Unique Median

flyfreemrn · 2025-01-19 21:21:53 · 题解

首先，对于所有长度为奇数的子串，一定是好的子串，我们可以直接预处理出来。

对于长度为偶数的子串，我们可以观察到 a 的数据范围只有 10，一个暴力的思想就是直接枚举子串的中位数 i，然后统计子串个数。

我们假设一个子串小于 i 的数的个数为 a，等于 i 的数的个数为 b 大于 i 的数的个数为 c，那么一个好的子串需要满足：

我们将式子拆开，发现 a，b，c 并不好处理，也很难统计，所以我们可以换个思路，应用容斥思想，统计以 i 为其中一个中位数但不是好子串的个数。

假设，有 a 个数小于等于 i，b 个数大于 i，对于我们要统计的两个条件：

1. 以 i 为其中一个中位数：i 要在子串中出现过，且

   \frac{(a+b)}{2} \le a

2. 这个子串不是好子串，也就是排序后第 (a+b)/2+1 为不等于 i。

   a<\frac{(a+b)}{2}+1

这个式子列出来，我们就可以发现，其实我们要统计的子串就是小于等于 i 的数出现恰好 \frac{(a+b)}{2} 次且 i 出现过的子串。

我们可以借助前缀和和桶统计答案。

最后，ACcode：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200010
#define N 100000
// By flyfreemrn
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
ll T,n,a[MAXN],t[MAXN],ans;
ll work(ll p){
//  memset(t,0,sizeof(t)); 不能直接清空桶，会TLE
    ll now=N,res=0;//赋初始值N，防止now<0时越界
    queue<ll> q,_q;//q暂存桶数据，_q负责清空桶
    q.push(N);
    for(int i=1;i<=n;i++){
        if(a[i]<=p)now++;
        else now--;//前缀和统计当前位置小于等于i的数和大于i的数的数量关系
        if(a[i]==p){
            while(!q.empty()){//发现和p相同的数，这时队列中的数据可以添加到桶中在之后被查询
                ll fnt=q.front();
                _q.push(fnt);
                q.pop();
                t[fnt]++;
            }
        }
        res+=t[now];
        q.push(now);//因为我们要保证子串存在p，所以要暂存数据
    }
    while(!_q.empty()){//清空桶
        ll fnt=_q.front();
        _q.pop();
        t[fnt]=0;
    }
    return res;
}
int main(){
    T=read();
    while(T--){
        n=read();
        ans=0;
        for(int i=1;i<=n;i++)a[i]=read(),ans+=i;//处理所有子串
        for(int i=1;i<=10;i++){
            ans-=work(i);//容斥
//          cout<<i<<" "<<work(i)<<endl;
        }
        cout<<ans<<endl;
    }
    return 0;
}

AC