以下做法渐进复杂度最低,为 `log_2` 外线性。是迄今为止全站最快的做法。
正文:
比较麻烦的找性质+模拟题,但还是秒了。~~但是由于各种细节实现上花了好久~~
一开始的想法就是,对操作 $(1)$ 的每一层打反向的标记,然后向上跳的时候遇到这一层反向跳一下,第二个操作打另一种正向的标记就好了。写了半天才写出来,这里说几个小细节:
1、两个操作的标记都打在当前层而不是上一层。但是两个标记释放的时刻不同。第二个标记每次要在跳之前下传当前层的,而第一个标记要在跳之后下传下一层的。原因是第一个标记是整体有效的,第二个标记是暂时有效的。
2、第一个标记在输出之后要清除。
3、注意到操作 $(1)$ 标记反向是因为跳的时候要走相对位移。但是如果一开始起点时存在标记,这个标记的作用应该是正向的。判一下即可。
4、`<cmath> log2()` 贼慢,甚至比手写的还要慢…
```cpp
int T ;
ll buc1[70] ;
ll buc2[70] ;
il int i_lg2(ll n){
int m = 0 ;
if (n >> 32) m |= 32, n >>= 32 ;
if (n >> 16) m |= 16, n >>= 16 ;
if (n >> 8) m |= 8, n >>= 8 ;
if (n >> 4) m |= 4, n >>= 4 ;
if (n >> 2) m |= 2, n >>= 2 ;
if (n >> 1) m |= 1, n >>= 1 ;
return m ;
}
int main(){
qr(T) ; int p ;
ll x, y, z, s, t, yf ;
while (T --){
qr(x), qr(y) ;
if (x == 1)
y = i_lg2(y), qr(z), buc1[y] -= z ;
else if (x == 2)
y = i_lg2(y), qr(z), buc2[y] += z ;
else {
qw(y, ' ') ;
p = i_lg2(y) ;
z = 1ll << p ;
s = (z << 1) - 1 ;
t = - buc1[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
y = x ;
while (p > 0){
s = (z << 1) - 1 ;
t = buc2[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
y = x ;
-- p ;
s = z - 1 ;
z = z >> 1 ;
y = y >> 1 ;
t = buc1[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
yf = y ; y = x ;
qw(y, ' '), y = yf ;
}
putchar('\n') ;
}
}
}
```
#