这数据水到家了
查看原帖
这数据水到家了
411727
Kingna楼主2023/8/5 14:03

对于这份代码:

#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的数据是谁造的。。。

2023/8/5 14:03
加载中...