记录编号	150628	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.740 s
提交时间	2015-03-02 08:59:18	内存使用	14.12 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 3295: [Cqoi2011]动态逆序对
* ALG    : 树状数组
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

typedef unsigned int uint ;

#define READ
#ifdef  READ
	char ch[5000000],buf[5000000],*pi=ch,*po=buf;
	char GetChar(){return *pi++;}
#endif
void out(uint x){
	if(!x) *po++='0';
	int p=0;
	char buff[20];
	while(x) buff[++p]=x%10+'0',x/=10;
	while(p) *po++=buff[p--];
	*po++='\n';
}

int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=GetChar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = GetChar() ;
    while (ret = ret*10+CH-'0' , CH=GetChar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  maxn  100010LL
#define  lb    (p&(-p))

int  n , m ;

struct POINT { int x , y , z ; } A[maxn] , B[maxn] ;
uint C[maxn] = {0} ;
void Insert(int p) {for(;p<=n;p+=lb)C[p]++;}
uint Query(int p) {uint ret=0;for(;p;p-=lb)ret+=C[p];return ret;}
void Clear(int p) {for(;p<=n;p+=lb)C[p]=0;}
uint f[maxn] = {0} ;

void cdq(int L , int R) {
	if (L == R) return ;
	int M = L+(R-L)/2 , i , p = L , q = M+1 ;
	cdq(L,M) , cdq(M+1,R) ;
	for (i = L ; i <= R ; i ++ )
		B[i] = A[(q>R||(p<=M&&A[p].y<A[q].y))?p++:q++] ;
	for (i = L ; i <= R ; i ++ ) {
		A[i] = B[i] ;
		if (A[i].x <= M) Insert(A[i].z) ;
		else f[A[i].x] += Query(A[i].z) ;
	}
	for (i = L ; i <= R ; i ++ )
		if (A[i].x <= M) Clear(A[i].z) ;
}

int tim[maxn] = {0} , del[maxn] = {0} ;
bool flag[maxn] = {false} ;
uint ans[maxn] = {0} ;

int main() {
int i , k ;
	#ifdef  READ
		freopen("inverse.in" ,"r",stdin ) ;
		freopen("inverse.out","w",stdout) ;
		fread(ch,1,5000000,stdin);
	#endif
	read(n) , read(m) ;
	for (i = 1 ; i <= n ; i ++ )
		read(k) , tim[k] = i ;
	for (i = 1 ; i <= m ; i ++ )
		read(del[i]) , flag[del[i]] = true ;
	for (k = m , i = 1 ; i <= n ; i ++ )
		if (!flag[i]) del[++k] = i ;
	for (k = 0 , i = n ; i ; i -- )
		A[++k] = (POINT) { n-i+1,n-del[i]+1,tim[del[i]] } ;
	cdq(1,n) ;
	for (k = 0 , i = n ; i ; i -- )
		A[++k] = (POINT) { n-i+1,del[i],n+1-tim[del[i]] } ;
	cdq(1,n) ;
	for (i = 1 ; i <= n ; i ++ ) ans[i] = ans[i-1]+f[i] ;
	for (i = 1 ; i <= m ; i ++ ) out(ans[n-i+1]) ;
	#ifdef  READ
 	    fwrite(buf , 1 , po-buf , stdout) ;
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
}