Codeforces 137 C. History

問題

n個の区間が与えられる。
区間のうち、他の区間に完全に含まれるようなものはいくつあるか、求めよ。

制約条件

n≦10^5
1≦区間の左端、右端≦10^9
区間の左端の値、右端の値は全て異なる

方針

区間を長い順にソート。
左端に対して右端の値が決まるが、
RMQで、自分より左の左端に対しての右端の最大値を求めてやればよい。

RMQは、区間の始点が常に0なのでbinary indexed treeを使うことができる。
座標の値が大きいので座標圧縮をする。

別解がある。
単にソートして、今までの右端の最大値を覚えさえすればよい模様。
気づかなかった。

ソースコード

int n,l[100000],r[100000];
int bit[200010];
pi p[100000];
void add(int i,int x){
	i++;
	for(;i<=200009;i+=i&-i)bit[i]=max(bit[i],x);
}
int sum(int i){
	int res=-1;
	i++;
	for(;i;i-=i&-i)res=max(res,bit[i]);
	return res;
}
bool cmp(pi a,pi b){
	int da=a.second-a.first,db=b.second-b.first;
	if(da!=db)return da>db;
	return a.first<b.first;
}
void run()
{
	cin>>n;
	map<int,int> M;
	rep(i,n){
		cin>>l[i]>>r[i];
		M[l[i]]=M[r[i]]=0;
	}
	int k=0;
	fr(i,M)i->second=k++;
	rep(i,n)p[i]=mp(M[l[i]],M[r[i]]);
	sort(p,p+n,cmp);
	
	memset(bit,-1,sizeof(bit));
	int ans=0;
	rep(i,n){
		int a=p[i].first,b=p[i].second;
		if(sum(a)>=b)ans++;
		add(a,b);
	}
	cout<<ans<<endl;
}