CodeForces-Greetings 转存洛谷
题目
题目思路
首先这道题我并不没有用树状数组然后离散化去写，因为不会，我的思路是逆序对。
分析以下给的样例：
2 6
3 9
4 5
1 8
7 10
-2 100
我做这道题的思路就是一个初中物理追及相遇的想法，比如对于 \((2,6)\) 与 \((3,9)\) 这两个点来说，我们可以发现是只可以打招呼一次的，就是当前者走到了终点时，后者追上来了，有没有可能存在两个人打招呼两次呢？答案是否定的，因为大家的速度都是 \(1\)，不会存在你追上我，我后面又反追的情况的。
所以只能是要么打一次招呼，要么一次也不打，而且打一次的情况，也只能是某个人停下来，你路过他的终点才有，因为都在途中跑的情况下，是不会打招呼的，毕竟速度都一样，所以大家不妨把几组数据写下来找下规律，就可以得出结论两个人，其中甲的起点比乙的起点小，但是甲的终点比乙的远时，就可以发生一次打招呼，而且也只有这一种情况可以发生打招呼。
需要优化的地方
那么我们得出这个结论时，可以想到把终点按从大到小的顺序排下，然后从第一个点开始与第二个，第三个到最后一个点，比较每人的起点，然后再是第二个与第三个，第四个比较起点，以此类推，就可以正确得出答案了，为什么不用比较终点，因为已经排好了，但是呢，如果是这样做是会超时的，所以需要用到逆序对，可以很快的做出来，因为数据很大的时候，你这样循环比较肯定是暴力做法，要超时的。
学习逆序对
逆序对的模板题目
视频
我非常推荐大家观看这个视频学习，因为讲的很好，不懂的小伙伴可以去学习下逆序对，下面代码我也给了我的注释。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long ans;//切记开long long 因为数据很大，会有超出int的答案的
int n;
int b[200005], c[200005];
struct node {
int st;
int fin;
} a[200005];//存起点 start以及终点final
bool cmp(node a, node b) {
return a.fin > b.fin;
}
void merge(int l, int r) {
if (l >= r)return ;
int i = l;
int k = l, mid = l + r >> 1, j = mid + 1;
merge(l, mid);//不断分层合并操作
merge(mid + 1, r);
while (i <= mid && j <= r) {
if (b[i] <= b[j])c[k++] = b[j++], ans += mid - i + 1;
else c[k++] = b[i++];
}
//这里修改了下逆序对的写法，
//改成是甲比乙小,下标也比乙小，符合题解分析的写法（原先是甲比乙大，但下标比乙小） 就答案ans+
//你也可以换一种排序 排起点 那就是正常的逆序对写法
//别的都是模板了没带改的
while (i <= mid)c[k++] = b[i++];
while (j <= r)c[k++] = b[j++];
for ( i = l; i <= r; i++)b[i] = c[i];
return ;
}
void solve() {
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(c, 0, sizeof c);
ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].st >> a[i].fin;
}
sort(a, a + n, cmp);
for (int i = 0; i < n; i++) {
b[i] = a[i].st;
}
merge(0, n - 1);
cout << ans << endl;
return ;
}
int main() {
int t ;
cin >> t;
while (t--) {
solve();
}
return 0;
}
感谢观看，祝大家元旦快乐，新的一年能心想事成，幸苦管理员大大了。