简单题解

本题询问打招呼次数，但是对于两个人来说，$x(a_x,b_x)$ 和 $y(a_y,b_y)$，因为两个人是同时出发且速度相同，所以只存在一下三种相遇的方式：

• 运动中相遇，起点相同-------$a_x == a_y$
• 结束后发生相遇
  • 1.终点相同，同时结束---$b_x == b_y$
  • 2.终点不同，其中一个结束，静待另一个经过，发生相遇

本题看似是运动相遇，其实是处理区间交集问题的模型。
因为题目说，这 n 个人的起点和终点都不相同，所以前两种情况不成立，只有第三种情况成立。成立必要条件是，x 先结束，静待 y 经过，那么条件就是 $a_y<a_x<b_x<b_y$;
所以处理思路也就出来了：

• 1.先按照右端点 b 升序排列
• 2.对于每个区间 i ，去前面寻找其它区间 j，在 $b_j<b_i$ 的情况下，去寻找 $a_j>a_i$ 的数量。这个有一点类似于逆序对，用 1 标记每个出现的点，求和就能直接得到数量。

注意：本题数据范围很大，是 $10^9$，用树状数组的话，内存爆掉，需要离散化

    //离散化
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());

怎么找到离散化后，原数字所对应的新的数字呢？直接找数组对应下标，即为其离散化后的数字，注意树状数组下标从 1 开始，所以需要额外 +1。

int id_x = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;

找到这个数字 id_x 之后，去寻找前面有多少区间左端点是 > id_x 的；
令 m 为离散化的最大值，可以去求 [idx+1,m] 区间之和，通过 [1,m] - [1,id_x] 得到。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N = 5e5+10;
int tr[N];//树状数组
int n,m;
int lowbit(int x){
    return x & (-x);
}
void add(int x,int c){//在x位置加c
    for(int i = x; i <= m; i += lowbit(i)){
        tr[i] += c;
    }
}
int sum(int x){//求前x项之和
    int res = 0;
    for(int i = x; i >= 1; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}
bool cmp(pii a,pii b){
	return a.second<b.second;
}
void solve(){
	cin >> n;
	vector<pii>p(n);
	vector<int>v;
	for(int i = 0; i < n; i ++){
		cin >>p[i].first>>p[i].second;
		v.push_back(p[i].first);
		v.push_back(p[i].second);
	}
	//离散化
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	m = v.size();
	//按 r 升序排列
	sort(p.begin(),p.end(),cmp);
	memset(tr,0,sizeof tr);
	ll ans = 0;
	for(auto& [x,y] : p){
		// 已经确定前面的r均小于当前 r，统计前面l大于当前l的数量，
		//就是一定能和当前的人打招呼的
		int id_x = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
		ans += (sum(m) - sum(id_x));
		add(id_x,1);
	}
	cout << ans <<endl;
}
int main(){
    int tt;
    cin >>tt;
    while(tt--){
    	solve();
    }
    return 0;
}