[BZOJ 1106] [POI2007] 立方体大作战tet 【树状数组】

浏览数：46 / 时间：2015年06月08日

题目分析

从1到2n枚举每一个位置。

如果枚举到某一个数，这个数已经是第二次出现，那么就看它和第一次出现的位置之间有多少数还没有被匹配，有多少没有匹配的就要进行多少次交换。

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int MaxN = 100000 + 5;

int n, Ans;
int A[MaxN], T[MaxN], L[MaxN];

void Add(int x, int Num) 
{
	for (int i = x; i <= n; i += i & -i)
		T[i] += Num;
}

int Get(int x) 
{
	int ret = 0;
	for (int i = x; i; i -= i & -i)
		ret += T[i];
	return ret;
}

int main()
{
	scanf("%d", &n);
	n <<= 1;
	for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
	Ans = 0;
	for (int i = 1; i <= n; ++i) 
	{
		if (L[A[i]] == 0) 
		{
			L[A[i]] = i;
			Add(i, 1);
		}
		else 
		{
			Ans += Get(i) - Get(L[A[i]]);
			Add(L[A[i]], -1);
		}
	}
	printf("%d\n", Ans);
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[BZOJ 1106] [POI2007] 立方体大作战tet 【树状数组】