Inversion Queries

2 secs 1024 MB

shinnshinn

問題

提出

テストケース

解説

この問題はMo's algorithmとFenwick treeで解くことができます。

区間 $[L,R)$ の転倒数が分かっている時、

$R+1$ と加える時、 $A[R]$ より大きい要素の数を答えに加える
$R-1$ と削除する時、 $A[R]$ より大きい要素の数を答えから引く
$L+1$ と削除する時、 $A[L]$ より小さい要素の数を答えから引く
$L-1$ と加える時、 $A[L]$ より小さい要素の数を答えに加える

これらの操作により答えが求まります。

計算量はMo's algorithmが $O(N\sqrt{Q})$ 、区間を広げる処理に $O(\log{\max(A_i)})$ より、全体で $O(N\sqrt{Q} \log{ \max(A_i) })$ となります。

実装

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
template<typename T>
struct FenwickTree{
    int n;
    vector<T> data;
​
    FenwickTree(int n):n(n), data(n+1){}
​
    void add(int i, T x){
        assert(0 <= i && i < n);
        i++;
        while(i <= n){
            data[i] += x;
            i += i & -i;
        }
    }
​
    // sum[0, i)
    T sum(int i) const{
        assert(0 <= i && i <= n);
        T retu_sum = 0;
        while(i > 0){
            retu_sum += data[i];
            i -= i & -i;
        }
​
        return retu_sum;
    }
​
    // sum[l, r)
    T sum(int l, int r) const {
        assert(0 <= l && l <= n);
        assert(0 <= r && r <= n);
        return sum(r) - sum(l);
    }
};
​
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    for(int i = 0;i < q; ++i){
        cin >> l[i] >> r[i];
        --l[i];
    }
​
​
    const int MAX_A = 1e5;
    FenwickTree<long> tree(MAX_A + 1);
​
    long now = 0;
    vector<int> ans(q);
    auto add_r = [&](int i){
        now += tree.sum(a[i]+1, MAX_A+1);
        tree.add(a[i], 1);
    };
    auto add_l = [&](int i){
        now += tree.sum(1, a[i]);
        tree.add(a[i], 1);
    };
    auto del_r = [&](int i){
        now -= tree.sum(a[i]+1, MAX_A+1);
        tree.add(a[i], -1);
    };
    auto del_l = [&](int i){
        now -= tree.sum(1, a[i]);
        tree.add(a[i], -1);
    };
​
    const int width = max<int>(1, n/sqrt(q));
    vector<int> p(q);
    for(int i = 0;i < q; ++i){
        p[i] = i;
    }
    sort(p.begin(), p.end(), [&](int i, int j){
        if(l[i]/width == l[j]/width){
            return r[i] < r[j];
        }
        return l[i] < l[j];
    });
​
    int li = 0, ri = 0;
    for(int i: p){
        int nl = l[i], nr = r[i];
        while(ri < nr){
            add_r(ri);
            ++ri;
        }
        while(li > nl){
            --li;
            add_l(li);
        }
        while(ri > nr){
            --ri;
            del_r(ri);
        }
        while(li < nl){
            del_l(li);
            ++li;
        }
        ans[i] = now;
    }
​
    for(int i = 0;i < q; ++i){
        cout << ans[i] << '\n';
    }
}