这个题就是动态偏序对，每次操作做两个删除两个插入就好了。
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 100010
using namespace std;
typedef long long LL;
typedef double D;
const D a=0.756;
LL ans;
struct ScapeGoat_Tree
{
ScapeGoat_Tree *ch[];
int key,size,cover,ex;
bool bad()
{
return cover*a+<ch[]->cover||cover*a+<ch[]->cover;
}
void pushup()
{
size=ch[]->size+ch[]->size+ex;
cover=ch[]->cover+ch[]->cover+;
}
}*null,*stack[(MAXN<<)+],pool[(MAXN<<)+],*lst[(MAXN<<)+];
int top,len;
inline void Init()
{
null=pool;
null->ch[]=null->ch[]=null;
null->key=null->size=null->cover=null->ex=;
for(int i=;i<(MAXN<<);i++)stack[++top]=pool+i;
}
inline ScapeGoat_Tree *New(int key)
{
ScapeGoat_Tree *p=stack[top--];
p->ch[]=p->ch[]=null;
p->key=key;
p->size=p->ex=p->cover=;
return p;
}
struct Tree
{
Tree *ch[];
int mid,l,r;
ScapeGoat_Tree *root;
Tree(){ch[]=ch[]=NULL;mid=l=r=;root=null;}
void* operator new(size_t size);
}*root,*C,*mempool;
void* Tree :: operator new(size_t size)
{
if(C==mempool)
{
C=new Tree[(<<)+];
mempool=C+(<<)+;
}
C->root=null;
return C++;
}
void travel(ScapeGoat_Tree *p)
{
if(p==null)return;
travel(p->ch[]);
if(p->ex)lst[++len]=p;
else stack[++top]=p;
travel(p->ch[]);
}
ScapeGoat_Tree *divide(int l,int r)
{
if(l>r)return null;
int mid=(l+r)>>;
lst[mid]->ch[]=divide(l,mid-);
lst[mid]->ch[]=divide(mid+,r);
lst[mid]->pushup();
return lst[mid];
}
inline void rebuild(ScapeGoat_Tree *&p)
{
len=;
travel(p);
p=divide(,len);
}
ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key)
{
if(p==null )
{
p=New(key);
return &null;
}
p->size++;
p->cover++;
ScapeGoat_Tree **ret=insert(p->ch[p->key<=key],key);
if(p->bad())ret=&p;
return ret;
}
inline void Insert(ScapeGoat_Tree *&Root,int key)
{
ScapeGoat_Tree **p=insert(Root,key);
if(*p!=null )rebuild(*p);
}
inline int Rank_Max(ScapeGoat_Tree *Root,int key)
{
ScapeGoat_Tree *now=Root;
int ret=;
while(now!=null )
if(now->key<=key)
now=now->ch[];
else
ret+=now->ch[]->size+now->ex,now=now->ch[];
return ret;
}
inline int Rank_Min(ScapeGoat_Tree *Root,int key)
{
ScapeGoat_Tree *now=Root;
int ret=;
while(now!=null )
if(now->key>=key)
now=now->ch[];
else
ret+=now->ch[]->size+now->ex,now=now->ch[];
return ret;
}
void del(ScapeGoat_Tree *p,int k)
{
p->size--;
if(p->ex&&p->ch[]->size+==k)
{
p->ex=;
return;
}
if(p->ch[]->size>=k) del(p->ch[],k);
else del(p->ch[],k-p->ch[]->size-p->ex);
}
inline void Del(ScapeGoat_Tree *&Root,int key)
{
del(Root,Rank_Min(Root,key)+);
if(Root->size<Root->cover*a)rebuild(Root);
}
int n,m,pos[MAXN];
void build(Tree *p)
{
p->mid=(p->l+p->r)>>;
if(p->l==p->r)return;
p->ch[]=new Tree;
p->ch[]->l=p->l;
p->ch[]->r=p->mid;
p->ch[]=new Tree;
p->ch[]->l=p->mid+;
p->ch[]->r=p->r;
build(p->ch[]);
build(p->ch[]);
}
void Ins(Tree *p,int key,int aim)
{
Insert(p->root,key);
if(p->l==p->r)return;
Ins(p->ch[p->mid<aim],key,aim);
}
int query_Max(int l,int r,int key,Tree *p)
{
if(l<=p->l&&p->r<=r)
return Rank_Max(p->root,key);
int tmp=;
if(l<=p->mid)tmp+=query_Max(l,r,key,p->ch[]);
if(p->mid<r)tmp+=query_Max(l,r,key,p->ch[]);
return tmp;
}
int query_Min(int l,int r,int key,Tree *p)
{
if(l<=p->l&&p->r<=r)
return Rank_Min(p->root,key);
int tmp=;
if(l<=p->mid)tmp+=query_Min(l,r,key,p->ch[]);
if(p->mid<r)tmp+=query_Min(l,r,key,p->ch[]);
return tmp;
}
void Delete(Tree *p,int key,int aim)
{
Del(p->root,key);
if(p->l==p->r)return;
Delete(p->ch[p->mid<aim],key,aim);
}
int main()
{
//freopen("nt2011_queue.in","r",stdin);
//freopen("nt2011_queue.out","w",stdout);
Init();
scanf("%d",&n);
root=new Tree;
root->l=;
root->r=n;
build(root);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
pos[i]=x;
Ins(root,x,i);
if(i!=)ans+=query_Max(,i-,x,root);
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
printf("%lld\n",ans);
int x,y;
scanf("%d%d",&x,&y);
if(x!=) ans-=query_Max(,x-,pos[x],root);
if(x!=n) ans-=query_Min(x+,n,pos[x],root);
Delete(root,pos[x],x);
if(y!=) ans-=query_Max(,y-,pos[y],root);
if(y!=n) ans-=query_Min(y+,n,pos[y],root);
Delete(root,pos[y],y);
swap(pos[x],pos[y]);
Ins(root,pos[x],x);
if(x!=) ans+=query_Max(,x-,pos[x],root);
if(x!=n) ans+=query_Min(x+,n,pos[x],root);
Ins(root,pos[y],y);
if(y!=) ans+=query_Max(,y-,pos[y],root);
if(y!=n) ans+=query_Min(y+,n,pos[y],root);
}
printf("%lld\n",ans);
return ;
}