笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「找性质+模拟」 CF960D Full Binary Tree Queries

posted on 2020-06-09 08:11:09 | under 题解 |

以下做法渐进复杂度最低,为 log_2 外线性。是迄今为止全站最快的做法。

正文:

比较麻烦的找性质+模拟题,但还是秒了。但是由于各种细节实现上花了好久

一开始的想法就是,对操作 $(1)$ 的每一层打反向的标记,然后向上跳的时候遇到这一层反向跳一下,第二个操作打另一种正向的标记就好了。写了半天才写出来,这里说几个小细节:

1、两个操作的标记都打在当前层而不是上一层。但是两个标记释放的时刻不同。第二个标记每次要在跳之前下传当前层的,而第一个标记要在跳之后下传下一层的。原因是第一个标记是整体有效的,第二个标记是暂时有效的。

2、第一个标记在输出之后要清除。

3、注意到操作 $(1)$ 标记反向是因为跳的时候要走相对位移。但是如果一开始起点时存在标记,这个标记的作用应该是正向的。判一下即可。

4、<cmath> log2() 贼慢,甚至比手写的还要慢…

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') ;
        }
    }
}