程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5147 Sequence II(樹狀數組)

hdu 5147 Sequence II(樹狀數組)

編輯:C++入門知識

hdu 5147 Sequence II(樹狀數組)


題目鏈接:hdu 5147 Sequence II

預處理每個位置作為b和c可以組成的對數,然後枚舉b的位置計算。

#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxn = 50005;

int N, arr[maxn], fenw[maxn], lef[maxn], rig[maxn];

#define lowbit(x) ((x)&(-x))
void add(int x, int v) {
	while (x <= N) {
		fenw[x] += v;
		x += lowbit(x);
	}
}

int sum(int x) {
	int ret = 0;
	while (x) {
		ret += fenw[x];
		x -= lowbit(x);
	}
	return ret;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		scanf("%d", &N);
		memset(fenw, 0, sizeof(fenw));
		for (int i = 1; i <= N; i++)
			scanf("%d", &arr[i]);

		ll ans = 0, tmp = 0;
		for (int i = 1; i <= N; i++) {
			lef[i] = sum(arr[i]);
			rig[i] = N - i - arr[i] + lef[i] + 1;
			add(arr[i], 1);
			tmp += rig[i];
		}

		for (int i = 1; i <= N; i++) {
			tmp -= rig[i];
			ans += tmp * lef[i];
		}
		printf("%I64d\n", ans);
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved