题目链接：http://codeforces.com/problemset/problem/652/D
给你n个不同的区间，L或者R不会出现相同的数字，问你每一个区间包含多少个区间。
我是先把每个区间看作整体，按照R从小到大排序。然后从最小的R开始枚举每个区间，要是枚举到这个区间L的时候，计算之前枚举的区间有多少个Li在L之后，那么这些Li大于L的区间的数量就是答案。那我每次枚举的时候用树状数组add(L , 1) 说明在L这个位置上出现了区间，之后枚举的时候计算L之前的和，然后i - 1 - sum(L)这个就是答案。（跟用树状数组计算逆序对有点类似，自己模拟一下就明白了）。
但是区间的L和R很大，区间的个数又不是很多。所以我用离散化，区间的大小包含1到2n这些数。我用map做的，也可以用二分。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 4e5 + ;
struct data {
int l , r , pos;
}a[MAXN];
int ans[MAXN] , n , bit[MAXN] , x[MAXN * ];
map <int , int> mp;
bool cmp(data x , data y) {
return x.r < y.r;
}
int sum(int i) {
int s = ;
while(i > ) {
s += bit[i];
i -= (i&-i);
}
return s;
} void add(int i , int x) {
while(i <= n*) {
bit[i] += x;
i += (i&-i);
}
} int main()
{
scanf("%d" , &n);
int cont = ;
for(int i = ; i <= n ; i++) {
scanf("%d %d" , &a[i].l , &a[i].r);
x[++cont] = a[i].l;
x[++cont] = a[i].r;
a[i].pos = i;
}
sort(x + , x + cont + );
for(int i = ; i <= cont ; i++) {
mp[x[i]] = i;
}
sort(a + , a + n + , cmp);
for(int i = ; i <= n ; i++) {
a[i].l = mp[a[i].l];
a[i].r = mp[a[i].r];
}
for(int i = ; i <= n ; i++) {
ans[a[i].pos] = i - - sum(a[i].l);
//cout << a[i].l << " " << a[i].r << " " << sum(a[i].l) << endl;
add(a[i].l , );
}
for(int i = ; i <= n ; i++) {
printf("%d\n" , ans[i]);
}
}