1800*D. Nested Segments（数组数组&&离散化）

 解析：

        按照右端点进行排序，这样某个区间包含的区间只能是在其前面的区间中。

        所以维护左端点 x 的出现次数，这样我们在查询某个区间 x，y 的时候，只需要求 x-y 之间包含多少个前面区间的 x 即可（前缀和），因为 前面区间的 y 显然小于当前区间的 y。

        树状数组维护，可以 logn 内求出前缀和。

        其中存在负数，所以需要离散化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=4e5+5;
int n,m,res[N];
int b[M],c[M],idx;
struct node{
	int id,x,y;
	bool operator<(const node& t)const{
		return y==t.y?x>t.x:y<t.y; 
	}
}a[N];
int lowbit(int x){return x&-x;}
void add(int k){
	for(int i=k;i<=m;i+=lowbit(i)) c[i]+=1;
}
int sum(int x,int y){
	int ans=0;
	for(int i=y;i;i-=lowbit(i)) ans+=c[i];
	for(int i=x-1;i;i-=lowbit(i)) ans-=c[i];
	return ans;
}
map<int,int>mp;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[i]={i,x,y};	
		b[++idx]=x;
		b[++idx]=y;
	}
	sort(b+1,b+idx+1);	//排序及其离散化 
	m=unique(b+1,b+idx+1)-(b+1);
	for(int i=1;i<=m;i++) 
		mp[b[i]]=i;		//映射 
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		int x=a[i].x,y=a[i].y;
		res[a[i].id]=sum(mp[x],mp[y]);	//查询在 x-y区间内的前面的 x 
		add(mp[x]);		//将自己的 x 加入数组数组 
	}
	for(int i=1;i<=n;i++) printf("%d\n",res[i]);
	return 0;
}