题解 | 计算数组的小和

核心算法

void solve() {
  int n;  cin >> n;
  BIT<int> bit(400);
  int ans = 0;
  for(int i = 1, tp; i <= n; i ++){
    cin >> tp;
    tp += 200;
    ans += bit.ask(1, tp);
    bit.add(tp, tp - 200);
  }
  cout << ans << endl;
}

对于每一个元素都会对 大于等于自身的数字产生贡献

其贡献的值为自身

所以我们利用树状数组快速进行区间加法，对于数字a_i 对所有大于等于a_i的数字加上a_i

由于数字的范围是 - 100 到 100 我们可以任意加上一个大数使所有数字变为非负数

如果数字范围很大可以直接离散化处理

火车头和树状数组板子

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef __int128 i128;

#define int long long

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define fi first
#define se second

#define pb push_back
#define eb emplace_back

const int mod = 998244353;
const int MOD = 1e9 + 7;
const ld eps = 1e-10;

using pp = pair<int, int>;

template<class Int> 
struct BIT { 
    vector<Int> a; 
    int n; 
 
    BIT() {} 
    BIT(int n) { 
        init(n); 
    } 
 
    void init(int n) { 
        this->n = n; 
        a.resize(n + 1); 
    } 
 
    void add(int x, int k) { 
        for (; x <= n; x += x & -x) { 
            a[x] += k; 
        } 
    } 
 
    void add(int x, int y, Int k) { 
        add(x, k), add(y + 1, -k); 
    } 
 
    Int ask(int x) { 
        Int ans = 0; 
        for (; x; x -= x & -x) { 
            ans += a[x]; 
        } 
        return ans; 
    } 
 
    Int ask(int x, int y) { 
        return ask(y) - ask(x - 1); 
    } 
 
    Int kth(int k) { 
        Int ans = 0; 
        for (int i = __lg(n); i >= 0; i--) { 
            Int val = ans + (1 << i); 
            if (val < n && a[val] < k) { 
                k -= a[val]; 
                ans = val; 
            } 
        } 
        return ans + 1; 
    } 
}; 

void solve() {
  
}

signed main()
{
  ios::sync_with_stdio(false);  cin.tie(nullptr);
  int T = 1;
  //cin >> T;
  while(T --) solve();

  return 0;
}