はじめてのBIT.cpp

#include <bits/stdc++.h>
using namespace std;

template<class T> class BIT{
private:
	/**
	 * [---------------------8]
	 * [---------4]
	 * [---2]      [---6]
	 * [1]   [3]   [5]   [7]   [9]
	 */
	vector<T> pyon;
public:
	BIT(int n){
		pyon = vector<T>(n, (T)0);
	}
	/**
	 * [++++++++++++++++++++++]
	 * [----------]
	 * [----]      [++++]
	 * [-]   [-]   [+]   [-]   [-]
	 * 5: 0101 +    1 -> 6
	 * 6: 0110 +   10 -> 8
	 * 8: 1000 + 1000 -> out of range
	 */
	void add(int i, int d){
		i++;
		while(i <= pyon.size()){
			pyon[i - 1] += d;
			i += i & -i;
		}
	}
	/**
	 * [++++++++++++++++++++++]
	 * [----------]
	 * [----]      [++++]
	 * [-]   [-]   [+]   [-]   [-]
	 * 5: 0101 -    1 -> 4
	 * 4: 0100 - 0100 -> 0
	 */
	T sum(int i){
		i++;
		T sum = (T)0;
		while(i){
			sum += pyon[i - 1];
			i -= i & -i;
		}
		return sum;
	}
};

int main(){
	int N, sum = 0;
	cin >> N;
	BIT<int> pyon(N);
	for(int i = 0; i < N; i++){
		int a;
		cin >> a;
		sum += pyon.sum(--a);
		pyon.add(a, 1);
	}
	cout << sum;
	return 0;
}