记录编号	364144	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.423 s
提交时间	2017-01-15 16:01:30	内存使用	43.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int _size_=20<<20;
char is[_size_],*pi=is,os[_size_],*po=os;
template<class T>inline void readint(T &x){
	x=0;
	while(*pi<48)pi++;
	while(*pi>47)x=(x<<1)+(x<<3)+(*pi++^48);
}
template<class T>inline void writeint(T x){
	static int a[25],i;
	if(!x)*po++='0';
	else{
		i=0;
		while(x){
			a[++i]=x%10;
			x/=10;
		}
		while(i)*po++=a[i--]^48;
	}
}
const int maxn=100010,maxm=50010;
struct A{int x,y,t;}a[maxm],b[maxm];
void CDQ(int,int);
void add(int,int);
int query(int);
int seq[maxn],pos[maxn],c[maxn]={0},t[maxn]={0};
long long ans[maxm]={0};
int n,m;
int main(){
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	fread(is,sizeof(is),sizeof(char),stdin);
	readint(n);readint(m);
	for(int i=1;i<=n;i++){
		readint(seq[i]);
		pos[seq[i]]=i;
	}
	for(int i=1;i<=m;i++){
		readint(a[i].x);
		a[i].y=a[i].x;
		a[i].x=pos[a[i].x];
		t[a[i].x]=a[i].t=m-i+1;
	}
	for(int i=n;i;i--){
		ans[t[i]]+=query(seq[i]-1);
		if(!t[i])add(seq[i],1);
	}
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++){
		if(t[i])ans[t[i]]+=query(n)-query(seq[i]);
		else add(seq[i],1);
	}
	memset(c,0,sizeof(c));
	reverse(a+1,a+m+1);
	CDQ(1,m);
	for(int i=1;i<=m;i++)ans[i]+=ans[i-1];
	for(int i=m;i;i--){
		writeint(ans[i]);
		*po++='\n';
	}
	fwrite(os,po-os,sizeof(char),stdout);
	return 0;
}
void CDQ(int l,int r){
	if(l>=r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){//正着扫一遍，统计第一种情况
		if(a[i].x<a[j].x){
			add(a[i].y,1);
			b[k++]=a[i++];
		}
		else{
			ans[a[j].t]+=i-l-query(a[j].y);
			b[k++]=a[j++];
		}
	}
	while(i<=mid){
		add(a[i].y,1);
		b[k++]=a[i++];
	}
	while(j<=r){
		ans[a[j].t]+=i-l-query(a[j].y);
		b[k++]=a[j++];
	}
	copy(b+l,b+r+1,a+l);
	for(i=l;i<=r;i++)if(a[i].t<=mid)add(a[i].y,-1);//清空树状数组
	for(i=r;i>=l;i--){//序列已经按照x排好序，倒着扫一遍，统计第二种情况
		if(a[i].t<=mid)add(a[i].y,1);
		else ans[a[i].t]+=query(a[i].y-1);
	}
	for(i=l;i<=r;i++)if(a[i].t<=mid)add(a[i].y,-1);//清空树状数组
}
inline void add(int x,int d){
	while(x<=n){
		c[x]+=d;
		x+=x&-x;
	}
}
inline int query(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x&=x-1;
	}
	return ans;
}
/*
首先时光倒流，删除操作变成了插入操作。
每个元素抽象为三元组(x,y,t)，设t1<t2，两个元素在t2时刻产生逆序对有两种情况：
1.x1<x2 && y1>y2
2.x1>x2 && y1<y2
初始就有的元素t为0，先求出初始逆序对和插入的元素和原序列产生的逆序对，
然后对t分治，内层对x排序，正反各扫一遍，树状数组维护y即可。
*/