记录编号	317825	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	河北交通广播992小强来了	是否通过	通过
代码语言	C++	运行时间	6.649 s
提交时间	2016-10-08 16:26:22	内存使用	3.44 MiB

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
#define LL long long
const int maxn=100010;
LL a[maxn],b[330][330],n,m,kk,l[330],r[330],bel[maxn],cnt,pos[maxn],tot,back[maxn],ans,ma;
bool flag[maxn];
LL get(LL);
void Up(LL);
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
LL Find(LL,LL);
int Main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	scanf("%lld%lld",&n,&m);kk=sqrt(n+0.0);l[1]=1;cnt=1;
	for(int i=1;i<=n;i++)
	{
		bel[i]=cnt;a[i]=read();pos[a[i]]=i;tot++;b[cnt][tot]=a[i];ma=max(ma,a[i]);ans+=get(a[i]+1);Up(a[i]);
		if(i%kk==0)tot=0,r[cnt]=i,b[cnt][0]=kk,sort(b[cnt]+1,b[cnt]+kk+1),cnt++,l[cnt]=i+1;
	}
	if(n%kk!=0)r[cnt]=n,b[cnt][0]=(r[cnt]-l[cnt]+1),sort(b[cnt]+1,b[cnt]+b[cnt][0]+1);
	else cnt--;
	for(int i=1;i<=m;i++)
	{
		printf("%lld\n",ans);
		int x;x=read();
		int st=l[bel[pos[x]]],ed=r[bel[pos[x]]];
		for(int j=st;j<pos[x];j++)
		{
			if(flag[a[j]])continue;
			if(a[j]>x)ans--;
		}
		for(int j=pos[x]+1;j<=ed;j++)
		{
			if(flag[a[j]])continue;
			if(x>a[j])ans--;
		}
		for(int j=bel[pos[x]]+1;j<=cnt;j++)
		{
			if(!b[j][0])continue;
			LL ttt=Find(x,j);ttt--;if(ttt<=0)continue;
			ans-=(ttt-1+1);
		}
		for(int j=1;j<bel[pos[x]];j++)
		{
			if(!b[j][0])continue;
			LL ttt=Find(x,j);if(ttt>b[j][0])continue;//printf("---------back==%d----%d-\n",ttt,b[j][ttt]);
			ans-=(b[j][0]-ttt+1);
		}
		LL ttt=Find(x,bel[pos[x]]);//printf("exact=======%d\n",ttt);
		flag[x]=1;b[bel[pos[x]]][ttt]=0x7f7f7f7f;sort(b[bel[pos[x]]]+1,b[bel[pos[x]]]+b[bel[pos[x]]][0]+1);
		b[bel[pos[x]]][0]--;
	}//while(1);//system("pause");
	//printf("%f\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}
LL get(LL x)
{
	LL an=0;
	for(int i=x;i<=ma;i+=(i&(-i)))an+=back[i];
	return an;
}
void Up(LL x)
{
	for(int i=x;i>0;i-=(i&(-i)))back[i]+=1;
}
LL Find(LL x,LL j)
{
	LL l=1,r=b[j][0];
	while(l<=r)
	{
		LL mid=(l+r)>>1;
		if(b[j][mid]<x)l=mid+1;
		else r=mid-1;
	}
	return l;
}
int start=Main();
int main(){;}