@[2018liuzhiyuan](/space/show?uid=118826) 就算离散化，空间也会炸啊。。。
by getchar123 @ 2019-08-14 07:56:53
@[getchar123](/space/show?uid=102754) 如果数字$\le$100,那可以怎么做？
by 2018LZY @ 2019-08-14 07:57:28
@[2018liuzhiyuan](/space/show?uid=118826) ~~按右端点从小到大排序，边扫描边处理前缀和，扫到询问边界就用前缀和处理（吧~~（好像错了
by getchar123 @ 2019-08-14 08:01:03
然而还是达不到O（nlogn）~~（（O（nlogn+m*100）~~
by getchar123 @ 2019-08-14 08:02:36
@[getchar123](/space/show?uid=102754) 这代价并没有区间可加减性。
by 2018LZY @ 2019-08-14 08:02:57
@[2018liuzhiyuan](/space/show?uid=118826) 设从1~r，a出现x次，从1~l-1，a出现y次，从l~r，a的代价就是a*（x-y+1）*（x-y）/2
by getchar123 @ 2019-08-14 08:09:50
~~（貌似不用前缀和~~（然而时间复杂度貌似。。。
by getchar123 @ 2019-08-14 08:11:21
@[getchar123](/space/show?uid=102754) 上面那个大佬说的数字$<=100$时用线段树或树状数组来维护前缀和可行吗？
by dunko @ 2019-08-14 08:14:52
@[dp好难啊](/space/show?uid=47757) （好像可以吧。。。他还没回我呀。。。（然而时间复杂度可能还不如莫队
by getchar123 @ 2019-08-14 08:16:51
$O(nlog_2n)$的预处理，$O(mlog_2n*100)$的询问？好像是不如莫队的，但它在线
by dunko @ 2019-08-14 08:25:55