高速公路(road)

如果直接维护一个点到其它点的距离，维护起来很困难。

不妨转换思路，考虑每个点对答案的贡献，

设询问区间为$l,r$，

则点$i$的贡献为$(i-l)*(r-i)*w[i]=(-i^2+(l+r)*i-l*r)*w[i]$。

对于$i^2*w[i],i*w[i],w[i]$分别维护，再乘上只与$l,r$有关的系数即可。

 

CPU监控

鸽了

 

 

排序

如果直接排序，复杂度不能接受。

考虑到对于01序列，线段树可以$O(logn)$查找并统计设置，完成一次排序。

二分第q个数的大小，将大于等于mid的值设为1，小于mid的值设为0。

完成m次排序后检验位置q是否为1即可。

复杂度$O(mlog^2n)$

 

 

 

山海经

分块做法：

处理每个块内的答案，前缀和最小值和前缀和最大值。

答案出现在每个块中，或不在同一块的最大值减最小值。

 

线段树做法：

鸽了

莫队做法：

 

 

 

permu