第4题 #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 2e5 + 100; int T; int a[N], b[N], aa[N]; int c[N]; int cnt; int n; int mx, my; LL ans = 0; vector <int> v[N]; inline int query(int x){ if (x <= 0) return 0; int ret = 0; for (; x; x -= x & -x) ret += c[x]; return ret; } inline void update(int x){ for (; x <= 2e5; x += x & -x) ++c[x]; } void ins(int x){ int tmp = query(x) - query(x - 1); if (tmp) return; update(x); } int main(){ scanf("%d", &T); while (T--){ ans = 0; cnt = 0; scanf("%d", &n); rep(i, 1, n){ scanf("%d%d", a + i, b + i); aa[++cnt] = a[i]; aa[++cnt] = b[i]; } memset(c, 0, sizeof c); sort(aa + 1, aa + cnt + 1); cnt = unique(aa + 1, aa + cnt + 1) - aa - 1; rep(i, 1, n) a[i] = lower_bound(aa + 1, aa + cnt + 1, a[i]) - aa; rep(i, 1, n) b[i] = lower_bound(aa + 1, aa + cnt + 1, b[i]) - aa; mx = my = 0; rep(i, 1, 2e5) v[i].clear(); rep(i, 1, n) v[a[i]].push_back(b[i]), mx = max(mx, a[i]), my = max(my, b[i]); dec(i, mx, 1){ int mm = 0; for (auto u : v[i]) ins(u), mm = max(mm, u); ans += 1ll * query(mm); } printf("%lld\n", ans); } return 0; }