学步园

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1106

POI一刷根本停不下来……

树状数组统计相同元素之间不能匹配的个数

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,ans;
int d[maxn],a[maxn];
int p[maxn][2],vis[maxn];
int lowbit(int x){
	return x&-x;
}
int get(int x){
	int ans=0;
	while(x)ans+=d[x],x-=lowbit(x);
	return ans;
}
void updata(int x,int s){
	while(x<=n)d[x]+=s,x+=lowbit(x);
}
int main(){
	scanf("%d",&n);n*=2;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(!vis[a[i]])
			updata(i,1),vis[a[i]]=i;
		else{
			ans+=get(i)-get(vis[a[i]]-1)-1;
			updata(vis[a[i]],-1);
		}
	}cout<<ans<<endl;
	return 0;
}