P8313 Izbori 题解

· · 题解

原题链接

提供一种考场上想出来的 n \log^2 n 分治做法，应该比正解好实现许多。

首先由于是序列计数问题，自然要往单调性方面去想。可仔细思考就会发现，众数这东西的性质好像不那么美妙，区间扩展时并不具有很好的性质，不能考虑枚举左端点然后向右扩展。

既然区间扩展不行，就考虑区间拼接。

我们先考虑两个区间拼起来是合法的，需要满足什么条件？我们用 L_x,R_x 分别表示 L,R 区间喜欢 x 菜肴的人数，那么 L,R 拼接起来合法，一定是存在一个 x，使得 2 \times (L_x+R_x) > len_L+len_R，不难发现不等式拆开就是一个一维偏序，将序列离散化后两组区间的拼接可以 O(n) 解决。

可现在还有一个问题，上面偏序的前提是 x 确定，可我们怎么知道 x 是什么呢？不难发现，对于两个确定的区间拼接，x 必须是其中一方的众数，可这并不能帮助我们把许多区间更快拼接。

可让我们一看题目,你就会发现题目还有一个很强的条件：获得一半以上的人支持！

我们定义一个序列有绝对众数，当且仅当一个序列的众数个数大于区间长度除以二。这时我们可以将上面的结论改一改：对于两个确定的区间拼接，x 必须是其中一方的绝对众数。

考虑序列分治，每次递归处理子区间的问题，现在我们只考虑跨过 mid 的区间。考虑分治带给我们什么好处：不难发现，对于左半部分，这些区间右端点固定，对于右边部分，这些区间左端点固定。

那这又有什么用呢？不难发现，一端端点固定的一组序列，不同的绝对众数的个数是 \log n 级别的。这也很好证明，因为若 [L,R] 这段区间绝对众数为 a ,那么往左右扩展时要求众数改变并且是绝对众数，每次几乎都需要成倍级别增长，结论得证。

那这时思路就明确了，先序列分治，然后对于每层来说，先求出可能的绝对众数作为 x，然后枚举绝对众数用桶做一维偏序。

并且这样做不会算重，因为拼接后的一个序列一定只会被一个绝对众数判断为合法。

下附代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
const int N=2e5+10,delta=2e5;
int n,val[N],cnt[N<<1];
bool vis[N];
vector<int> vec,chosen;
inline LL solve(int l,int r)
{
    if(l==r) return 1;
    LL ans=solve(l,mid)+solve(mid+1,r);
    for(int i=mid;i>=l;i--)
    {
        cnt[val[i]]++;
        if(!vis[val[i]]&&cnt[val[i]]>(mid-i+1)/2)   
        {
            chosen.push_back(val[i]);
            vis[val[i]]=true;
        }
    }
    for(int i=mid;i>=l;i--) cnt[val[i]]--;
    for(int i=mid+1;i<=r;i++)
    {
        cnt[val[i]]++;
        if(!vis[val[i]]&&cnt[val[i]]>(i-mid)/2) 
        {
            chosen.push_back(val[i]);
            vis[val[i]]=true;
        }
    }
    for(int i=mid+1;i<=r;i++)   cnt[val[i]]--;
    for(auto x:chosen)
    {
        int now,minn=delta-max(mid-l+1,r-mid),maxn=delta+max(mid-l+1,r-mid);
        now=0;
        for(int i=mid;i>=l;i--) 
        {
            now+=(val[i]==x);
            cnt[(now<<1)-(mid-i+1)+delta]++;
        }
        for(int i=minn;i<=maxn;i++) cnt[i]+=cnt[i-1];
        now=0;
        for(int i=mid+1;i<=r;i++)
        {
            now+=(val[i]==x);
            ans+=(mid-l+1)-cnt[(i-mid)-(now<<1)+delta];
        }
        for(int i=minn;i<=maxn;i++) cnt[i]=0;       
    }
    chosen.clear();
    for(int i=l;i<=r;i++)   vis[val[i]]=false;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&val[i]);
    for(int i=1;i<=n;i++)   vec.push_back(val[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++)   val[i]=lower_bound(vec.begin(),vec.end(),val[i])-vec.begin()+1;
    printf("%lld",solve(1,n));
    return 0;
}

完结撒花~