@[_qingshu_](/user/602803) 操作次数多少
by 0x28202e202e29 @ 2024-03-20 20:16:29
@[0x28202e202e29](/user/790188)
$10^6$
by _qingshu_ @ 2024-03-20 20:21:24
@[0x28202e202e29](/user/790188)
感觉可能是个线段树套线段树之类的,但是好像时间上说不过去。
by _qingshu_ @ 2024-03-20 20:25:25
@[_qingshu_](/user/602803) 有个想法:对于l=9 r=12(即l=r-lowbit(r)+1),其实就是将[9,12]内所有数加上3v
by 0x28202e202e29 @ 2024-03-20 20:30:10
l>r-lowbit(r)+1的情况不知道怎么弄
by 0x28202e202e29 @ 2024-03-20 20:31:47
@[0x28202e202e29](/user/790188)
会是 $3v$ 吗?好像不是吧,而且这结论局限性有点太大了是不?
by _qingshu_ @ 2024-03-20 20:35:15
$[9,12]$ 不应该是 $[9,9],[9,10],[11,11],[9,12]$
总体加和不是 ${3v,2v,2v,v}$
by _qingshu_ @ 2024-03-20 20:37:16
@[_qingshu_](/user/602803) 确实不是
例如对于l=1 r=4
```
[1,4]
[1,2] [3,4]
[1,1] [2,2] [3,3] [4,4]
```
是给所有左子([1,4] [1,2] [1,1])加上一个+v的tag
by 0x28202e202e29 @ 2024-03-20 21:08:00
对于 $l<r-lowbit(r)+1$,可以将 $[l,r]$ 分成 $[l,r-lowbit(r)]$ 和 $[r-lowbit(r)+1,r]$
例如[7,12]可以分成[7,8]和[9,12],类似于线段树区间修改
by 0x28202e202e29 @ 2024-03-20 21:12:13
> 例如对于l=1 r=4
>
> [1,4]
>
> [1,2] [3,4]
>
>[1,1] [2,2] [3,3] [4,4]
>
>是给所有左子([1,4] [1,2] [1,1])加上一个+v的tag
好像也不是,还有一个[3,3]的
by 0x28202e202e29 @ 2024-03-20 21:14:41