对于这份代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, mod = 99999997 ;
int n, a[N], b[N];
map<int, int> vis;
struct edge {
int l, r, sum;
}tree[N * 4];
void push_up(int p) {
tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
void build(int p, int l, int r) {
tree[p].l = l, tree[p].r = r;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
push_up(p);
}
void modify(int p, int x, int v) {
if (tree[p].l == tree[p].r) {
tree[p].sum += v;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) modify(p * 2, x, v);
else modify(p * 2 + 1, x, v);
push_up(p);
}
int query(int p, int l, int r) {
if (l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
int mid = (tree[p].l + tree[p].r) >> 1, res = 0;
if (l <= mid) res += query(p * 2, l, r);
if (r > mid) res += query(p * 2 + 1, l, r);
return res;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], vis[a[i]] = i;
for (int i = 1; i <= n; i++) cin >> b[i], b[i] = vis[b[i]];
int res = 0;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
res = (res + query(1, b[i] + 1, n)) % mod;
modify(1, b[i], 1);
}
cout << res << endl;
}
给出 hack 数据:
10
103 538 706 338 310 54 235 437 77 458
746 465 54 882 206 615 1031 513 1001 288
正确输出:
37
错误代码输出
43
ps: 差不多随机一个数据都能卡掉这个代码,不知道luogu的数据是谁造的。。。