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