大哥,N混用了,取模的时候是1e8-3;
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e8 - 3;
ll ans = 0;
struct sb {
ll data;
ll id;
};
sb a[N], b[N];
ll x[N], c[N];
bool cmp(sb x, sb y) {
return x.data < y.data;
}
void cnm(ll zb, ll yb) {
if (zb == yb)
return;
ll mid = (zb + yb) / 2, i = zb, j = mid + 1, flag = zb;
cnm(zb, mid);
cnm(mid + 1, yb);
while (i <= mid && j <= yb) {
if (x[i] <= x[j])
c[flag++] = x[i++];
else {
c[flag++] = x[j++];
ans += ll(mid - i + 1) % P;
}
}
while (i <= mid)
c[flag++] = x[i++];
while (j <= yb)
c[flag++] = x[j++];
for (int p = zb; p <= yb; p++)
x[p] = c[p];
return;
}
signed main() {
ll n;
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i].data;
a[i].id = i;
}
for (ll i = 1; i <= n; i++) {
cin >> b[i].data;
b[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
for (ll i = 1; i <= n; i++)
x[b[i].id] = a[i].id;
cnm(1, n);
printf("%lld", ans % P);
return 0;
}
```
by kmlihaiming @ 2023-12-07 13:39:57