POJ 3067 樹狀數組求逆序數

題意：日本東海岸有n個城市，西海岸有m個城市，現在要修建k條高鐵連接配接東海岸的城市u和西海岸的城市v。問這k條高鐵總共有多少個交點。

#include <stdio.h>  
#include <iostream>  
#include <algorithm>  
#include <string.h>  
#include <math.h>  
#define M 1005  
#define LL long long  
using namespace std;  
  
int n,m,k;  
int c[M];  
struct node  
{  
    int x,y;  
    bool operator < ( const node &h ) const  
    {  
        return x<h.x || (x==h.x && y<h.y);  
    }  
};  
struct node p[M*M];  
  
int Lowbit(int x)  
{  
    return x&(-x);  
}  
  
void Update(int x,int d)  
{  
    while(x<=M)  
    {  
        c[x]+=d;  
        x+=Lowbit(x);  
    }  
}  
  
int Sum(int x)  
{  
    int sum=0;  
    while(x>0)  
    {  
        sum+=c[x];  
        x-=Lowbit(x);  
    }  
    return sum;  
}  
  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    for(int count=1;count<=t;count++)  
    {  
        memset(c,0,sizeof(c));  
        scanf("%d%d%d",&n,&m,&k);  
        for(int i=1;i<=k;i++)  
        {  
            scanf("%d%d",&p[i].x,&p[i].y);  
        }  
        sort(p+1,p+1+k);  
        LL ans=0;  
        for(int i=1;i<=k;i++)  
        {  
            Update(p[i].y,1);  
            ans+=(i-Sum(p[i].y));  
        }  
        printf("Test case %d: %lld\n",count,ans);  
    }  
    return 0;  
}  
           

#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
typedef __int64 int64;
typedef unsigned int uint;
const double EPS = 1e-8;
const double PI = acos(-1.);
const int INF = 0x7f7f7f7f;
const int INF32 = ~0U >> 1;
const int64 INF64 = ~0ULL >> 1;
const int MOD = int(1e9) + 7;
/* Macros */
#define TR int __T;scanf("%d",&__T);while(__T--)
#define NR while(~scanf("%d",&n))
#define MR while(~scanf("%d%d",&n,&m))
#define NO while(~scanf("%d",&n),n)
#define MO while(~scanf("%d%d",&n,&m),n||m)
#define SQR(x) ((x)*(x))
#define ALL(x) (x).begin(),(x).end()

#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define mm (l+r)>>1

const int N = 1100;
int n, m, k, cas = 1;

struct Link {
    int l, r;
    bool operator <(const Link& next) const {
        if (l == next.l) {
            return r < next.r;
        }
        return l < next.l;
    }
} link[1000005];

void get_data() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &link[i].l, &link[i].r);
    }
    sort(link, link + k);
}

int64 in[N];

int lowbit(int t) {
    return t & (-t);
}

int64 sum(int end) {//與上面的差別
    int64 sum = 0;
    while (end <= 1001) {
        sum += in[end];
        end += lowbit(end);
    }
    return sum;
}

void add(int pos) {//差別
    while (pos > 0) {
        in[pos]++;
        pos -= lowbit(pos);
    }
}

void run() {
    int64 tot = 0;
    memset(in, 0, sizeof(in));
    for (int i = 0; i < k; i++) {
        int r = link[i].r;
        tot += sum(r + 1);//差別
        add(r);
    }
    printf("Test case %d: %I64d\n", cas++, tot);
}

int main() {
    TR {
        get_data();
        run();
    }
    return 0;
}