自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:37:55，当前版本为作者最后更新于2022-11-09 15:27:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

提供一种考场上想出来的 $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;
}

完结撒花~