Codeforces 960D - Full Binary Tree Queries

960D - Full Binary Tree Queries

思路：

用move1[i]记录第i层第1种操作移动的个数（对这一层的个数取模）

用move2[i]记录第i层第2种操作移动的个数（对这一层的个数取模）

查询方法：

记当前值为 x，当前层为 i，则经过操作后，他到了 x + move1[i] + move2[i] 的位置，记 x = x + move1[i] + move2[i]

则这个位置上一层的位置是 x >> 1，记 x = x >> 1

那我们只要知道 x 这个位置的值是多好就好了，因为第二种操作对值并没有影响，所以 x 这个位置的值是 x - move1[i-1]，记 x = x - move1[i-1]

这样循环操作就能输出路径了

代码：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define mem(a, b) memset(a, b, sizeof(a))

LL move1[], move2[];

int main() {

    int q, t;

    LL x, k;

    scanf("%d", &q);

    while (q--) {

        scanf("%d", &t);

        if (t == ) {

            scanf("%lld%lld", &x, &k);

            int dep = ;

            while (x) {

                x >>= ;

                dep++;

            }

            LL mod = 1LL << (dep - );

            move1[dep] = ((move1[dep] + k ) % mod + mod) % mod;

        }

        else if (t == ) {

            scanf("%lld%lld", &x, &k);

            int dep = ;

            while (x) {

                x >>= ;

                dep++;

            }

            LL mod = 1LL << (dep - );

            move2[dep] = ((move2[dep] + k) % mod + mod) % mod;

        }

        else {

            scanf("%lld", &x);

            LL tx = x;

            int dep = ;

            while (tx) {

                dep++;

                tx >>= ;

            }

            bool f = true;

            while (x) {

                printf("%lld ", x);

                LL mod = (1LL << dep - );

                LL mv = (move1[dep] + move2[dep]) % mod;

                LL L = 1LL << (dep - ), R = (L << ) - ;

                if(x + mv > R) x = x + mv - mod;

                else x = x + mv;

                x >>= ;

                dep --;

                mod = (1LL << dep - );

                L = 1LL << (dep - ), R = (L << ) - ;

                if(x - move1[dep] < L) x = x + mod - move1[dep];

                else x = x - move1[dep];

            }

            printf("\n");

        }

    }

    return ;

} 

Codeforces 960D - Full Binary Tree Queries的相关教程结束。