文章

25

粉丝

0

获赞

0

访问

68465

头像
树状数组(求逆序对)
经验总结
发布于2020年4月20日 22:19
阅读数 3037

树状数组用于动态维护数组(矩阵)的前缀和,异或和,最大值,最小值。

(1)利用树状数组求逆序对O(nlogn)

楼兰图腾:y1~yn是1~n的一个全排列:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll c[N], l[N], r[N];
int n;
int a[N];
int lowbit(int x){
	return x&(-x);
}
void add(int x, int y){
	for (int i = x; i <= n; i += lowbit(i)){
		c[i] += y;
	}
}
int ask(int x){
	int res = 0;
	for (int i = x; i; i -= lowbit(i)){
		res += c[i];
	}
	return res;
}
int main(){
	ll sum1=0, sum2=0;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for (int i = n; i >= 1; i--){//求a[i]右边比a[i]大的数
		r[i] = ask(n) - ask(a[i]);
		add(a[i], 1);
	}
	//重置树状数组c
	memset(c, 0, sizeof c);
	for (int i = 1; i <= n; i++){//求a[i]左边比a[i]大的数
		l[i] = ask(n) - ask(a[i]);
		add(a[i], 1);
	}
	//计算V图腾的数量
	for (int i = 1; i <= n; i++){
		sum1 += r[i] * l[i];
	}
	//重置
	memset(l, 0, sizeof l);
	memset(r, 0, sizeof r);
	memset(c, 0, sizeof c);
	for (int i = n; i >= 1; i--){//计算a[i]右边比a[i]小的数
		r[i] = ask(a[i] - 1);
		add(a[i], 1);
	}
	memset(c, 0, sizeof c);
	for (int i = 1; i <= n; i++){
		l[i] = ask(a[i] - 1);
		add(a[i], 1);
	}
	for (int i = 1; i <= n; i++){
		sum2 += l[i] * r[i];
	}
	cout << sum1 << " " << sum2 << endl;

	return 0;
}

https://blog.csdn.net/ssimple_y/article/details/53744096

https://blog.csdn.net/bestsort/article/details/80796531

https://www.bilibili.com/video/BV1pE41197Qj?from=search&seid=12108682439425406153



登录后发布评论

暂无评论,来抢沙发