bzoj2568

题目链接

bzoj2568

题解

这题有毒&&bzojAC100祭

我们需要在最大\log_2级别的复杂度内解决4个问题:

  • 插入一个元素
  • 删除集合中值等于X(输入的值)的所有元素
  • 对于整个集合的所有元素值增加X
  • 查询集合内元素二进制下第K位为1的个数

数据范围N\leq 500000,X\leq 10^{16}

X在10^{16},所以如果我们不能开权值线段树去维护这4个操作,首先我们没办法在\log的复杂度内实现第四个操作,其次空间难以承受。

我们考虑一个与线段树功能类似的数据结构。

树状数组。

我们将权值作为下标,开16个权值树状数组,分别表示考虑后i位的小于等于x的数的个数。

所以我们通过作差可以求出第K位为1的数的个数。

显然易见:ans=c[k][2^{k+1}-1]-c[k][2^k-1]

至于ADD操作的lazy标记可以通过标记永久化来解决。

额外参考

写个博客表示我还在水题

By:Wahacer

2018.06.19

16:54

发表评论

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