记录编号	323524	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.579 s
提交时间	2016-10-16 19:10:03	内存使用	0.97 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*f;
}
const ll maxn=20100;
ll n,m,size,c[maxn],fen[maxn];
ll block[maxn],b[maxn],a[maxn];
ll ans;
ll query(ll x){ll s=0;for(ll i=x;i;i-=i&-i)s+=fen[i];return s;}
void add(ll x){for(ll i=x;i<=n;i+=i&-i) fen[i]++;}

void resort(ll i){
	ll l=(i-1)*size+1,r=min(i*size,n);
	for(ll i=l;i<=r;i++) b[i]=c[i];
	sort(b+l,b+r+1);
}
ll query(ll l,ll r,ll x){
	if(l>r)return 0;
	ll bl=block[l],br=block[r],rec=0;
	if(bl==br){
		for(ll i=l;i<=r;i++) if(c[i]>x) rec++;
		return rec;
	}else{
		for(ll i=l;block[i]==bl;i++)if(c[i]>x)rec++;
		for(ll i=r;block[i]==br;i--)if(c[i]>x)rec++;
		for(ll i=bl+1;i<br;i++){
			ll ml=(i-1)*size+1,mr=min(n,i*size);
			rec+=mr-ml+1-(upper_bound(b+ml,b+mr+1,x)-(b+ml-1));
		}
		return rec;
	}
}
ll query2(ll l,ll r,ll x){
	if(l>r)return 0;
	ll bl=block[l],br=block[r],rec=0;
	if(bl==br){
		for(ll i=l;i<=r;i++) if(c[i]<x) rec++;
		return rec;
	}else{
		for(ll i=l;block[i]==bl;i++)if(c[i]<x)rec++;
		for(ll i=r;block[i]==br;i--)if(c[i]<x)rec++;
		for(ll i=bl+1;i<br;i++){
			ll ml=(i-1)*size+1,mr=min(n,i*size);
			rec+=lower_bound(b+ml,b+mr+1,x)-(b+ml-1)-1;
		}
		return rec;
	}
}
void modify(ll l,ll r){
	if(c[l]>c[r]) ans--;
	if(c[r]>c[l]) ans++;
	ll aa=0,bb=0,cc=0,dd=0;
	if(r-1>=l+1){
		aa=query(l+1,r-1,c[l]),cc=query2(l+1,r-1,c[l]);
		bb=query(l+1,r-1,c[r]),dd=query2(l+1,r-1,c[r]);
	}
	ans=ans+aa-cc+dd-bb;
	swap(c[l],c[r]);
	resort(block[l]);resort(block[r]);
}
int main(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	n=read(),size=sqrt(n);
	for(ll i=1;i<=n;i++) c[i]=a[i]=read();
	sort(a+1,a+n+1);
	for(ll i=1;i<=n;i++){
		c[i]=lower_bound(a+1,a+n+1,c[i])-a;
		block[i]=(i-1)/size+1;
	}
	for(int i=n;i>=1;i--)
		ans+=query(c[i]-1),add(c[i]);
	memset(b,0,sizeof b);
	for(ll i=1;i<=block[n];i++) resort(i);
	m=read();
	printf("%lld\n",ans);
	for(ll i=1;i<=m;i++){
		ll a=read(),b=read();
		if(a>b)swap(a,b);
		modify(a,b);
		printf("%lld\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}