[HOJ] 87 - 佇列

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define N 20005
#define low(x) (x&-x)
map<int,int> ma;
map<int,int>::iterator k;
vector<int> vec;
int s[N],c[N],top=1,n;
void add(int x){
    int i;
    for(i=x;i<top;i+=low(i)){
        c[i]++;
    }
}
int cntn(int x){
    int i,tmp=0;
    for(i=x;i>0;i-=low(i))
        tmp+=c[i];
    return tmp;
}
long long int cnt(){
    long long int tmp=0;
    int i;
    memset(c,0,sizeof(c));
    for(i=1;i<=n;i++){
        tmp+=i-1-cntn(s[i]);
        add(s[i]);
    }
    return tmp;
}
int main(){
    int m,i,j,x,y;
    long long int ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&s[i]);
        vec.push_back(s[i]);
    }
    sort(vec.begin(),vec.end());
    for(i=0;i<vec.size();i++){
        k=ma.find(vec[i]);
        if(k==ma.end()){
            ma[vec[i]]=top++;
        }
    }
    for(i=1;i<=n;i++){
        s[i]=ma[s[i]];
    }
    ans=cnt();
    printf("%lld\n",ans);
    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);
        for(j=x+1;j<y;j++){
            if(s[j]<s[x])
                ans--;
            if(s[j]>s[x])
                ans++;
            if(s[j]<s[y])
                ans++;
            if(s[j]>s[y])
                ans--;
        }
        if(s[x]>s[y]) ans--;
        if(s[x]<s[y]) ans++;
        swap(s[x],s[y]);
        printf("%lld\n",ans);
    }
}