记录编号	315768	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	BillAlen	是否通过	通过
代码语言	C++	运行时间	0.168 s
提交时间	2016-10-05 20:37:31	内存使用	2.22 MiB

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAX_N 100000
#define MOD 99999997
using namespace std;
struct MatchItem {
    unsigned length, pos;
};
int n, cnt, lens[MAX_N];
MatchItem seriala[MAX_N], serialb[MAX_N];
int compareMatch(const void* a, const void* b){
    return ((MatchItem*)(a))->length - ((MatchItem*)(b))->length;
}
void merge_sort(int* lp, int* rp, int &res){ // 区间左闭右开
    if(lp >= rp - 1) return;
    int *mid = int(floor(double(rp - lp) / 2)) + lp;
    merge_sort(lp, mid, res);
    merge_sort(mid, rp, res);
    vector<int> temp;
    int *p1 = lp, *p2 = mid;
    while(p1 < mid && p2 < rp){
        if(*p1 < *p2) temp.push_back(*(p1++));
        else{
            temp.push_back(*(p2++));
            res += (mid - p1);
            res %= MOD;
        }
    }
    while(p1 < mid) temp.push_back(*(p1++));
    while(p2 < rp) temp.push_back(*(p2++));
    for(int *p = lp; p < rp; ++p)
        *p = temp[p - lp];
    
}
int main(int argc, const char* argv[]){
    fstream in("MatchNOIP2013.in", ios::in), out("MatchNOIP2013.out", ios::out);
    cin.rdbuf(in.rdbuf());
    cout.rdbuf(out.rdbuf());
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> seriala[i].length;
    for(int i = 0; i < n; ++i){
        cin >> serialb[i].length;
        serialb[i].pos = i;
    }
    qsort(serialb, n, sizeof(MatchItem), compareMatch);
    for(int i = 0; i < n; ++i) lens[i] = serialb[i].length;
    for(int i = 0; i < n; ++i) seriala[i].pos = serialb[lower_bound(lens, lens + n, seriala[i].length) - lens].pos;
    for(int i = 0; i < n; ++i) lens[i] = seriala[i].pos;
    merge_sort(lens, lens + n, cnt);
    cout << cnt << endl;
    return 0;
}