[ZJ][BIT+描] a457. TOI2010 第五：餐＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-03-01 22:11:35| 人1,253| 回0 | 上一篇 | 下一篇

[ZJ][BIT+描] a457. TOI2010 第五：餐

推 0 收藏 0 0 站台

容：

　　台是吃的王，到都有好吃的餐。有於此，身的小明，定每出一本餐刊介各地值得推的好餐；每一本刊由一名特派到各地的餐身後，在刊上每餐、分。每位特派可以自己定最高的分，例如特派Damon通常用10分代表分(如一)，而特派Chandler只用5 分代表分(如二)。而刊售一段後，小明也者回吃了之後的感想，者可以根自身吃的，依照特派的分表回。

　　然而，可能在某位特派眼中A餐只有到"算可以"(6分/10分)的程度，但民吃後通常都反"很好吃"(8分/10分)。情形通常生在分比格的特派，反之也有分比的特派，但由於每本刊都只有一位特派，因此只要分一致，基本上都有太大的。

　　不，小明有些餐相之下在刊上的大部分民的反不一致，例如A餐在刊中的高於B餐，但者普遍反B餐比A餐好。此，小明召了，要每位特派更用心的比每家餐的劣，才不民的反落差太大造成者得刊不。因此小明提出了一套算差的方式，若算後刊的民的反相去不，期刊的特派。假在某期刊中共了k家餐，特派第i家餐的分s_i分，透者反得到第i家餐的平均分r_i，分方式如下（小明此分"差分"，差分越低表示特派的民反越符合）：

　　差分= |{(i, j) | (s_i > s_j and r_i < r_j) or (s_i < s_j and r_i > r_j), 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餐的分有落差。由於每本刊介的餐目以及特派的分都不同，因此小明你一程式算差分，好他分差分符合他的特派。

入明：

　　料共有三行。第一行有正整k和m (5 ≤ k ≤ 100000，m ≤ 2000000000，km由空白隔)，分代表被比的餐目，以及特派的分。接下的行各包含了k介於1到m的整(整由空白隔 )，分代表了特派以及刊者每家餐所的分。

出明：

　　根小明提供的算式，算出差分。

例入： help

例一： 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

提示：

限仿照原，更改10秒。 (2012/7/6 修改)

出：

2010 TOI 研初 (管理：longbiau)

其不用理 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) {
    i(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;
}