记录编号	364646	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.151 s
提交时间	2017-01-17 16:07:08	内存使用	27.31 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=20005;
struct node{
  node *ch[2];
  int data,Min,Max,ord,sz;
  node(int x){
    Min=Max=data=x;ord=rand();sz=1;ch[0]=ch[1]=0;
  }
  node(){}
  void update(){
    Min=Max=data;sz=1;
    if(ch[0])sz+=ch[0]->sz,Min=min(Min,ch[0]->Min),Max=max(Max,ch[0]->Max);
    if(ch[1])sz+=ch[1]->sz,Min=min(Min,ch[1]->Min),Max=max(Max,ch[1]->Max);
  }
}t[maxn*50];int tot=0;
node* newnode(int x){
  t[++tot]=node(x);return t+tot;
}
void rot(node* &rt,int t){
  node *c=rt->ch[t];rt->ch[t]=c->ch[t^1];c->ch[t^1]=rt;rt=c;
  rt->ch[t^1]->update();rt->update();
}
void insert(node* &rt,int x){
  if(!rt){
    rt=newnode(x);return;
  }
  int t=(x>=rt->data);
  insert(rt->ch[t],x);
  rt->update();
  if(rt->ch[t]->ord>rt->ord)rot(rt,t);
}
void remove(node* &rt,int x){
  if(x==rt->data){
    if(!rt->ch[0])rt=rt->ch[1];
    else if(!rt->ch[1])rt=rt->ch[0];
    else{
      int t=(rt->ch[0]->ord<rt->ch[1]->ord);
      rot(rt,t);remove(rt->ch[t^1],x);rt->update();
    }
  }else{
    remove(rt->ch[x>rt->data],x);
    rt->update();
  }
}
int getsz(node *rt){
  return rt?rt->sz:0;
}
int rk(node *rt,int x){//how many numbers smaller than x
  if(!rt)return 0;
  if(x<=rt->data)return rk(rt->ch[0],x);
  return getsz(rt->ch[0])+1+rk(rt->ch[1],x);
}
int RK(node *rt,int x){//how many numbers larger than x
  if(!rt)return 0;
  if(x>=rt->data)return RK(rt->ch[1],x);
  return getsz(rt->ch[1])+1+RK(rt->ch[0],x);
}
int n,m;
int a[maxn];
node* BIT[maxn];
inline int lowbit(int x){return x&(-x);}
void build(){
  for(int i=1;i<=n;++i){
    for(int j=i;j<=n;j+=lowbit(j)){
      insert(BIT[j],a[i]);
    }
  }
}
int Qsmall(int x,int w){
  int ans=0;
  for(;x;x-=lowbit(x))ans+=rk(BIT[x],w);
  return ans;
}
int Qsmall(int l,int r,int w){
  return Qsmall(r,w)-Qsmall(l-1,w);
}
int Qlarge(int x,int w){
  int ans=0;
  for(;x;x-=lowbit(x))ans+=RK(BIT[x],w);
  return ans;
}
int Qlarge(int l,int r,int w){
  return Qlarge(r,w)-Qlarge(l-1,w);
}
void Insert(int x,int w){
  for(;x<=n;x+=lowbit(x))insert(BIT[x],w);
}
void Remove(int x,int w){
  for(;x<=n;x+=lowbit(x))remove(BIT[x],w);
}
int c[maxn];
void add(int x){
  for(;x;x-=lowbit(x))c[x]++;
}
int sum(int x){
  int ans=0;
  for(;x<maxn;x+=lowbit(x))ans+=c[x];
  return ans;
}
int seq[maxn];
bool cmp(const int &x,const int &y){
  return a[x]<a[y];
}
int main(){
   freopen("nt2011_queue.in","r",stdin);
   freopen("nt2011_queue.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",a+i);
  for(int i=1;i<=n;++i)seq[i]=i;
  sort(seq+1,seq+n+1,cmp);
  int tot=0,old=-1;
  for(int i=1;i<=n;++i){
    if(a[seq[i]]!=old){
      old=a[seq[i]];++tot;
    }
    a[seq[i]]=tot;
  }
  long long ans=0;
  for(int i=1;i<=n;++i){
    ans+=sum(a[i]+1);add(a[i]);
  }printf("%lld\n",ans);
  build();
  scanf("%d",&m);
  int x,y;
  for(int i=1;i<=m;++i){
    scanf("%d%d",&x,&y);
    if(x>y)swap(x,y);
    if(a[x]<a[y])ans++;
    else if(a[x]>a[y])ans--;
    Remove(x,a[x]);Remove(y,a[y]);
    if(x+1<y){
      ans-=Qsmall(x+1,y-1,a[x]);ans+=Qlarge(x+1,y-1,a[x]);
      ans-=Qlarge(x+1,y-1,a[y]);ans+=Qsmall(x+1,y-1,a[y]);
    }
    swap(a[x],a[y]);
    Insert(x,a[x]);Insert(y,a[y]);
    printf("%lld\n",ans);
  }
  fclose(stdin);fclose(stdout);
  return 0;
}