题面
在一条直线上有 \(n\) 条线段，每条线段用 \((l,r)\) 表示，求每条线段包含多少条其他的线段。
思路
线段的包含
首先，怎么样的线段是包含关系？
答案：对于一个线段 \((l_1,r_1)\) 与另一个线段 \((l_2,r_2)\)，若 \(l_1 \ge l_2\) 且 \(r_1 \le r_2\)，那么这 \((l_1,r_1)\) 就被 \((l_2,r_2)\) 包含。
这很好证明，请读者在草稿纸上画一个数轴（什么，你竟然说你没学过数轴？），自己探究一下。
处理数据
首先，如果线段序列按照 \(r\) 单一关键字进行升序排序，那么一定有 \(r_{i-1} \le r_{i}\)，且根据上面的理论， \((l_i,r_i)\) 一定只能包含不超过 \(i-1\) 条线段。前面的线段若 \(l_j \ge l_i\) 即 \(j\) 被 \(i\) 包含（当然，这里 \(j \lt i\)）。
\(l\)挺大的（\(-10^{9} \le l_{i} \lt r_{i} \le 10^{9}\)）。 所以需要离散化来缩小范围到\(n\)的范围（\(1 \le n \le 2 \times 10^{5}\)）。另外，离散化也可以为之后的求逆序对创造有利条件。
还是不懂为什么要离散化？
树状数组需要开的数组，如果没有离散化那么要开 $2 \times 10^9 $ 以上大小的数组，肯定会MLE。
如何初始化
先创建一个 \(l\) 数组的副本，然后每次用二分寻找原来的数组 \(l_i\) 的位置替换原来的真实值。
离散化的思想与HASH类似，都是缩小数据范围的一种有力的方法。
树状数组出场
经过上面的分析，就能够知道这就是一个求前面有多少个小于这个数的问题（逆序对），可以使用树状数组解答（当然，神犇们用线段树我也不阻止了）。
归并排序每一次都会重新计算，可能会过不去（请读者们试一试）。
至此，我们已经解决该问题，时间复杂度为 \(O(n \log n)\)。
贴上源代码
#include <bits/stdc++.h>
#define SIZE int(2*(1e5)+5)
#define inti int i
using namespace std;
int n,yl[SIZE],tree[SIZE],result[SIZE];
struct Segment{
int l,r,id;
bool operator<(const Segment csgt) const {
return (this->r)<(csgt.r);
}
} sgts[SIZE];
namespace BIT{ // 树状数组求逆序对板子
int lowbit(int x){
return x&-x;
}
void add(int p, int val){
while(p<=n) {
tree[p]+=val;
p+=lowbit(p);
}
return;
}
int query(int p){
int sum=0;
while(p){
sum+=tree[p];
p-=lowbit(p);
}
return sum;
}
}
void lisanhua(){
sort(yl+1,yl+n+1);
for(inti=1;i<=n;++i){
sgts[i].l=lower_bound(yl+1,yl+n+1,sgts[i].l)-yl;
}
sort(sgts+1,sgts+1+n);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>sgts[i].l>>sgts[i].r;
sgts[i].id=i;
yl[i]=sgts[i].l;
}
lisanhua();
for(int i=1;i<=n;i++){
BIT::add(sgts[i].l,1);
result[sgts[i].id]=i-BIT::query(sgts[i].l-1);
}
for(int i=1;i<=n;i++){
printf("%d\n",result[i]-1);
}
return 0;
}
最后啰嗦一句，看样例可以知道，这道题“包含”不包括自己与自己包含，所以一定要减一！
\(\color{green}\textbf{AC}\) 了！