记录编号	394623	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013][HZOI 2016]删除物品	最终得分	100
用户昵称	Albert S. Chang	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2017-04-13 20:27:06	内存使用	0.96 MiB

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <stdexcept>
#include <algorithm>
using namespace std;

const int INF=0x7FFFFFFF;
const int MAXN=100010;

int n;
int s;
int ln;
int rn;
int ans;
int c[MAXN];
int d[MAXN];
int pos[MAXN];
int data[MAXN];
bool deleted[MAXN];

void Initialize();
int LowBit(int);
int Query(int);
void Add(int);
void Update();

int Main(){
	Initialize();
	for(int i=n;i>0;i--){
		if(pos[i]>s){
			ans+=pos[i]-s-1+Query(s)-Query(pos[i]);
			s=pos[i];
		}
		else{
			ans+=s-pos[i]+Query(pos[i])-Query(s);
			s=pos[i];
		}
		Add(pos[i]);
		deleted[i]=true;
		Update();
	}
	printf("%d\n",ans);
	return 0;
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("hzoi_remove.in","r",stdin);
	freopen("hzoi_remove.out","w",stdout);
#endif
	scanf("%d%d",&ln,&rn);
	n=ln+rn;
	s=ln;
	for(int i=1;i<=ln;i++){
		scanf("%d",data+i);
		d[i]=data[i];
	}
	reverse(data+1,data+ln+1);
	for(int i=1;i<=rn;i++){
		scanf("%d",data+ln+i);
		d[ln+i]=data[ln+i];
	}
	sort(d+1,d+n+1);
	for(int i=1;i<=n;i++){
		data[i]=lower_bound(d+1,d+n+1,data[i])-d;
		pos[data[i]]=i;
	}
}

inline void Update(){
	while(deleted[data[s]]){
		s--;
	}
}

inline void Add(int x){
	for(;x<=n;x+=LowBit(x)){
		c[x]++;
	}
}

inline int Query(int x){
	int ans=0;
	for(;x>0;x-=LowBit(x)){
		ans+=c[x];
	}
	return ans;
}

inline int LowBit(int x){
	return x&-x;
}

int WORKING=Main();
int main(){;}