P4229某位歌姬的故事题解\(n\le9\times10^8\)，显然复杂度不与\(n\)相关。\(m\le500\)，显然可以接受\(O(Tm^2)\)的做法。对于\([l,r]\)，考虑套路地将端点离散化，使得复杂度只和关键点个数有关。考虑对于\([l,r,m]\)，离散化后被分成了\(a_1,a_2,\cdots,a_p\)段，那么这些段的