贪心加树状数组

给出的数据可能出现两种情况，包含与不包含，但我们从右向左删就能避免这个问题；

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=200010; int f[maxn],l[maxn],a[maxn]; long long tree[maxn]; int n; inline int lowbit(int x) { return x&(-x); } void add(int pos,int x) { for(int i=pos;i<=2*n;i+=lowbit(i)) tree[i]+=x; } int getsum(int pos) { int sum=0; for(int i=pos;i>0;i-=lowbit(i)) sum+=tree[i]; return sum; } int main() { while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); memset(l,0,sizeof(l)); for(int i=1;i<=2*n;i++) { scanf("%d",&a[i]); f[a[i]]==0?f[a[i]]=i:l[a[i]]=i; add(i,1); } long long ans=0; for(int i=1;i<2*n;i++) { //if(getsum(i)-getsum(i-1)>0) //{ if(f[a[i]]==0) continue; ans=ans+getsum(l[a[i]])-getsum(i-1)-1; add(i,-1); add(l[a[i]],-1); f[a[i]]=0; //} } printf("%lld\n",ans); } return 0; }