길이 $n$인 배열 $a_1, a_2, \cdots, a_n$이 있을 때, 이 배열의 인버전의 개수는 $i<j, a_i>a_j$를 만족하는 쌍 $(i, j)$의 개수입니다.

인버전의 개수는 세그먼트 트리를 활용해 $O(n\log n)$에 구할 수 있습니다.

// TODO

확장

위 문제를 확장해서, $i_1 < i_2 < \cdots < i_k,\ a_{i_1}<a_{i_2}<\cdots<a_{i_k}$인 쌍 $(i_1, i_2, \cdots, i_k)$의 개수도 세어 봅시다.

• :platinum4: 24505. blobhyperthink :blobhyperthink: ← $k=11$인 경우

위와 유사하게, 세그먼트 트리에 $i$로 끝나는 길이 $k-1$인 쌍의 개수를 저장해 놓으면, 길이가 $k$인 쌍의 개수를 $O(N\log N)$에 구할 수 있습니다.

vector cur(n, 1), arr = inputArr(n);
repeat(10) {
    vector nxt(n);
    Segtree<int> seg(n);
    forn(i, n) {
        nxt[i] = seg.query(1, arr[i]-1);
        seg.add(arr[i], cur[i]);
    }
    cur = nxt;
}
println(sum(cur));

총 시간복잡도는 $O(kn\log n)$이 됩니다.