记录编号	230204	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	6.878 s
提交时间	2016-02-21 09:53:55	内存使用	49.69 MiB

#include<cstdio>
#include<algorithm>
long long n,m,M,t,cnt,w[310000],id[310000],a[310000],ans[310000];
bool flag[310000];
struct event
{
	long long x,y,t,id,w;
	bool flag;
}o[510000],tmp[510000];
inline bool comp(event a,event b)
{
	if(a.x==b.x&&a.y==b.y)
		return a.flag>b.flag;
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
void build()
{
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;++i)
		scanf("%lld",&w[i]),id[w[i]]=i;
	for(long long j=1;j<=m;++j)
		scanf("%lld",&a[j]),flag[id[a[j]]]=1;
	for(long long i=1;i<=n;++i)
		if(!flag[i])
		{
			o[++t].x=i;
			o[t].t=t;
			o[t].y=w[i];
			o[t].flag=1;
			o[++t].id=++cnt;
			o[t].t=t;
			o[t].x=i;
			o[t].y=n;
			o[t].w=1;
			o[++t].id=cnt;
			o[t].t=t;
			o[t].x=n;
			o[t].y=w[i];
			o[t].w=1;
			o[++t].id=cnt;
			o[t].t=t;
			o[t].x=i;
			o[t].y=w[i];
			o[t].w=-2;
		}
	for(long long i=m;i;--i)
	{
		o[++t].x=id[a[i]];
		o[t].t=t;
		o[t].y=a[i];
		o[t].flag=1;
		o[++t].id=++cnt;
		o[t].t=t;
		o[t].x=id[a[i]];
		o[t].y=n;
		o[t].w=1;
		o[++t].id=cnt;
		o[t].t=t;
		o[t].x=n;
		o[t].y=a[i];
		o[t].w=1;
		o[++t].id=cnt;
		o[t].t=t;
		o[t].x=id[a[i]];
		o[t].y=a[i];
		o[t].w=-2;
	}
}
long long tree[310000];
inline void ADD(long long x,long long w)
{
	for(;x<=n;x+=x&(-x))
		tree[x]+=w;
}
inline long long sum(long long x)
{
	long long end=0;
	for(;x;x-=x&(-x))
		end+=tree[x];
	return end;
}
inline void CDQ(long long l,long long r)
{
	if(l==r)
		return;
	long long mid=l+r>>1,l1=l,l2=mid+1;
	for(long long i=l;i<=r;++i)
	{
		if(o[i].t<=mid&&o[i].flag)
			ADD(o[i].y,1);
		else if(o[i].t>mid&&!o[i].flag)
		{
			if(o[i].id==2)
			{
				++i;
				--i;
			}
			ans[o[i].id]+=sum(o[i].y)*o[i].w;
		}

	}
	for(long long i=l;i<=r;++i)
		if(o[i].t<=mid&&o[i].flag)
			ADD(o[i].y,-1);
	for(long long i=l;i<=r;++i)
		if(o[i].t<=mid)
			tmp[l1++]=o[i];
		else
			tmp[l2++]=o[i];
	for(long long i=l;i<=r;++i)
		o[i]=tmp[i];
	CDQ(l,mid);
	CDQ(mid+1,r);
}
int main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	build();
	std::sort(o+1,o+t+1,comp);
	CDQ(1,t);
	for(long long i=2;i<=cnt;++i)
		ans[i]+=ans[i-1];
	for(long long i=cnt;i>cnt-m;--i)
		printf("%lld\n",ans[i]);
}