A 了但是问
查看原帖
A 了但是问
1036180
ChampionCyan楼主2025/2/7 16:02

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,求各路神仙指教!

2025/2/7 16:02
加载中...