记录编号	143025	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.780 s
提交时间	2014-12-12 15:39:30	内存使用	13.01 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEN=20010,SIZEB=160;
class BIT{
public:
	int n;
	int s[SIZEN];
	#define lowbit(x) ((x)&(-x))
	void clear(int n_){
		memset(s,0,sizeof(s));
		n=n_;
	}
	void add(int x,int t){
		for(;x<=n;x+=lowbit(x)) s[x]+=t;
	}
	int prefsum(int x){//前缀和
		int ans=0;
		for(;x;x-=lowbit(x)) ans+=s[x];
		return ans;
	}
	int sum(int x,int y){
		if(x>y) return 0;
		return prefsum(y)-prefsum(x-1);
	}
};
int N,H[SIZEN],BN;
int HX[SIZEN]={0};
int sum=0;
BIT T[SIZEB];
int belong[SIZEN];//属于哪一块
int head[SIZEN],tail[SIZEN];
bool valid[SIZEN]={0};//这个姿势真不优美......貌似分块容易写得丑
int calc(int x,int t){//H[x]=t(可能并未赋值),求x对答案的影响
	int ans=0,k=belong[x];
	for(int i=head[k];i<x;i++) ans+=(valid[i]&&H[i]>t);
	for(int i=tail[k];i>x;i--) ans+=(valid[i]&&H[i]<t);
	for(int i=1;i<k;i++) ans+=T[i].sum(t+1,N);
	for(int i=BN;i>k;i--) ans+=T[i].sum(1,t-1);
	return ans;
}
void modify(int a,int b){//交换a,b
	sum-=calc(a,H[a]);
	T[belong[a]].add(H[a],-1);
	valid[a]=false;
	sum-=calc(b,H[b]);
	T[belong[b]].add(H[b],-1);
	valid[b]=false;
	swap(H[a],H[b]);
	sum+=calc(a,H[a]);
	T[belong[a]].add(H[a],1);
	valid[a]=true;
	sum+=calc(b,H[b]);
	T[belong[b]].add(H[b],1);
	valid[b]=true;
}
void work(void){
	int Q,a,b;
	scanf("%d",&Q);
	printf("%d\n",sum);
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&a,&b);
		modify(a,b);
		printf("%d\n",sum);
	}
}
void init(void){
	for(int i=1;i<=N;i++) valid[i]=true;
	int Bsize=sqrt(N+0.5),tot=0;
	BN=1;head[1]=1;
	for(int i=1;i<=N;i++){
		tot++;
		belong[i]=BN;
		if(tot==Bsize||i==N){//一块结尾
			T[BN].clear(N);
			tail[BN]=i;head[BN+1]=i+1;
			tot=0,BN++;
		}
	}
	BN--;
	memcpy(HX,H,sizeof(H));
	sort(HX+1,HX+1+N);
	static BIT s;
	s.clear(N);
	sum=0;
	for(int i=N;i>=1;i--){
		H[i]=lower_bound(HX+1,HX+1+N,H[i])-HX;
		T[belong[i]].add(H[i],1);
		s.add(H[i],1);
		sum+=s.sum(1,H[i]-1);
	}
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&H[i]);
}
int main(){
	freopen("nt2011_queue.in","r",stdin);
	freopen("nt2011_queue.out","w",stdout);
	read();
	init();
	work();
	return 0;
}