一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
P3660 [USACO17FEB] Why Did the Cow Cross the Road III G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二、解题报告
1、思路分析
二维偏序问题
我们将坐标按照第一维排序
然后树状数组维护区间内的右端点数目
我们预排序后顺序遍历所有坐标，这样有个然后查询左右端点间的右端点数目，这些右端点的左端点一定在当前左端点左边，所以当前坐标的贡献就是区间内右端点的数目
查询完之后将右端点插入即可
由于所有坐标一定不重复，查的时候也不用考虑啥细节
2、复杂度
时间复杂度： O(nlogn)空间复杂度：O(n)
3、代码详解
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;const int N = 1e5 +10;std::vector<int> tr(N);std::vector<std::array<int, 2>> a(n + 1);for (int i = 0, x; i < n * 2; i ++ ) {std::cin >> x;if (!a[x][0]) a[x][0] = i + 1;else a[x][1] = i + 1;} std::function<void(int, int)> add = [&](int x, int k) {for (; x < N; x += (x & -x)) tr[x] += k;};std::function<int(int)> query = [&](int x) {int res = 0;for (; x; x &= (x - 1)) res += tr[x];return res;};std::sort(a.begin() + 1, a.end(), [](const auto& x, const auto& y) {return x[0] < y[0];});int res = 0;for (int i = 1; i <= n; i ++ ) {res += query(a[i][1]) - query(a[i][0]);add(a[i][1], 1);}std::cout << res;
}int main () {std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}