yukicoder No.919 You Are A Project Manager 解説
☩☩☩WAVELET MATRIX☩☩☩
Wavelet Matrixにより数列
$ (A_1,\ldots,A_N)
の部分列
$ (A_l,\ldots,A_{r-1})
のk番目に大きい数はO(1)で求まる。
従って、
$ K=1,\ldots,N
を全探索しても、各Kについてチーム数は高々
$ \lbrack N/K \rbrack
だから計算量は
$ O(N \log N)
で済む。