verify/library_checker/data_structure/static_range_inversions_query.test.cpp

View this file on GitHub
Last update: 2024-11-09 01:50:04+09:00
Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/fenwick_tree.hpp"
#include "../../../src/data_structure/mo.hpp"
int main(void) {
    int n, q;
    cin >> n >> q;
    Mo mo(n, q);
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    vector<int> comp = a;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    rep(i, 0, n) a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
    rep(i, 0, q) {
        int l, r;
        cin >> l >> r;
        mo.insert(l, r);
    }
    vector<ll> ans(q);
    FenwickTree<int> fw(n);
    ll cnt = 0;
    auto add_left = [&](int idx) {
        cnt += fw.sum(0, a[idx]);
        fw.add(a[idx], 1);
    };
    auto add_right = [&](int idx) {
        cnt += fw.sum(a[idx] + 1, n);
        fw.add(a[idx], 1);
    };
    auto delete_left = [&](int idx) {
        cnt -= fw.sum(0, a[idx]);
        fw.add(a[idx], -1);
    };
    auto delete_right = [&](int idx) {
        cnt -= fw.sum(a[idx] + 1, n);
        fw.add(a[idx], -1);
    };
    auto out = [&](int idx) {
        ans[idx] = cnt;
    };
    mo.run(add_left, add_right, delete_left, delete_right, out);
    rep(i, 0, q) {
        cout << ans[i] << '\n';
    }
}

#line 1 "verify/library_checker/data_structure/static_range_inversions_query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/fenwick_tree.hpp"
template <typename T>
struct FenwickTree {
    FenwickTree(const int N)
        : n(N), data(N) {}
    void add(int p, const T& x) {
        assert(0 <= p and p < n);
        ++p;
        while(p <= n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }
    T sum(const int l, const int r) const {
        assert(0 <= l and l <= r and r <= n);
        return sum(r) - sum(l);
    }
    T get(const int x) const {
        assert(0 <= x and x < n);
        return sum(x + 1) - sum(x);
    }

   private:
    int n;
    vector<T> data;
    inline T sum(int r) const {
        T s = 0;
        while(r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};
#line 3 "src/data_structure/mo.hpp"
struct Mo {
    Mo(const int N, const int Q)
        : n(N), order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(order.begin(), order.end(), 0);
    }
    void insert(const int l, const int r) {
        assert(0 <= l and l <= r and r <= n);
        left.emplace_back(l);
        right.emplace_back(r);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& add_left, const AR& add_right, const DL& delete_left, const DR& delete_right, const OUT& out) {
        assert(left.size() == order.size());
        sort(order.begin(), order.end(), [&](const int i, const int j) {
            const int iblock = left[i] / width, jblock = left[j] / width;
            if(iblock != jblock) return iblock < jblock;
            if(iblock & 1) return right[i] < right[j];
            return right[i] > right[j];
        });
        int nl = 0, nr = 0;
        for(const int idx : order) {
            while(nl > left[idx]) add_left(--nl);
            while(nr < right[idx]) add_right(nr++);
            while(nl < left[idx]) delete_left(nl++);
            while(nr > right[idx]) delete_right(--nr);
            out(idx);
        }
    }

   private:
    int n, width;
    vector<int> left, right, order;
};
#line 5 "verify/library_checker/data_structure/static_range_inversions_query.test.cpp"
int main(void) {
    int n, q;
    cin >> n >> q;
    Mo mo(n, q);
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    vector<int> comp = a;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    rep(i, 0, n) a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
    rep(i, 0, q) {
        int l, r;
        cin >> l >> r;
        mo.insert(l, r);
    }
    vector<ll> ans(q);
    FenwickTree<int> fw(n);
    ll cnt = 0;
    auto add_left = [&](int idx) {
        cnt += fw.sum(0, a[idx]);
        fw.add(a[idx], 1);
    };
    auto add_right = [&](int idx) {
        cnt += fw.sum(a[idx] + 1, n);
        fw.add(a[idx], 1);
    };
    auto delete_left = [&](int idx) {
        cnt -= fw.sum(0, a[idx]);
        fw.add(a[idx], -1);
    };
    auto delete_right = [&](int idx) {
        cnt -= fw.sum(a[idx] + 1, n);
        fw.add(a[idx], -1);
    };
    auto out = [&](int idx) {
        ans[idx] = cnt;
    };
    mo.run(add_left, add_right, delete_left, delete_right, out);
    rep(i, 0, q) {
        cout << ans[i] << '\n';
    }
}