记录编号	430250	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.346 s
提交时间	2017-07-29 16:02:30	内存使用	0.47 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=2e4+10;
const int qrt=150;
int n,m,bl,ans,qr;
int beg[qrt],bend[qrt],val[M],sval[M],c[M],block[M];
inline int read(){
	int 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<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void init(){
	for(int i=1;i<=bl;i++) beg[i]=(i-1)*qr+1,bend[i]=i*qr;
	bend[bl]=n;
}
inline void lisan(){
	sort(sval+1,sval+n+1);
	for(int i=1;i<=n;i++)
		val[i]=lower_bound(sval+1,sval+1+n,val[i])-sval;
}
inline int lb(int x){return x&(-x);}
inline void update(int x){while(x<=n)c[x]++,x+=lb(x);}
inline int getnum(int x){
	int temp=0;
	while(x){
		temp+=c[x];
		x-=lb(x);
	}return temp;
}
inline void new_sval(){
	for(int i=1;i<=bl;i++){
		for(int j=beg[i];j<=bend[i];j++) sval[j]=val[j];
		sort(sval+beg[i],sval+bend[i]+1);
	}
}
inline void getans(){
	for(int i=n;i>=1;i--){
		ans+=getnum(val[i]-1);
		update(val[i]);
	}
}
inline void rt_new(int x){
	for(int i=beg[x];i<=bend[x];i++) sval[i]=val[i];
	sort(sval+beg[x],sval+bend[x]+1);
}
inline void query(int l,int r){
	if(val[l]==val[r]) return ;
	int le=block[l],ri=block[r];
	if(val[l]<val[r]) ans++;
	else ans--;
	if(le==ri){
		for(int i=l+1;i<r;i++){
			if(val[l]>val[i]) ans--;
			if(val[l]<val[i]) ans++;
			if(val[r]>val[i]) ans++;
			if(val[r]<val[i]) ans--;
		}
		swap(val[l],val[r]);
		rt_new(le);rt_new(ri);return ;
	}
	for(int i=l+1;i<=bend[le];i++){
		if(val[l]>val[i]) ans--;
		if(val[l]<val[i]) ans++;
		if(val[r]>val[i]) ans++;
		if(val[r]<val[i]) ans--;
	}
	for(int i=beg[ri];i<r;i++){
		if(val[l]>val[i]) ans--;
		if(val[l]<val[i]) ans++;
		if(val[r]>val[i]) ans++;
		if(val[r]<val[i]) ans--;
	}
	for(int i=le+1;i<=ri-1;i++){
		int lef=lower_bound(sval+beg[i],sval+bend[i]+1,val[l])-sval;
		int rig=upper_bound(sval+beg[i],sval+bend[i]+1,val[l])-sval;
		ans+=beg[i]+bend[i]-lef-rig+1;
		lef=lower_bound(sval+beg[i],sval+bend[i]+1,val[r])-sval;
		rig=upper_bound(sval+beg[i],sval+bend[i]+1,val[r])-sval;
		ans+=rig+lef-beg[i]-bend[i]-1;
	}
	swap(val[l],val[r]);
	rt_new(le),rt_new(ri);
}
int DK(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	n=read();qr=sqrt(n+0.5);
	for(int i=1;i<=n;i++) block[i]=(i-1)/qr+1,val[i]=read(),sval[i]=val[i];
	bl=block[n];init();lisan();new_sval();getans();
	printf("%d\n",ans);m=read();
	for(int i=1;i<=m;i++){
		int aa=read(),bb=read();
		if(aa>bb) swap(aa,bb);
		query(aa,bb);
		printf("%d\n",ans);
	}
	return 0;
}
int dk=DK();
int main(){
	;
}