传送门
T2防ak题？
其实也不是很难（考试时sb了）。
直接变形一下求出区间长度在[l2,r2][l2,r2][l2,r2]之间，中位数≤l1−1\le l1-1≤l1−1的区间数，和区间长度在[l2,r2][l2,r2][l2,r2]之间，中位数≤r1\le r1≤r1的区间数就行了。
继续变变形，一个区间的中位数如果≤k\le k≤k。
那么显然有：区间中≤k\le k≤k的数的个数≤\leq≤区间中>k>k>k的数的个数。
我们记smallismall_ismalli表示111$i$中比$k$小的数的个数，$big_i$表示$1$iii中比kkk大的数的个数。
那么就有：smallr−small−1≤bigr−bigl−1small_r-smal_{l-1}\leq big_r-big_{l-1}smallr−small−1≤bigr−bigl−1
移项后发现：smallr−bigr≤smalll−1−bigl−1small_r-big_r\leq small_{l-1}-big_{l-1}smallr−bigr≤smalll−1−bigl−1
然后就可以主席树做了。
代码