2430.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2430 on 2007-01-15 at 22:57:39 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 102400;

class TreeArray {
private:
	int A[2*N], C;
	int lowBit(int t) const { return t&(-t); }
public:
	void clear(int n) { C = 2*n; memset(A, 0, sizeof(A)); }
	void add(int n, int a) { for(; n <= C; n += lowBit(n)) A[n] += a; }
	int sum(int b, int e) const { return total(e)-total(b-1); }
	int total(int) const;
};
int TreeArray::total(int n) const {
	int sum = 0;
	for(; n > 0; n -= lowBit(n)) sum += A[n];
	return sum;
}

TreeArray ta;
int s[2*N], pos[N][2], top[N], n;

int main()
{
	while(scanf("%d", &n) != EOF) {
		memset(top, 0, sizeof(top));
		ta.clear(n);
		for(int i = 0; i < 2*n; i++) {
			scanf("%d", &s[i]); s[i]--;
			pos[s[i]][top[s[i]]++] = i;
			ta.add(i+1, 1);
		}
		int64 score = 0;
		for(int i = 0; i < 2*n; i++) {
			if(top[s[i]] < 0) continue;
			top[s[i]] = -1;
			score += ta.sum(pos[s[i]][0], pos[s[i]][1]);
			ta.add(pos[s[i]][0]+1, -1); ta.add(pos[s[i]][1]+1, -1);
		}
		printf("%lld\n", score);
	}
	
	return 0;
}