題目大意：
在Japan的東西兩邊都有海岸線，且都是南北方向的。兩邊分別有n，m個城市，他們的編號分別都為1....n, 1....m.
要在東西海岸的城市間建立一些高速路，求所有的交點有多少個（一個交點保證只有兩條路穿過）。
分析與總結：
這題並不難想，把所有路按照以東海岸變為起點u，西海岸為終點v保存下來。然後按照u從小到大順序排序（v的順序不重要）。排完序之後，依次枚舉就相當於從西海岸的城市1開始依次開始建立連接一直到n為止。
當處理到第i條邊時，目標是v城市，這條邊連接過去將會增加多少個交點呢？ 只需要畫畫草圖就可以發現了，是之前所有變連接到大於v的城市的邊之和。
知道了這個後，就可以直接用樹狀數組或線段樹切掉了。
有2個注意的地方：
1. 題目沒直接給k的數據范圍，數組要開到50W
2. 用long long
代碼：
1.樹狀數組
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int64;
const int MAXN = 1000000;
int n,m,k;
int64 c[MAXN];
struct node{
int u,v;
friend bool operator<(const node&a,const node&b){
if(a.u!=b.u) return a.u<b.u;
return a.v<b.v;
}
}arr[MAXN];
inline int lowbit(int x){return x&(-x);}
int64 sum(int x){
int64 ret=0;
while(x>0){
ret += c[x];
x -= lowbit(x);
}
return ret;
}
void add(int x){
while(x<=m){
++c[x];
x += lowbit(x);
}
}
int main(){
int T,cas=1;
scanf("%d",&T);
while(T--){
printf("Test case %d: ",cas++);
memset(c, 0, sizeof(c));
scanf("%d%d%d",&n,&m,&k);
for(int i=0; i<k; ++i)
scanf("%d%d",&arr[i].u,&arr[i].v) ;
sort(arr,arr+k);
int64 ans=0;
for(int i=0; i<k; ++i){
ans += sum(m)-sum(arr[i].v) ;
add(arr[i].v);
}
printf("%lld\n",ans);
}
return 0;
}
2. 線段樹
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((left+right)>>1)
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
using namespace std;
typedef long long int64;
const int MAXN = 1000000;
int n,m,k;
int64 c[MAXN];
struct node{
int u,v;
friend bool operator<(const node&a,const node&b){
if(a.u!=b.u) return a.u<b.u;
return a.v<b.v;
}
}arr[MAXN];
void update(int rt,int left,int right,int data){
++c[rt];
if(left==right)return;
if(data <= mid) update(lson,data);
else update(rson,data);
}
int query(int rt,int left,int right,int l,int r){
if(left==l && right==r) return c[rt];
int m = mid;
if(r <= m) return query(lson,l,r);
else if(l > m) return query(rson,l,r);
else return query(lson,l,m)+query(rson,m+1,r);
}
int main(){
int T,cas=1;
scanf("%d",&T);
while(T--){
printf("Test case %d: ",cas++);
memset(c, 0, sizeof(c));
scanf("%d%d%d",&n,&m,&k);
for(int i=0; i<k; ++i) {
scanf("%d%d",&arr[i].u,&arr[i].v) ;
}
sort(arr,arr+k);
int64 ans=0;
for(int i=0; i<k; ++i){
ans += query(1,1,m+1,arr[i].v+1,m+1);
update(1,1,m+1,arr[i].v);
}
printf("%lld\n",ans);
}
return 0;
}
