순회 순서를 좌표의 오름차순, 좌표가 같다면 의 내림차순으로 하면 임의의 를 확인할 때, 이전에 고른 좌표들의 값들은 현재 보다 작거나 같기 때문에 일단 좌표는 조건을 만족한다. 이 중에서 좌표 또한 보다 큰 경우만 세주면 모든 경우의 수를 셀 수 있다.
구간 합 세그먼트 트리로 update하면서 세준다. 좌표의 범위가 넓지만 좌표의 개수는 개이므로 좌표압축을 적용한다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bw = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
while (TC-- > 0) {
int N = Integer.parseInt(br.readLine());
ArrayList<Pair> S = new ArrayList<>(N);
ArrayList<Integer> yLoc = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
S.add(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
yLoc.add(S.get(i).y);
}
Collections.sort(S);
// 좌표 압축
Collections.sort(yLoc);
Map<Integer, Integer> compress = new HashMap<>();
int index = 1;
for (int y : yLoc) if (compress.get(y) == null) compress.put(y, index++);
FenwickTree t = new FenwickTree(index - 1);
long cnt = 0; int n = 0;
for (Pair p : S) {
p.y = compress.get(p.y);
cnt += n - t.sum(p.y - 1);
t.add(p.y, 1);
n++;
}
bw.append(cnt).append("\n");
}
System.out.print(bw);
}
}
class Pair implements Comparable<Pair> {
int x, y;
Pair(int x, int y) { this.x = x; this.y = y; }
public int compareTo(Pair o) { return x == o.x ? o.y - y : x - o.x; }
}
class FenwickTree {
int[] tree;
FenwickTree(int n) { tree = new int[n + 1]; }
void add(int pos, int val) {
while (pos < tree.length) {
tree[pos] += val;
pos += (pos & -pos);
}
}
int sum(int pos) {
int ret = 0;
while (pos > 0) {
ret += tree[pos];
pos -= (pos & -pos);
}
return ret;
}
}