我自认为自己写的非常模板和规范了,没想到,一看提交有好多人用70ms就能通过,不知道还能怎样优化呢?
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, mod = 99999997;
typedef long long ll;
ll a[N], b[N], ra[N], rb[N], rka[N], rkb[N], tmp[N], inda, indb, n, ans;
void merge(int b, int e) {
if (b >= e)return;
int mid = (b + e) / 2, l = b, r = mid + 1, ind = b;
merge(l, mid), merge(mid + 1, e);
while (l <= mid && r <= e) {
if (rkb[l] < rkb[r])tmp[ind++] = rkb[l++];
else {
ans = (ans + mid - l + 1) % mod;
tmp[ind++] = rkb[r++];
}
}
while (l <= mid)tmp[ind++] = rkb[l++];
while (r <= e)tmp[ind] = rkb[r++];
for (int i = b; i < ind; i++)rkb[i] = tmp[i];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i], ra[i] = a[i];
for (int i = 1; i <= n; i++)cin >> b[i], rb[i] = b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++) {
inda = lower_bound(a + 1, a + n + 1, ra[i]) - a - 1;
indb = lower_bound(b + 1, b + n + 1, rb[i]) - b - 1;
ra[i] = inda;
rka[ra[i]] = i;
rb[i] = indb;
}
for (int i = 1; i <= n; i++)rkb[i] = rka[rb[i]];
merge(1, n);
cout << ans % mod;
}