100pts:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100005;
int n, a[MAXN], b[MAXN];
inline int lowbit(int x) {
return x & -x;
}
inline void update(int c[], int x, int k) {
while (x < MAXN)//here
c[x] += k, x += lowbit(x);
}
inline int query(int c[], int x) {
int res = 0;
while (x)//here
res += c[x], x -= lowbit(x);
return res;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int ans = 0, x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
ans += query(b, x - 1);
update(b, x, query(a, x - 1));
update(a, x, 1);
}
cout << ans;
return 0;
}
18pts:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100005;
int n, a[MAXN], b[MAXN];
inline int lowbit(int x) {
return x & -x;
}
inline void update(int c[], int x, int k) {
for (int i = x; i < MAXN; i += lowbit(x))//here
c[i] += k;
}
inline int query(int c[], int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(x))//here
res += c[i];
return res;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int ans = 0, x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
ans += query(b, x - 1);
update(b, x, query(a, x - 1));
update(a, x, 1);
}
cout << ans;
return 0;
}
两代码仅 here
处有不同,但是我是ShaBi蒟蒻,看不出来 hh,求各路神仙指教!