test/static-range-query/StaticRangeInversionQuery.test.cpp

• View this file on GitHub
• Last update: 2023-07-12 04:26:50+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• BinaryIndexedTree - BIT (lib/11-binary-indexed-tree/BinaryIndexedTree.cpp)
• StaticRangeInversionQuery - 静的区間転倒数クエリ (lib/13-static-range-query/StaticRangeInversionQuery.cpp)
• AbelPrefixSumPointAdd (lib/99-operator/abel/AbelPrefixSumPointAdd.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <cmath>
using namespace std;
#include "../../lib/11-binary-indexed-tree/BinaryIndexedTree.cpp"
#include "../../lib/99-operator/abel/AbelPrefixSumPointAdd.cpp"
#include "../../lib/13-static-range-query/StaticRangeInversionQuery.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false); 
    int N,Q; cin >> N >> Q;
    vector<long long> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    StaticRangeInversionQuery<long long> riq(A);
    while(Q--) {
        int l,r; cin >> l >> r;
        long long inv = riq.fold(l,r);
        cout << inv << "\n";
    }
}

#line 1 "test/static-range-query/StaticRangeInversionQuery.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <cmath>
using namespace std;
#line 1 "lib/11-binary-indexed-tree/BinaryIndexedTree.cpp"
/*
 * @title BinaryIndexedTree - BIT
 * @docs md/binary-indexed-tree/BinaryIndexedTree.md
 */
template<class Abel> class BinaryIndexedTree {
    using TypeNode = typename Abel::TypeNode;
    size_t length;
    size_t num;
    vector<TypeNode> node;
public:

    //[0,N) constructed, inplace [0,1) + [1,N+1)
    //you can ignore inplace offset
    BinaryIndexedTree(const size_t num) : num(num) {
        for (length = 1; length < num; length *= 2);
        node.resize(length+1, Abel::unit_node);
    }

    //[idx,idx+1) operate
    void operate(size_t idx, TypeNode var) {
        assert(0 <= idx && idx < length);
        for (++idx; idx <= length; idx += idx & -idx) node[idx] = Abel::func_fold(node[idx],var);
    }

    //[0,idx) fold
    TypeNode fold(size_t idx) {
        TypeNode ret = Abel::unit_node;
        for (idx = min(length,idx); idx > 0; idx -= idx & -idx) ret = Abel::func_fold(ret,node[idx]);
        return ret;
    }

    //return [0,length]
    int binary_search(TypeNode var) {
        if(!Abel::func_check(node.back(),var)) return num;
        TypeNode ret = Abel::unit_node;
        size_t off = 0;
        for(size_t idx = length; idx; idx >>= 1){
            if(off + idx <= length && !Abel::func_check(Abel::func_fold(ret,node[off+idx]),var)) {
                off += idx;
                ret = Abel::func_fold(ret,node[off]);
            }
        }
        return min(off,num);
    }

    void print() {
        cout << "{ " << fold(1);
        for(int i = 1; i < length; ++i) cout << ", " << fold(i+1);
        cout << " }" << endl;
    }
};
#line 1 "lib/99-operator/abel/AbelPrefixSumPointAdd.cpp"
/*
 * @title AbelPrefixSumPointAdd
 * @docs md/operator/abel/AbelPrefixSumPointAdd.md
 */
template<class T> struct AbelPrefixSumPointAdd {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_fold(const TypeNode& l,const TypeNode& r){return l+r;}
    inline static constexpr TypeNode func_fold_inv(const TypeNode& l,const TypeNode& r){return l-r;}
};
#line 1 "lib/13-static-range-query/StaticRangeInversionQuery.cpp"
/*
 * @title StaticRangeInversionQuery - 静的区間転倒数クエリ
 * @docs md/static-range-query/StaticRangeInversionQuery.md
 */
template<class T> class StaticRangeInversionQuery {
    vector<size_t> compressed;
    vector<long long> prefix_inv;
    vector<long long> suffix_inv;
    vector<vector<long long>> sqrt_bucket_freq;
    vector<long long> sqrt_bucket_inv;
    vector<vector<size_t>> sqrt_bucket_sort_index;
    vector<long long> sqrt_bucket_size;
    size_t N,B,M;
public:
    StaticRangeInversionQuery(const vector<T>& ar, T pre=-1)
            : compressed(ar.size()),prefix_inv(ar.size()),suffix_inv(ar.size()) {
        N = ar.size();
        B = sqrt(N) + 1; // bucket size
        M = N / B + 1;   // bucket num
        //zarts
        {
            vector<pair<T,size_t>> ord(N);
            for(size_t i=0;i<N;++i) ord[i]={ar[i],i};
            sort(ord.begin(),ord.end());
            size_t inc=0;
            for(size_t i=0;i<N;++i) {
                if(pre < ord[i].first) inc++;
                compressed[ord[i].second] = inc;
                pre = ord[i].first;
            }
        }
        //freq
        {
            sqrt_bucket_freq.resize(M);
            vector<long long> freq(N+1,0);
            for(size_t i=0;i<M;++i) {
                size_t l = i*B, r = min((i+1)*B,N);
                for(size_t j=l;j<r;++j) freq[compressed[j]]++;
                sqrt_bucket_freq[i] = freq;
                for(size_t j=1;j<=N;++j) sqrt_bucket_freq[i][j]+=sqrt_bucket_freq[i][j-1];
            }
        }
        //prefix,suffix inv
        {
            BinaryIndexedTree<AbelPrefixSumPointAdd<long long>> bit(N+1);
            for(size_t i=0;i<M;++i) {
                int l = i*B, r = min((i+1)*B,N);
                //prefix
                {
                    long long inv = 0;
                    for(size_t j=l;j<r;++j) {
                        inv += bit.fold(N+1)-bit.fold(compressed[j]+1);
                        prefix_inv[j]=inv;
                        bit.operate(compressed[j],1);
                    }
                    for(size_t j=l;j<r;++j) {
                        bit.operate(compressed[j],-1);
                    }
                }
                //suffix
                {
                    long long inv = 0;
                    for(int j=r-1;l<=j;--j) {
                        inv += bit.fold(compressed[j]);
                        suffix_inv[j]=inv;
                        bit.operate(compressed[j],1);
                    }
                    for(size_t j=l;j<r;++j) {
                        bit.operate(compressed[j],-1);
                    }
                }
            }
        }
        //sqrt bucket inv
        {
            sqrt_bucket_inv.resize(M*M,0);
            for(size_t i=0;i<M;++i) {
                size_t l = i*B, r = min((i+1)*B,N);
                if(l<r) sqrt_bucket_inv[i*M+i] = prefix_inv[r-1];
            }
            for(size_t k=1;k<M;++k) {
                for(size_t i=0;i+k<M;++i) {
                    sqrt_bucket_inv[i*M+i+k] += sqrt_bucket_inv[i*M+i]+sqrt_bucket_inv[(i+1)*M+i+k];
                    size_t l = i*B, r = min((i+1)*B,N);
                    for(size_t j=l;j<r;++j) {
                        size_t& c = compressed[j];
                        sqrt_bucket_inv[i*M+i+k] += (sqrt_bucket_freq[i+k][c-1]-sqrt_bucket_freq[i][c-1]);
                    }
                }
            }
        }
        //sort
        {
            sqrt_bucket_sort_index.resize(M);
            sqrt_bucket_size.resize(M,0);
            size_t sz = 0;
            for(size_t i=0;i<M;++i) {
                int l = i*B, r = min((i+1)*B,N);
                sz += max(0,(r-l));
                sqrt_bucket_size[i] = sz;
                if(r-l<1) continue;
                sqrt_bucket_sort_index[i].resize(r-l);
                for(size_t j=l;j<r;++j) sqrt_bucket_sort_index[i][j-l]=j;
                sort(sqrt_bucket_sort_index[i].begin(),sqrt_bucket_sort_index[i].end(),
                     [&](size_t l,size_t r){return compressed[l]==compressed[r]?l<r:compressed[l]<compressed[r];});
            }
        }
    }
    //query [l,r)
    //return {freq,mode} ({頻度,元の配列における値})
    long long fold(int l, int r) {
        int bl = l/B + 1, br = (r-1)/B - 1;
        long long inv = 0;
        //同じbucketにl,rがあるとき
        if(bl > br + 1) {
            inv += prefix_inv[r-1];
            if(l%B) inv -= prefix_inv[l-1];
            long long sum = 0;
            for(size_t i: sqrt_bucket_sort_index[l/B]) {
                if(r <= i) continue;
                if(l <= i) sum++;
                else inv -= sum;
            }
        }
        else {
            inv += sqrt_bucket_inv[bl*M+br];
            inv += suffix_inv[l];
            inv += prefix_inv[r-1];
            size_t ml = bl*B;
            for(size_t i=l;i<ml;++i) {
                size_t& c = compressed[i];
                inv += sqrt_bucket_freq[br][c-1]-sqrt_bucket_freq[bl-1][c-1];
            }
            size_t mr = (br+1)*B;
            for(size_t i=mr;i<r;++i) {
                size_t& c = compressed[i];
                inv += (sqrt_bucket_size[br]-sqrt_bucket_freq[br][c])-(sqrt_bucket_size[bl-1]-sqrt_bucket_freq[bl-1][c]);
            }
            int ir = 0, nr = sqrt_bucket_sort_index[br+1].size();
            long long sum = 0;
            for(auto& xl:sqrt_bucket_sort_index[bl-1]) {
                if(xl < l) continue;
                for(;ir<nr;++ir) {
                    auto& xr = sqrt_bucket_sort_index[br+1][ir];
                    if(xr >= r) continue;
                    if(compressed[xl] > compressed[xr]) sum++;
                    else break;
                }
                inv += sum;
            }
        }
        return inv;
    }
};
#line 12 "test/static-range-query/StaticRangeInversionQuery.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false); 
    int N,Q; cin >> N >> Q;
    vector<long long> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    StaticRangeInversionQuery<long long> riq(A);
    while(Q--) {
        int l,r; cin >> l >> r;
        long long inv = riq.fold(l,r);
        cout << inv << "\n";
    }
}

Back to top page