BSOJ6310题解

互不相同，太困难啦！！！！！！

考虑可以相同的情况。可以容斥。

\[ans=(1+1+1+1)-(2+1+1)+(3+1)+(2+2)-(4)
\]

有点抽象，看看就好（）

\[ans=(a,b,c,d)-(a,a,b,c)-(a,b,a,c)-(a,b,c,a)-(a,b,b,c)-(a,b,c,b)-(a,b,c,c)+(a,a,a,b)+(a,a,b,a)+(a,b,a,a)+(a,b,b,b)+(a,a,b,b)+(a,b,a,b)+(a,b,b,a)-(a,a,a,a)
\]

\[ans=(a,b,c,d)-(a,b,a,c)-(a,b,c,a)-(a,b,b,c)-(a,b,c,b)
\]

然后变成 \(O(n\log n)\) 的偏序问题，随便做做就好了（

#include<algorithm>

#include<cstdio>

typedef unsigned ui;

typedef unsigned long long ull;

const int M=1e5+5;

ui n,a[M],px[M],sx[M],py[M],sy[M];ui V[M],BIT[M];ui len,lsh[M];

inline void Add(ui x){

	++V[x];while(x<=len)++BIT[x],x+=x&-x;

}

inline ui Qry(ui x){

	ui ans(0);while(x>=1)ans+=BIT[x],x^=x&-x;return ans;

}

signed main(){

	ull s1(0),s2(0),ans(0);

	scanf("%u",&n);

	for(ui i=1;i<=n;++i)scanf("%u",a+i),lsh[++len]=a[i];

	std::sort(lsh+1,lsh+len+1);len=std::unique(lsh+1,lsh+len+1)-lsh-1;

	for(ui i=1;i<=n;++i)a[i]=std::lower_bound(lsh+1,lsh+len+1,a[i])-lsh;

	for(ui i=1;i<=n;++i){

		sx[i]=Qry(a[i]-1);

		sy[i]=i-V[a[i]]-1-sx[i];

		Add(a[i]);

	}

	for(ui i=1;i<=len;++i)BIT[i]=V[i]=0;

	for(ui i=n;i>=1;--i){

		px[i]=Qry(a[i]-1);

		py[i]=n-i-V[a[i]]-px[i];

		Add(a[i]);

	}

	for(ui i=1;i<=n;++i)s1+=py[i],s2+=px[i];ans=s1*s2;

	for(ui i=1;i<=n;++i){

		ans-=py[i]*px[i]+py[i]*sy[i]+sx[i]*px[i]+sx[i]*sy[i];

	}

	printf("%llu",ans);

}

巴特西

BSOJ6310题解

最新文章

热门文章