divide & conquer + persistent data structure (interval tree) + fenwick tree

AC locally
MLE on BZOJ