[ZJ][BIT+掃描線] a457. TOI2010 第五題：餐廳評鑑
內容 ：
台灣是吃的王國，到處都有好吃的餐廳。有 鑑於此，身為雜誌編輯的小明，決定每週出一本餐廳週刊專門介紹各地值得推薦的好餐廳；每一本週刊由一名特派員負責到各個地區的餐廳親身體驗後，在週刊上對 每間餐廳寫評語、給分數。每位特派員可以自己決定最高的級分，例如特派員Damon通常會用10級分代表滿分(如圖一)，而特派員Chandler只用5 級分代表滿分(如圖二)。而週刊銷售一段時間後，小明也會讓讀者回饋吃了之後的感想，讀者可以根據自身吃過的經驗，依照特派員的評分表來回饋評價。
然而，可能在某位特派員眼中A餐廳只有到"還算可以"(6級分/10級分)的程度，但民眾吃過後通常都反應"很好吃"(8級分/10級分)。這種情形通 常會發生在給分比較嚴格的特派員，反之也有給分比較寬鬆的特派員，但由於每本週刊都只有一位特派員負責，因此只要給分標準一致，基本上都沒有太大的問題。
不過，小明卻發現有些餐廳相較之下在週刊上的評價與大部分民眾的反應並不一致，例如A餐廳在週刊中的評價高於B餐廳，但讀者們卻普遍反應B餐廳比A餐廳 好。為此，小明召開了會議，要每位特派員更用心的比較每家餐廳的優劣，才不會與民眾的反應落差太大造成讀者覺得週刊雜誌不夠專業。因此小明提出了一套計算 評價差異的方式，若經過計算後週刊的評價與民眾的反應相去不遠，則會給負責該期週刊的特派員獎賞。假設在某期週刊中總共評價了k家餐廳，特派員對第i家餐 廳的評分為si級分，透過讀者反應得到第i家餐廳的平均級分為ri，則計分方式如下（小明將此分數稱為"差異分數"，差異分數越低表示特派員的評價與民眾反應越符合）：
差異分數= |{(i, j) | (si > sj and ri < rj) or (si < sj and ri > rj), 1 ≤ i < j ≤ k}|.
舉例來說，假設某期週刊介紹了A、B、C、D、E五家餐廳，特派員分別給了3、7、5、5、8的分數，而統計了讀者回饋的分數平均後五家餐廳分別得到了 4、6、7、5、8的分數，那麼差異分數計算後為1，其原因為B餐廳和C餐廳特派員與大部分的讀者感覺有落差(兩家餐廳相較之下，特派員給了B餐廳較高的 分數，但讀者給了C餐廳較高的分數)。請注意C餐廳與D餐廳在特派員的評價中一樣好，但讀者回饋的分數C餐廳較高，這並不算一個落差。若讀者回饋的平均分 數五家餐廳分別得到4、6、7、7、7，則差異分數為2，其原因為特派員以及讀者在B餐廳和C餐廳、以及B餐廳和D餐廳的評分有落差。由於每本週刊裡介紹 的餐廳數目以及特派員的滿分標準都不同，因此小明請你寫一個程式來計算差異分數，好讓他分發獎賞給差異分數符合他標準的特派員。
輸入說明
：
輸出說明
：
範例輸入
：
範例一： 5 10 3 7 5 5 8 4 6 7 5 8 範例二： 5 10 3 7 5 5 8 4 6 7 7 7
範例輸出 ：
範例一： 1 範例二： 2
提示
：
出處
：
其實不用理會 i < j 的關係，既然都給定 or 的關係，排序之後計算也是不變的。
此外 = |{ or }| 是表示計算集合的大小。
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
struct D {
int s, r;
};
bool cmp(D a, D b) {
if(a.s != b.s) return a.s > b.s;
return a.r > b.r;
}
int n, i, j;
unsigned res = 0;
int C[100005] = {}, x, y;
map<int, int> R;
int main() {
scanf("%d %*d", &n);
D d[n];
for(i = 0; i < n; i++)
scanf("%d", &d[i].s);
for(i = 0; i < n; i++)
scanf("%d", &d[i].r), R[d[i].r] = 1;
sort(d, d+n, cmp);
i = 1;
for(map<int, int>::iterator it = R.begin();
it != R.end(); it++)
it->second = ++i;
int size = i;
for(i = 0; i < n; i++) {
y = x = R[d[i].r]-1;
while(y)
res += C[y], y -= y&(-y);
x++;
while(x <= size)
C[x]++, x += x&(-x);
}
printf("%u\n", res);
return 0;
}