Submission #56372128

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct BIT {
    int n;
    vector<T> bit;

    void init(int sz) { bit = vector<T> (n = sz + 7); }

    void upd(int i, T x) { 
        for (i++; i < n; i += i & -i) bit[i] += x;
    }

    T query(int i) {
        T ret = 0;
        for (i++; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    }

    T query(int l, int r) { return query(r) - query(l - 1); };
};

const int N = 2e5 + 7;
int n, m;
int p[N], a[N], cnt[N];
vector<int> e[N], f[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    cin >> m;

    BIT<int> bit;
    bit.init(n + 1);

    for (int i = 1; i <= m; i++) {
        cin >> a[i];

        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;

            if (mid - bit.query(mid, n) <= a[i])
                lo = mid;
            else
                hi = mid - 1;
        }

        a[i] = lo;
        bit.upd(a[i], 1);
        e[a[i]].push_back(i);
    }

    bit.init(n + 1);

    ll inv = 0;

    for (int i = 1; i <= n; i++) {
        cnt[i] = bit.query(p[i], n);

        inv += cnt[i];
        bit.upd(p[i], 1);
    }

    bit.init(m + 1);

    for (int i = n; i >= 1; i--) {
        for (int j : e[i])
            bit.upd(j, 1);

        // find cnt[i]'th one
        if (cnt[i] > 0) {
            int lo = 1, hi = m;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;

                if (bit.query(1, mid) <= cnt[i])
                    lo = mid;
                else
                    hi = mid - 1;
            }
            f[lo].push_back(i);
        }
    }

    bit.init(n + 1);
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > 0)
            bit.upd(i, 1);
    }

    for (int i = 1; i <= m; i++) {
        inv -= bit.query(1, a[i]);

        for (int j : f[i])
            bit.upd(j, -1);

        cout << inv << '\n';
    }

    return 0;
}

Submission Info

Judge Result