记录编号	601348	评测结果	AAAAAAAAAA
题目名称	1974.公路交叉	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	3.113 s
提交时间	2025-06-16 20:14:13	内存使用	16.45 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,T,l=1;
struct node {
	long long x,y;
}a[1234567];
long long b[1234567];
long long lowbit(long long x) {
	return x&-x;
}
void add(long long x, long long val) {
	for(;x<=m;x+=lowbit(x))b[x]+=val;
}

long long sum(long long x){
	long long res=0;
	for (;x;x-=lowbit(x))res+=b[x];
	return res;
}

bool cmp(node a,node b){
	return (a.x == b.x? a.y < b.y : a.x < b.x);
}
void Solve() {
	memset(b, 0, sizeof b);
	cin>>n>>m>>k;
	for (long long i=1;i<=k;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+k+1,cmp);
	long long res=0;
	for (long long i=k;i>=1;i--) {
		res+=sum(a[i].y-1);
		add(a[i].y,1);
	}
	printf("Test case %lld: %lld\n", l++, res);
	return;
}

signed main() {
	freopen("road.in","r",stdin);freopen("road.out","w",stdout);
	cin>>T;
	while(T--)Solve();
	return 0;
}