记录编号	433942	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2017-08-06 19:02:41	内存使用	1.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

# define MAXN (100010)
# define MOD (99999997)

struct DATA{ 
    int ha, hb;
    DATA() { ;}

    bool operator < (const DATA &a) const { 
        if(ha ^ a.ha) return ha < a.ha;
        
    }
};

struct MATCH{ 
    unsigned int hgt, pos;
    MATCH() { ;}
    MATCH(int h, int p) { 
        hgt = h, pos = p;
    }
};

bool operator < (MATCH a, MATCH b) { 
    return a.hgt < b.hgt;
}

void merge_sort(int l, int r);

vector<MATCH> A, B;
int p[MAXN];
int N, ans;

int main() { 
#ifndef LOCAL
    freopen("MatchNOIP2013.in", "r", stdin);
    freopen("MatchNOIP2013.out", "w", stdout);
#endif
    N = read();
    for(int i = 0; i < N; ++i) A.push_back(MATCH(read(), i));
    for(int i = 0; i < N; ++i) B.push_back(MATCH(read(), i));
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for(int i = 0; i < N; ++i) { 
        p[B[i].pos] = A[i].pos;
    }
    //for(int i = 0; i < N; ++i) printf("%d ", p[i]);
    merge_sort(0, N - 1);
    printf("%d", ans);
    return 0;
}

void merge_sort(int l, int r) { 
    static int tmp[MAXN];
    if(l == r) return ;
    register int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    register int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r) { 
        if(p[i] > p[j]) { 
            (ans += mid - i + 1) %= MOD;
            tmp[k++] = p[j++];
        } else tmp[k++] = p[i++];
    }
    while(i <= mid) tmp[k++] = p[i++];
    while(j <= r) tmp[k++] = p[j++];
    for(; l <= r; ++l) p[l] = tmp[l];
    return ;
}