【USACO 2017FEB】 Why Did the Cow Cross the Road III

【题目链接】 

            点击打开链接

【算法】

           树状数组

【代码】

            

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010

int n,i,x;
long long ans;
int pos[MAXN];
long long c[MAXN];

inline int lowbit(int x)
{
    return x & (-x);    
}    
inline void modify(int pos,long long val)
{
    int i;
    for (i = pos; i <= 2 * n; i += lowbit(i)) c[i] += val;
}
inline long long query(int pos)
{
    int i;
        long long ans = 0;
    for (i = pos; i; i -= lowbit(i)) ans += c[i];
    return ans;
}
inline long long query(int l,int r)
{
        return query(r) - query(l-1);
}

int main() {
        
        scanf("%d",&n);
        for (i = 1; i <= 2 * n; i++)
        {
                scanf("%d",&x);
                if (!pos[x])
                {
                        pos[x] = i;
                        modify(i,1);    
                }    else
                {
                        ans += query(pos[x]+1,i-1);
                        modify(pos[x],-1);
                }
        }
        printf("%lld
",ans);
        
        return 0;
    
}