记录编号	147085	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	Foenix	是否通过	通过
代码语言	C++	运行时间	5.168 s
提交时间	2015-01-24 13:00:02	内存使用	42.37 MiB

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=100005;
inline int Get(){
	int x;char ch;bool bo=false;
	while(!isdigit(ch=getchar()))if(ch=='-')break;
	if(ch=='-')bo=true;
	else x=ch-48;
	while(isdigit(ch=getchar()))x=x*10+ch-48;
	return bo==true? (-x):x;
}
struct NODE{
	int x,pos;bool bo;
}A[MAXN];
bool flag[MAXN];
LL ans;
int n,m,b[MAXN],c[MAXN],block,st[MAXN],en[MAXN],sum,belong[MAXN],pre[MAXN],x,pos[MAXN*100],nowst[MAXN];
void reset(int x){
	for(int i=st[x];i<=en[x];i++)pre[i]=A[i].x;
	sort(pre+st[x],pre+en[x]+1);
}
void Build(){
	for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;//i的所属 
	for(int i=1;i<=sum;i++){
		st[i]=(i-1)*block+1;en[i]=min(i*block,n);
		nowst[i]=st[i]; reset(i);
	}
}
void Guibingsort(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	Guibingsort(l,mid); Guibingsort(mid+1,r);
	int i=l,j=mid+1,now=l;
	while(i<=mid&&j<=r){
		if(b[i]<=b[j])c[now++]=b[i],i++;
		else{
			ans+=mid-i+1;
			c[now++]=b[j];j++;
		}
	}
	while(i<=mid)c[now++]=b[i],i++;
	while(j<=r)c[now++]=b[j],j++;
	for(int i=l;i<=r;i++)b[i]=c[i];
}
LL findmax(int v,int x){
	LL l=st[v],r=en[v],mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(pre[mid]<x)l=mid+1;
		else r=mid-1;
	}
	return en[v]-r;
}
int findmin(int v,LL x){
	int l=st[v],r=en[v],mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(pre[mid]<x)l=mid+1;
		else r=mid-1;
	}
	return r-(nowst[v]-1);
}
LL Ask(int t,int x){
	LL tmp=0,v;
	for(v=1;v<=sum;v++){
		if(belong[t]==v)break;
		tmp+=findmax(v,x);
	}
	for(int i=st[belong[t]];i<=en[belong[t]];i++){
		if(A[i].x<x&&A[i].pos>t&&A[i].bo==false)tmp++;
		if(A[i].x>x&&A[i].pos<t&&A[i].bo==false)tmp++;
	}
	for(v+=1;v<=sum;v++)tmp+=findmin(v,x);
	return tmp;
}
void change(int t){
	A[t].x=0; A[t].bo=true; for(int i=st[belong[t]];i<=en[belong[t]];i++)pre[i]=A[i].x;
	sort(pre+st[belong[t]],pre+en[belong[t]]+1);
	nowst[belong[t]]++;
}
int main(){
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	n=Get();m=Get();
	block=(int)sqrt(n);
	if(n%block)sum=n/block+1;
	else sum=n/block;
	for(int i=1;i<=n;i++)A[i].x=Get(),b[i]=A[i].x,pos[A[i].x]=i,A[i].pos=i;
	Build(); Guibingsort(1,n);
	for(int i=1;i<=m;i++){
		x=Get(); printf("%lld\n",ans);
		ans-=Ask(pos[x],x);
		change(pos[x]);
	}
}