记录编号	153260	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	2.152 s
提交时间	2015-03-17 17:25:27	内存使用	6.71 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot,tim=1,c[21000],h[21000],a[21000],ans[21000];
struct node{
	int id,x,y,v;
}q[200000],q0[200000];
bool cmp(node a,node b){
	if(a.x==b.x) return a.id<b.id;
	return a.x<b.x;
}
void in(int &x){
	int ch;
	while((ch=getchar())<48);x=ch-48;
	while((ch=getchar())>47) x=x*10+ch-48;
}
void add(int id,int x,int y,int w){
	if(w==1){
		q[++tot]=(node){id,x-1,tim,w};
		q[++tot]=(node){id,x-1,y,-w};
		q[++tot]=(node){id,n,y-1,w};
		q[++tot]=(node){id,x,y-1,-w};	
		q[++tot]=(node){-1,x,y,w};
	}
	else{
		q[++tot]=(node){-1,x,y,w};
		q[++tot]=(node){id,x-1,tim,w};
		q[++tot]=(node){id,x-1,y,-w};
		q[++tot]=(node){id,n,y-1,w};
		q[++tot]=(node){id,x-1,y-1,-w};	
	}
}
void modify(int i,int x){
	while(i<=tim) c[i]+=x,i+=i&-i;
}
int query(int i){
	int res=0;
	while(i) res+=c[i],i-=i&-i;
	return res;
} 
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1,cnt=0;
	for(int i=l;i<=mid;i++) if(q[i].id==-1) q0[++cnt]=q[i];
	for(int i=mid+1;i<=r;i++)if(q[i].id!=-1)q0[++cnt]=q[i];
	sort(q0+1,q0+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
		if(q0[i].id==-1) modify(q0[i].y,q0[i].v);
		else ans[q0[i].id]+=query(q0[i].y)*q0[i].v;
	for(int i=1;i<=cnt;i++) if(q0[i].id==-1) modify(q0[i].y,-q0[i].v);
	solve(l,mid),solve(mid+1,r);
}
int main(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	in(n);
	for(int i=1;i<=n;i++) in(h[i]),a[i]=h[i];
	sort(h+1,h+n+1),tim=1;
	for(int i=2;i<=n;i++) if(h[i]!=h[i-1]) h[++tim]=h[i];
	for(int i=1;i<=n;i++) a[i]=lower_bound(h+1,h+tim+1,a[i])-h;
	for(int i=1;i<=n;i++) add(0,i,a[i],1);
	in(m);
	for(int x,y,i=1;i<=m;i++){
		in(x),in(y);
		if(a[x]==a[y]) continue;
		add(i,x,a[x],-1),add(i,y,a[y],-1);
		add(i,x,a[y],1), add(i,y,a[x],1);
		swap(a[x],a[y]);
	}
	solve(1,tot),printf("%d\n",ans[0]);
	for(int i=1;i<=m;i++) ans[i]+=ans[i-1],printf("%d\n",ans[i]);
}