记录编号	601332	评测结果	AAAAAAAAAA
题目名称	1974.公路交叉	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	2.866 s
提交时间	2025-06-16 19:35:18	内存使用	16.29 MiB

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#define ll long long
using namespace std;
const int N=1000005;
ll t,n,m,k;
vector<pair<ll,ll>>v;
ll a[N],tr[N];
ll lb(ll x){
    return x&(-x);
}
void add(ll x,ll y){
    for(int i=x;i<=max(n,m);i+=lb(i)){
        tr[i]+=y;
    }
}
ll q(ll x){
    ll ans=0;
    for(int i=x;i>0;i-=lb(i)){
        ans+=tr[i];
    }
    return ans;
}
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    cin>>t;
    for(int _=1;_<=t;_++){
    	memset(tr,0,sizeof(tr));
    	v.clear();
        cin>>n>>m>>k;
        for(int i=1;i<=k;i++){
            ll x,y;
            cin>>x>>y;
            v.push_back(make_pair(x,y));
        }
        
        sort(v.begin(),v.end());
        for(int i=0;i<k;i++){
            a[i+1]=v[i].second;
//            add(a[i+1],1);
        }
        ll ans=0;
        for(int i=k;i>=1;i--){
            ans+=q(a[i]-1);
            add(a[i],1);
        }
        cout<<"Test case "<<_<<": "<<ans<<endl;
    }
    return 0;
}