记录编号	344660	评测结果	AAAAAAAATT
题目名称	[CQOI2011]动态逆序对	最终得分	80
用户昵称	小一米	是否通过	未通过
代码语言	C++	运行时间	10.291 s
提交时间	2016-11-10 14:34:29	内存使用	57.97 MiB

#include<cstdio>
#include<iostream>
#include<cstring> 
#define M 100003
#define LL long long
int n,m,cnt;
int root[M],pos[M],a[M],opt[M];
bool vis[M];
LL ans[M];
int in()
{
    int t=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') t=(t<<1)+(t<<3)+ch-48,ch=getchar();
    return t;
}
namespace Seg
{
	int tr[M*70],ls[M*70],rs[M*70];
	void update(int rt,int begin,int end,int pos)
	{
		++tr[rt];
		if (begin==end) return;
		int mid=(begin+end)>>1;
		if (pos<=mid)
		{
			if (!ls[rt]) ls[rt]=++cnt;
			update(ls[rt],begin,mid,pos);
		}
		else
		{
			if (!rs[rt]) rs[rt]=++cnt;
			update(rs[rt],mid+1,end,pos);
		}
	}
	int get(int rt,int begin,int end,int l,int r)
	{
		if (!rt) return 0;
		if (l<=begin&&end<=r) return tr[rt];
		int mid=(begin+end>>1),ans=0;
		if (mid>=l) ans+=get(ls[rt],begin,mid,l,r);
		if (mid<r) ans+=get(rs[rt],mid+1,end,l,r);
		return ans;
	}
}
namespace BIT//维护某一个前缀内的权值情况 
{
	void update(int x,int val)
	{
		for (;x<=n;x+=(x&-x))
		{ 
			if (!root[x]) root[x]=++cnt;
			Seg::update(root[x],1,n,val);
		}
	}
	int get(int x,int l,int r)
	{
		int t=0;
		for (;x;x-=(x&-x))
			t+=Seg::get(root[x],1,n,l,r);
		return t;
	}
}
main()
{
		freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	n=in();m=in();
	for (int i=1;i<=n;++i) pos[a[i]=in()]=i;
	for (int i=1;i<=m;++i) vis[opt[i]=in()]=1;
	int p=m;
	for (int i=1;i<=n;++i)
		if (!vis[i])
			opt[++m]=i;
	for (int i=1;i<=m>>1;++i) std::swap(opt[i],opt[m-i+1]);
	for (int i=1;i<=m;++i)
		BIT::update(pos[opt[i]],opt[i]),
		ans[i]=BIT::get(pos[opt[i]]-1,opt[i],n)-BIT::get(pos[opt[i]],1,opt[i])+BIT::get(n,1,opt[i]);
	for (int i=1;i<=m;++i) ans[i]+=ans[i-1];
	for (int i=m;i>=m-p+1;--i) printf("%lld\n",ans[i]);
}