這道題和那道Star如出一轍，可我還是做了很長時間 ...太菜了...有K條連接東西兩個城市的路，東西方向每個城市都有一個編號M,N，從北到南，最后問共有多少個十字路都，即有多少個交點。
先預處理，用結構體表示每條邊，對結構體按N進行從小到大的排序，如果N相同，按M從小到大排序。接下來就和Star一樣了，唯一不同的是Star那道題是每次求出當前星星前邊的個數(shù)，而這個是求當前點后邊的個數(shù)。用c[]表示樹狀數(shù)組，sum(n)求出的是N編號小于等于n的city的個數(shù)，只需每次拿出一個city，求出N編號大于它的city的個數(shù)，然后更新數(shù)組就可以了。
關鍵代碼：
1 long long ans=0;
2 for(i=1;i<=K;i++){ //K表示邊的個數(shù)
3 ans+=sum(max)-sum(a[i].east); //east即為N編號
4 modify(a[i].east,1); //將a[i].east插入到當前數(shù)組
5 }
6
解決了這一步，其余就是套路了，很簡單。
Code：
1 #include<iostream>
2 #include<algorithm>
3 #define MAX 10005 //最大的city個數(shù)
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為最多的邊的個數(shù)
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的最大值，以確定求和區(qū)間
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