————
可以先练道逆序对的题：P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
?原理概括：（abcd当做一组降序的4个数，现在进行归并）
//merge 降序： abcd mnop
//a大或者m大： a大，比右边全大，全是逆序对 -> ans+右边剩余数目,a归
// m大，比左边全大，m没有逆序对了 -> m归，不操作ans————
然后注意这道F题，
两人之间只会打一次招呼
我们按左节点顺序排，这样前面的左边界都包含后面的左边界
接下来看右边界，暴力看会超时。其实我们就是希望知道前面的右包含多少个后面的右
这就是逆序对（此时只看右区间就好）
AC代码：
ll ans;
void merge(int left, int right, vector<vector<int>>& arr)
{
if (left >= right)return;
int mid = left + (right - left) / 2;
merge(left, mid, arr);
merge(mid + 1, right, arr);
vector<int>tmp(right - left + 1);
int l = left, r = mid + 1, cur = 0;
while (l <= mid && r <= right)
{
if (arr[l][1] > arr[r][1])
{
ans += right - r + 1;//ans
tmp[cur++] = arr[l++][1];
}
else
{
tmp[cur++] = arr[r++][1];
}
}
while (l <= mid)
{
tmp[cur++] = arr[l++][1];
}
while (r <= right)
{
tmp[cur++] = arr[r++][1];
}
cur = left;
for (int i = 0; i < tmp.size(); i++)
{
arr[cur + i][1] = tmp[i];
}
}
void solve()
{
ans = 0;
int n; cin >> n;
vector<vector<int>>arr(n, vector<int>(2));
for (int i = 0; i < n; i++)
{
cin >> arr[i][0] >> arr[i][1];
}
sort(arr.begin(), arr.end());
merge(0,n-1,arr);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while (t--)
{
solve();
}
return 0;
}