test/binary-indexed-tree/BinaryIndexedTree-rsqraq.test.cpp

View this file on GitHub
Last update: 2023-05-31 01:48:55+09:00
Problem: https://yukicoder.me/problems/no/742

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/742"

#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
#include "../../lib/99-operator/abel/AbelPrefixSumPointAdd.cpp"
#include "../../lib/11-binary-indexed-tree/BinaryIndexedTree.cpp"

int main(void){
    int N; cin >> N;
    vector<int> A(N+1,0);
    for(int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    BinaryIndexedTree<AbelPrefixSumPointAdd<int>> bit(N+1);
    int ans = 0;
    for(int i = N; 1 <= i; --i) {
        ans += bit.fold(A[i]);
        bit.operate(A[i],1);
    }
    cout << ans << endl;
	return 0;
}

#line 1 "test/binary-indexed-tree/BinaryIndexedTree-rsqraq.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/742"

#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
#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/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 9 "test/binary-indexed-tree/BinaryIndexedTree-rsqraq.test.cpp"

int main(void){
    int N; cin >> N;
    vector<int> A(N+1,0);
    for(int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    BinaryIndexedTree<AbelPrefixSumPointAdd<int>> bit(N+1);
    int ans = 0;
    for(int i = N; 1 <= i; --i) {
        ans += bit.fold(A[i]);
        bit.operate(A[i],1);
    }
    cout << ans << endl;
	return 0;
}