原本是想看看rk1是如何写的那么快的,点进去发现是个假做法,主要部分的代码是这样的:
#define lowbit(x) ((x) & -(x))
const int N = 1e5 + 20;
const int mod = 99999997;
int n, x, ans, a[N], b[N], c[N];
inline void Add(int x) {
for (; x; x -= lowbit(x)) c[x]++;
}
inline int Getsum(int x) {
int cnt = 0;
for (; x <= n; x += lowbit(x)) cnt += c[x];
return cnt;
}
int main() {
int i, j, k;
read(n);
for (i = 1; i <= n; i++) {
read(x);
a[x] = i;
}
for (i = 1; i <= n; i++) {
read(x);
b[i] = a[x];
}
for (i = 1; i <= n; i++) {
ans = (ans + Getsum(b[i] + 1)) % mod;
Add(b[i]);
}
printf("%d\n", ans);
return 0;
}
很明显存在问题,随便一组数据就能卡掉:
input:
4
1 2 3 4
8 7 6 5
output:
6
这个代码会输出 0,但是居然能AC,这个数据真的太水了,怕不是直接random_shuffle两个 1 ~ n 的排列造的数据。
不过现在第一是我了,因为我一开始不信邪交了一发rk1的代码……