Codeforces 920F – SUM and REPLACE

现在有一个数列$a[1…n]$,函数$D(x)$表示$x$的因数个数,有如下操作:

  • 给出一个区间$[L, R]$,把区间里的每个数$a_i$替换成$D(a_i)$
  • 给出一个区间$[L, R]$,求和

看似一个区间修改,区间查询的维护问题。实际上,根据$D(x)$的性质我们可以知道当$x$为1或者2的时候就没有必要替换了,对于$10^6$以内的数,可以打表求看一看$D(x)$是多少,我们发现即使一个数很大,也不需要经过很多次就可以替换成一或者二。所以这一题单点更新即可。

我们需要建两个线段树,一颗维护区间最大值,一颗维护和。当我们查询到区间最大值小于等于二,就没有必要在求和的线段树上继续深入了。

对于$D(x)$,需要用筛法预处理。

 

说点什么

avatar
50
  Subscribe  
提醒