P4062 [Code+#1]Yazid 的新生舞会

思路：分治

提交：2次

错因：数组开小

题解：

我们枚举一下众数\(x\)。

设\(s[n]=\sum_{i=1}^n [a[i]==x]\)

那么对于区间\((l,r]\)，有\(s[r]-s[l]>\frac{r-l}{2}\)

即\(2*s[r]-r>2*s[l]-l\)

考虑分治，我们求出所有过中点的区间\([l,r]\)的贡献。

如何求呢？首先观察一个性质，两个子区间的众数至少有1个是大区间的众数，反之亦然。

那么我们先求出子区间中的众数，作为大区间的可行众数。然后我们枚举每个可行众数，依次求出符合\(2*s[r]-r>2*s[l]-l\)的区间。

还有一个特别神的数组做法，可是我不会

代码：

#include<bits/stdc++.h>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

} const int N=500010;

int n,a[N],pos[N],num[N],cnt[N*2]; ll ans;

inline void solve(int l,int r) {

	if(l==r) {++ans; return ;} R md=l+r>>1,tot=0;

	solve(l,md),solve(md+1,r);

	for(R i=md;i>=l;--i) if(++cnt[a[i]]>(md-i+1)/2)

		if(!pos[a[i]]) num[pos[a[i]]=++tot]=a[i];//左边的众数

	for(R i=l;i<=r;++i) cnt[a[i]]=0;

	for(R i=md+1;i<=r;++i) if(++cnt[a[i]]>(i-md)/2)

		if(!pos[a[i]]) num[pos[a[i]]=++tot]=a[i];//右边的众数

	for(R i=l;i<=r;++i) pos[a[i]]=0;

	for(R i=l;i<=r;++i) cnt[a[i]]=0;

	for(R i=1;i<=tot;++i) {//枚举可能的众数

		R sum=r-l+1,mx=sum,mn=sum;//mn,mx记录桶的上下界，sum作为初值相当于偏移量

		cnt[sum]=1; for(R j=l;j<md;++j) {//先处理出左边的桶

			a[j]==num[i]?++sum:--sum;

			mx=max(mx,sum),mn=min(mn,sum); ++cnt[sum];

		} a[md]==num[i]?++sum:--sum;

		for(R j=mn;j<=mx;++j) cnt[j]+=cnt[j-1];//前缀和。

		for(R j=md+1;j<=r;++j) {//处理右边

			a[j]==num[i]?++sum:--sum;

			ans+=cnt[min(mx,sum-1)];	//求出顺序对个数

		} for(R j=mn;j<=mx;++j) cnt[j]=0;

	}

}

inline void main() {

	n=g(); g(); for(R i=1;i<=n;++i) a[i]=g();

	solve(1,n); printf("%lld\n",ans);

}

} signed main() {Luitaryi::main(); return 0;}

2019.10.08

38

巴特西

P4062 [Code+#1]Yazid 的新生舞会

思路：分治

提交：2次

错因：数组开小

题解：

代码：

最新文章

热门文章