记录编号	153113	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	3.950 s
提交时间	2015-03-16 20:12:48	内存使用	20.41 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned int lnt;
const int maxn=100005;
bool del[maxn];
lnt c[maxn],ans[maxn];
int n,m,tot,a[maxn],b[maxn],pos[maxn];
char ci[2000000],co[1000000],*pi=ci,*po=co;
struct ques{int id,x,y,v,p;}q1[maxn<<2],q2[maxn<<2];
bool cmp(ques a,ques b){
	if(a.x==b.x) return a.id<b.id;
	return a.x<b.x;
}
void in(int &x){
	x=0;
	while(*pi<48) pi++;
	while(*pi>47) x=x*10+*pi++-48;
}
void out(lnt x){
	if(!x) {*po++='0',*po++='\n';return;}
	int p=0;char buf[20];
	while(x) buf[++p]=x%10+'0',x/=10;
	while(p) *po++=buf[p--];
	*po++='\n';
}
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1,cnt=0;
	for(int i=l;i<=mid;i++) if(!q1[i].v) q2[++cnt]=q1[i];
	for(int i=mid+1;i<=r;i++) if(q1[i].v)q2[++cnt]=q1[i];
	sort(q2+1,q2+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		if(!q2[i].v) for(int j=q2[i].y;j<=n;j+=j&-j) c[j]++;
		else{
			lnt res=0;
			for(int j=q2[i].y;j;j-=j&-j) res+=c[j];
			ans[q2[i].p]+=res*q2[i].v;
		}
	}
	for(int i=1;i<=cnt;i++)
		if(!q2[i].v) 
			for(int j=q2[i].y;j<=n;j+=j&-j) c[j]--;
	solve(l,mid),solve(mid+1,r);
}
int main(){
	freopen("inverse.in" ,"r",stdin ) ;
	freopen("inverse.out","w",stdout) ;
	fread(ci,1,2000000,stdin);
	in(n),in(m);
	for(int i=1;i<=n;i++) in(a[i]),pos[a[i]]=i;
	for(int i=1,k;i<=m;i++) in(b[i]),del[pos[b[i]]]=1;
	for(int i=1;i<=n;i++) 
		if(!del[i]){
			tot++,q1[tot]=(ques){tot,n,a[i]-1,1,0};
			tot++,q1[tot]=(ques){tot,i-1,n,1,0};
			tot++,q1[tot]=(ques){tot,i-1,a[i]-1,-2,0};
			tot++,q1[tot]=(ques){tot,i,a[i],0,0};
		}
	for(int i=m;i;i--){
		tot++,q1[tot]=(ques){tot,n,b[i]-1,1,i};
		tot++,q1[tot]=(ques){tot,pos[b[i]]-1,n,1,i};
		tot++,q1[tot]=(ques){tot,pos[b[i]]-1,b[i]-1,-2,i};
		tot++,q1[tot]=(ques){tot,pos[b[i]],b[i],0,i};
	}
	solve(1,tot);
	ans[m+1]=ans[0];
	for(int i=m;i;i--) ans[i]+=ans[i+1];
	for(int i=1;i<=m;i++) out(ans[i]);
	fwrite(co,1,po-co,stdout);
}