这道题和那道Star如出一辙，可我还是做了很长时间 ...太菜了...有K条连接东西两个城市的路，东西方向每个城市都有一个编号M,N，从北到南，最后问共有多少个十字路都，即有多少个交点。
先预处理，用结构体表示每条边，对结构体按N进行从小到大的排序，如果N相同，按M从小到大排序。接下来就和Star一样了，唯一不同的是Star那道题是每次求出当前星星前边的个数，而这个是求当前点后边的个数。用c[]表示树状数组，sum(n)求出的是N编号小于等于n的city的个数，只需每次拿出一个city，求出N编号大于它的city的个数，然后更新数组就可以了。
关键代码：
1 long long ans=0;
2 for(i=1;i<=K;i++){ //K表示边的个数
3 ans+=sum(max)-sum(a[i].east); //east即为N编号
4 modify(a[i].east,1); //将a[i].east插入到当前数组
5 }
6
解决了这一步，其余就是套路了，很简单。
Code：
1 #include<iostream>
2 #include<algorithm>
3 #define MAX 10005 //最大的city个数
4 using namespace std;
5 int c[MAX],n,N,M,K,omax;
6 struct road
7 {
8 int west,east;
9 }a[MAX*MAX]; //MAX*MAX为最多的边的个数
10 bool cmp(road a,road b){
11 if(a.west==b.west)
12 return a.east<b.east;
13 return a.west<b.west;
14 }
15 int lowbit(int t){
16 return t&(t^(t-1));
17 }
18 int sum(int t){
19 int total=0;
20 while(t>0){
21 total+=c[t];
22 t-=lowbit(t);
23 }
24 return total;
25 }
26 void modify(int posi,int key){
27 while(posi<=omax){
28 c[posi]+=key;
29 posi+=lowbit(posi);
30 }
31 }
32 int main()
33 {
34 int i,j,k,m,cas;
35 long long ans;
36 scanf("%d",&cas);
37 for(i=1;i<=cas;++i){
38 omax=0; //用omax表示所有east的最大值，以确定求和区间
39 memset(c,0,sizeof(c));
40 scanf("%d%d%d",&N,&M,&K);
41 for(j=1;j<=K;++j){
42 scanf("%d%d",&a[j].east,&a[j].west);
43 if(a[j].east>omax)
44 omax=a[j].east;
45 }
46 sort(a+1,a+1+K,cmp);
47 ans=0;
48 for(j=1;j<=K;++j){ //key code
49 ans+=(sum(omax)-sum(a[j].east));
50 modify(a[j].east,1);
51 }
52 printf("Test case %d: %lld\n",i,ans);
53 }
54 }
55