学步园

逆序数 树状数组

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 ll;
int const MAXN = 1010;
int c[MAXN * 2];
struct City{
    int e,w;
}city[MAXN * 1000];
bool cmp(City a,City b){
    if(a.w == b.w) return a.e < b.e;
    return a.w < b.w;
}
int LowBit(int x){
    return x & (-x);
}
void Add(int x,int d){
    while(x <= MAXN){
        c[x] += d;
        x += LowBit(x);
    }
}
int Sum(int x){
    int ret = 0;
    while(x > 0){
        ret += c[x];
        x -= LowBit(x);
    }
    return ret;
}
int main(){
    int t;
    while(~scanf("%d",&t)){
       for(int temp = 1;temp <= t;temp++){
            memset(c,0,sizeof(c));
            int n,m,k;
            scanf("%d%d%d",&n,&m,&k);
            for(int i = 1;i <= k;i++){
                scanf("%d%d",&city[i].e,&city[i].w);
                city[i].e++;
                city[i].w++;
            }
            sort(city+1,city+1+k,cmp);
            ll sum = 0;
            for(int i = 1;i <= k;i++){
                Add(city[i].e,1);
                sum += i - Sum(city[i].e);
            }
            printf("Test case %d: %I64d\n",temp,sum);
       }
    }
    return 0;
}