This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#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; }