@[泥土笨笨](/user/43206)
by Egg_laying_master @ 2022-10-13 21:57:26
@[Egg_laying_master](/user/771171) 数据不一样,你以为所有oj都是一样的嘛
by Bernie_qwq @ 2022-10-13 22:04:38
目前本题征集SPJ都星号加粗了还不看吗
by _Karasu_ @ 2022-10-13 22:04:41
@[Sprague_Garundy](/user/764746) 题管过来
by LuoTianyi_Official @ 2022-10-13 22:05:30
@[TX_Bernie](/user/701460) https://www.luogu.com.cn/discuss/show/96533
by Egg_laying_master @ 2022-10-13 22:11:12
@[Egg_laying_master](/user/771171) wssb
by Bernie_qwq @ 2022-10-13 22:14:54
@[__Ultimium__](/user/424089) 但是我没有数据,我找找
by Sprague_Garundy @ 2022-10-13 22:20:14
@[_Karasu_](/user/123451) https://www.luogu.com.cn/discuss/show/96533
by Egg_laying_master @ 2022-10-13 22:21:55
官网没 SPJ,寄。
by Sprague_Garundy @ 2022-10-13 22:24:19
@[Egg_laying_master](/user/771171)
同学,不是这道题的问题,是你代码树状数组写假了。我给你改了一下已经AC了,这样改:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e5 + 5;
class BIT {
public:
void upd(int x, int v) {
for (; x <= n; x += x & -x) {
c[x] += v;
}
}
int qry(int x) {
int ret = 0;
for (; x; x -= x & -x) {
ret += c[x];
}
return ret;
}
BIT() {}
BIT(int _n) : n(_n) {}
int n, c[kMaxN];
} b;
int n, k, idx, tot;
int a[kMaxN], c[kMaxN];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
b.n = n;
a[n + 1] = n + 1;
for (int i = n; i; --i) {
if (a[i] < a[i + 1]) {
b.upd(a[i], 1), ++tot;
} else {
idx = i; break ;
}
}
for (int i = 1; i <= idx; ++i) {
int x = b.qry(a[i]) + 1;
++tot;
c[++k] = n - tot + x - 1;
b.upd(a[i], 1);
}
cout << k << endl;
for (int i = 1; i <= k; ++i) {
cout << c[i];
if (i != k) cout << ' ';
}
return 0;
}
```
你错误的原因是,你在main里面,重新创建了一个BIT的对象,但是因为是局部变量,你的BIT里面的c数组并没有被初始化成0,因此c数组里面是随机的垃圾值,在不同平台提交结果不同是显然的。
我给你改成了使用全局变量里面的b对象,并且在main里面直接给b.n赋值,而不是创建一个新的b,这样就AC了。
本题唯一解,不需要SPJ。
by 泥土笨笨 @ 2022-10-14 17:52:25