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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&seq[i]);
		pos[seq[i]]=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&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--)printf("%lld\n",ans[i]);
	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);//,printf("ans[%d]+=%d\n",ans[a[j].t],i+l-query(a[
		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);//清空树状数组
}
void add(int x,int d){
	while(x<=n){
		c[x]+=d;
		x+=x&-x;
	}
}
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即可。
*/