[CF1151C]Problem for Nazar(倍增)

题目链接

题解

这次的题目真的都还挺不错的,考的比较活
two times more这个关键信息告诉我们序列变化的规律,即为 2^i 变换一次
于是我们可以考虑倍增

我们用 s[i] 来表示第1到i段(每一次变化称为一段)的数字和
ls1 为奇数序列,ls2 为偶数序列
lst1 表示当前奇数序列的首项,lst2 同理

假设现在计算第i段的值(假设是奇数段,偶数段同理)

我们就有:

  • 首项:lst1
  • 末项:lst1+(2^{i-1})\times 2
  • 项数:2^{i-1}

于是得到值为:
(lst1+2^{j-1}-1)\times 2^{i-1}

预处理完之后我们就可以处理查询啦(与上面同理)

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注