[트리] [시도x] MEASURETIME

1. 펜윅트리를 이용한 풀이

 

처음에 이 문제를 봤을때 

 

펜윅트리를 어떻게 써야할 지 감을 못잡았다.

 

책에서는 수열의 입력값으로 이루어진 트리를 만들고

 

해당 입력값이 오게되면 그것을 포함하는 구간을 전부 +1을 해줘서

 

루트에 현재 수열의 길이를 저장하게 되고

 

입력값 까지의 부분합을 구하게 되면 

 

현재 수열중에서 입력값보다 작은 것들의 개수를 알 수 있다.

 

이를 통해 자신보다 큰 원소의 개수를 알 수 있고, 앞으로 몇칸 이동 시켜야하는지 파악할 수 있다. 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
struct FenwickTree {
    vector<int> tree;
    FenwickTree(int n) : tree(n+1, 0) {}
    int sum(int pos) {
        ++pos;
        int ret = 0;
        while(pos>0) {
            ret += tree[pos];
            pos&=(pos-1);
        }
        return ret;
    }
    void add(int pos, int val) {
        ++pos;
        while(pos < tree.size()) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};
 
 
 
int C, N;
vector<int> A;
 
long long totalMove() {
    long long ret = 0;
    FenwickTree tree(1000000);
    for(int i = 0; i < A.size(); i++) {
        ret += tree.sum(1000000-1) - tree.sum(A[i]);
        tree.add(A[i], 1);
    }
    return ret;
}
int main() {
    cin>>C;
    while(C--) {
        cin>>N;
        A.clear();
        A.resize(N);
        while(N--) {
            int tmp;
            cin>>tmp;
            A.push_back(tmp);
        }
        cout<<totalMove()<<"\n";
    }
}

• MEASURETIME

 

-알고리즘 문제해결전략 760p