Nested Segments CodeForces 652D 树状数组+离散化

传送门：CodeForces  652D

题意：给出n个区间，问每个区间包含多少区间。

思路：同时维护两个端点不好维护，我们可以按其中一个端点排序然后维护另一个端点，用树状数组维护一下就好了。

代码：

#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
#define MAXN 100010
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;
struct node{
	int l,r,id;
}a[MAXN*2];
int bit[MAXN*10];
bool cmp(node x,node y)
{
	return x.r<y.r;
}
int num[MAXN*4];
int sum(int i)
{
	int ans=0;
	while(i>0)
	{
		ans+=bit[i];
		i-=-i&i;
	}
	return ans;
}
void add(int i,int x)
{
	while(i<MAXN*10)
	{
		bit[i]+=x;
		i+=-i&i;
	}
}
int res[MAXN*10];
int main()
{
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].id=i;
		num[cnt++]=a[i].l;
		num[cnt++]=a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	sort(num,num+cnt);
	cnt=unique(num,num+cnt)-num;
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(num,num+cnt,a[i].l)-num+1;
		int r=lower_bound(num,num+cnt,a[i].r)-num+1;
		res[a[i].id]=sum(r)-sum(l-1);
		add(l,1);
	}
	for(int i=1;i<=n;i++)
	printf("%d\n",res[i]);
    return 0;
}