BZOJ4994[Usaco2017Feb]WhyDidtheCowCrosstheRoadIII树状数组

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N=100000+5;
int n,c[N*2],f[N];
LL ans=0;
int lowbit(int x){
	return x&-x;
}
void add(int x,int d){
	for (;x<=n*2;x+=lowbit(x))
		c[x]+=d;
}
int sum(int x){
	int ans=0;
	for (;x>0;x-=lowbit(x))
		ans+=c[x];
	return ans;
}
int main(){
	scanf("%d",&n);
	memset(c,0,sizeof c);
	memset(f,0,sizeof f);
	for (int i=1,x;i<=n*2;i++){
		scanf("%d",&x);
		if (!f[x]){
			f[x]=i;
			add(i,1);
		}
		else {
			ans+=sum(i-1)-sum(f[x]);
			add(f[x],-1);
		}
	}
	printf("%lld",ans);
	return 0;
}