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

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int size,key,fix;
	node(int x=0):lch(NULL),rch(NULL),size(1),key(x),fix(rand()){}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
	}
}*tr[80005];
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v){
	if(!x){
		x=new node(v);
		return;
	}
	if(v<=x->key){
		insert(x->lch,v);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline void del(node *&x,int v){
	if(x->key==v){
		if(x->lch&&x->rch){
			if(x->lch->fix<x->rch->fix){
				right_rotate(x);
				del(x->rch,v);
			}
			else{
				left_rotate(x);
				del(x->lch,v);
			}
		}
		else{
			node *tmp(NULL);
			if(x->lch)
				tmp=x->lch;
			else
				tmp=x->rch;
			delete x;
			x=tmp;
		}
	}
	else{
		if(v<=x->key)
			del(x->lch,v);
		else
			del(x->rch,v);
	}
	if(x)
		x->pushup();
}
inline int qmin(node *now,int x){
	int ret(0);
	while(now){
		if(x<=now->key)
			now=now->lch;
		else
			ret+=get_size(now->lch)+1,now=now->rch;
	}
	return ret;
}
inline int qmax(node *now,int x){
	int ret(0);
	while(now){
		if(x>=now->key)
			now=now->rch;
		else
			ret+=get_size(now->rch)+1,now=now->lch;
	}
	return ret;
}
int n,m,ans,size;
int a[20005],num[20005],bittree[20005];
inline int lowbit(int x){
	return x&-x;
}
inline void update(int pos){
	while(pos<=n){
		++bittree[pos];
		pos+=lowbit(pos);
	}
}
inline int sum(int pos){
	int ret(0);
	while(pos){
		ret+=bittree[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
inline void build(int l,int r,int rt){
	for(int i=l;i<=r;++i)
		insert(tr[rt],a[i]);
	if(l==r)return;
	int mid((l+r)>>1);
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
inline void update(int pos,int las,int w,int l,int r,int rt){
//	cout<<pos<<' '<<l<<' '<<r<<' '<<w<<endl;
	del(tr[rt],las);
	insert(tr[rt],w);
	if(l==r)return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(pos,las,w,l,mid,rt<<1);
	else
		update(pos,las,w,mid+1,r,rt<<1|1);
}
inline int qmax(int ll,int rr,int w,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return qmax(tr[i],w);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)
		ret+=qmax(ll,rr,w,l,mid,i<<1);
	if(mid<rr)
		ret+=qmax(ll,rr,w,mid+1,r,i<<1|1);
	return ret;
}
inline int qmin(int ll,int rr,int w,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return qmin(tr[i],w);
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)
		ret+=qmin(ll,rr,w,l,mid,i<<1);
	if(mid<rr)
		ret+=qmin(ll,rr,w,mid+1,r,i<<1|1);
	return ret;
}
int main(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	srand(time(NULL));
	n=read();
	for(int i=1;i<=n;++i)
		num[i]=a[i]=read();
	sort(num+1,num+n+1);
	size=unique(num+1,num+n+1)-num-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(num+1,num+size+1,a[i])-num;
		ans+=sum(n)-sum(a[i]);
		update(a[i]);
//		cout<<i<<' '<<a[i]<<endl;
	}
	printf("%d\n",ans);
	build(1,n,1);
	m=read();
	while(m--){
		int x(read()),y(read());
		if(a[x]==a[y]){
			printf("%d\n",ans);
			continue;
		}
		int tmp(0);
		if(x>y)
			swap(x,y);
		if(a[x]>a[y])
			tmp=1;
		else
			tmp=-1;
		int tp1(0),tp2(0),tp3(0),tp4(0),tp5(0),tp6(0),tp7(0),tp8(0);
		if(x!=1)tp1=qmax(1,x-1,a[x],1,n,1);
		if(y!=1)tp2=qmax(1,y-1,a[y],1,n,1);
		if(x!=n)tp3=qmin(x+1,n,a[x],1,n,1);
		if(y!=n)tp4=qmin(y+1,n,a[y],1,n,1);
		int gg1(a[x]),gg2(a[y]);
		update(x,gg1,gg2,1,n,1),update(y,gg2,gg1,1,n,1);
//		cout<<"last array"<<endl;
//		for(int i=1;i<=n;++i)
//			cout<<a[i]<<' ';
//		cout<<endl;
		swap(a[x],a[y]);
		if(x!=1)tp5=qmax(1,x-1,a[x],1,n,1);
		if(y!=1)tp6=qmax(1,y-1,a[y],1,n,1);
		if(x!=n)tp7=qmin(x+1,n,a[x],1,n,1);
		if(y!=n)tp8=qmin(y+1,n,a[y],1,n,1);
//		cout<<"now array"<<endl;
//		for(int i=1;i<=n;++i)
//			cout<<a[i]<<" ";
//		cout<<endl;
//		cout<<ans<<' '<<tp1<<' '<<tp2<<' '<<tp3<<' '<<tp4<<' '<<tp5<<' '<<tp6<<' '<<tp7<<" "<<tp8<<endl;
		ans=ans-tp1-tp2-tp3-tp4+tp5+tp6+tp7+tp8+tmp;
		printf("%d\n",ans);
	}
}