题解-Enemy is weak

Enemy is weak

求序列 (a{n}) 中的三元逆序对数量。

数据范围:(3le nle 1e6)


这题真是一道又好又水的题,可是我看别人的题解做法真是玄学难懂,于是蒟蒻要写一篇简单易懂的。


考虑到二元逆序对的做法:离散化后动态维护一个权值树状数组。

其中对于每个当做逆序对后一元的 (i),当做逆序对前一元的 (j(j<i,a_j>a_i)) 的贡献为 (1)(i) 为总答案的贡献为 (s_i=sum_{j=1}^{i-1}[a_j>a_i])

其实求三元逆序对同样可以离散化后动态维护一个权值树状数组。

其中对于每个当做逆序对后一元的 (i),当做逆序对前一元的 (j(j<i,a_j>a_i)) 的贡献为 (s_j)(i) 为总答案的贡献为 (S_i=sum_{j=1}^{i-1}[a_j>a_i]s_j)

所以总共维护两个权值树状数组即可。


空间复杂度 (Theta(n)),时间复杂度 (Theta(nlog n))


小蒟蒻讲不清楚,小蒟蒻还是太蒻了 (/kk)。小蒟蒻放个代码吧,记得树状数组要开 ( exttt{long long})

//Data
const int N=1e6;
int n,a[N+7],b[N+7];
lng ans;

//Bittree
typedef vector<lng> bit;
bit c1(N+7),c2(N+7);
void add(bit&c,int x,lng y){for(;x<=n;x+=x&-x) c[x]+=y;}
lng sum(bit&c,int x){lng res=0;for(;x;x-=x&-x) res+=c[x];return res;}
lng sum(bit&c,int x,int y){return sum(c,y)-sum(c,x-1);}

//Main
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1;i<=n;i++) ans+=sum(c2,a[i]+1,n),add(c2,a[i],sum(c1,a[i]+1,n)),add(c1,a[i],1);
	printf("%lld
",ans);
	return 0;
}

祝大家学习愉快!

原文地址:https://www.cnblogs.com/George1123/p/12812951.html