P3806 【模板】点分治1

既然已经说了是模板,那么考虑怎么套用点分治。
容易想到记录到所有值的方案数,但是发现瓶颈在于每次结束以后去枚举答案。
因为k在1kw,显然单次统计都会有1kw的复杂度,考虑优化,发现实际上只有不到1w个取值,
那么在每次新增一个取值的时候去更新即可,然后现在又有一个问题在于每次新查找的时候数组的清空。
这个直接套个时间戳即可
c++代码如下:

 

6 + 5 =