用树状数组或者线段树做dp, O(nlgn)