记录编号	482442	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	xzz_666	是否通过	通过
代码语言	C++	运行时间	0.815 s
提交时间	2018-01-08 20:14:04	内存使用	27.22 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
#define lb(o) ((o)&-(o))
typedef long long ll;
il int gi(){
	rg int x=0,f=1;rg char ch=getchar();
	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int maxn=20001;
int h[maxn],H[maxn];
int root[maxn],ls[2333333],rs[2333333],sum[2333333],id;
#define mid ((l+r)>>1)
il vd Update(int&x,int l,int r,const int&p,const int&k){
	if(!x)x=++id;sum[x]+=k;
	if(l==r)return;
	if(p<=mid)Update(ls[x],l,mid,p,k);
	else Update(rs[x],mid+1,r,p,k);
	sum[x]=sum[ls[x]]+sum[rs[x]];
}
il int Query(const int&x,int l,int r,const int&L,const int&R){
	if(L<=l&&r<=R)return sum[x];
	if(!x||R<l||r<L||!sum[x]||L>R)return 0;
	return Query(ls[x],l,mid,L,R)+Query(rs[x],mid+1,r,L,R);
}
int main(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	int n=gi(),m,q,a,b;
	for(rg int i=1;i<=n;++i)h[i]=H[i]=gi();
	std::sort(H+1,H+n+1);m=std::unique(H+1,H+n+1)-H-1;
	for(rg int i=1;i<=n;++i)h[i]=std::lower_bound(H+1,H+m+1,h[i])-H;
	for(rg int i=1;i<=n;++i)
		for(rg int j=i;j<=n;j+=lb(j))
			Update(root[j],1,m,h[i],1);
	long long ans=0;
	for(rg int i=1;i<=n;++i)
		for(rg int j=i-1;j;j-=lb(j))
			ans+=Query(root[j],1,m,h[i]+1,m);
	printf("%lld\n",ans);
	q=gi();while(q--){
		a=gi(),b=gi();
		if(a>b)std::swap(a,b);

		if(h[a]<h[b]){
			++ans;
			for(rg int j=b-1;j;j-=lb(j))ans+=Query(root[j],1,m,h[a],h[b])+Query(root[j],1,m,h[a]+1,h[b]-1);
			for(rg int j= a ;j;j-=lb(j))ans-=Query(root[j],1,m,h[a],h[b])+Query(root[j],1,m,h[a]+1,h[b]-1);
		}else if(h[a]>h[b]){
			--ans;
			for(rg int j=b-1;j;j-=lb(j))ans-=Query(root[j],1,m,h[b],h[a])+Query(root[j],1,m,h[b]+1,h[a]-1);
			for(rg int j= a ;j;j-=lb(j))ans+=Query(root[j],1,m,h[b],h[a])+Query(root[j],1,m,h[b]+1,h[a]-1);
		}
		
		for(rg int j=a;j<=n;j+=lb(j))Update(root[j],1,m,h[a],-1),Update(root[j],1,m,h[b],1);
		for(rg int j=b;j<=n;j+=lb(j))Update(root[j],1,m,h[b],-1),Update(root[j],1,m,h[a],1);
		std::swap(h[a],h[b]);
		
		printf("%lld\n",ans);
	}
	return 0;
}