题意 : 给出一颗无限层的满二叉树，然后每个值为 X （根的 X 等于 1 ） 左孩子的值是 2*X，右孩子的值是 2*X+1 ，现在有两种操作，（1， x，k） 表示将 x 所在层的所有节点整体向右循环地移动 k 个单位、（2，x，k）表示将 x 所在的层的所有节点及其子树向右循环地移动 k 个单位、（3，x）输出从 x 到根的路径
分析 :
第一个操作不难进行模拟
只要给每个层记录其偏移量，最后查询的时候依据偏移量来输出具体的值即可
关键是第二个操作
仔细一想，会发现一个规律
如果第一层移动 k 个单位
那么对于第二种操作，其孩子分别移动了 k*2^1、k*2^2、k*2^3……
所以其本质就是进行第一种操作，偏移量不一样了而已
查看了题目数据量之后发现每一次只进行到第 60 层
所以模拟到第 60 层就是回答所有问询了
#include<bits/stdc++.h>
#define LL long long
using namespace std;
;
LL Move1[maxn];///正移动偏移量，方便知道原节点去了哪个位置
LL Move2[maxn];///反移动偏移量，方便知道原节点现在是什么值
inline void op1(int Lay, LL move, LL x, LL times)
{
) Lay = log2(x) + ;///获取 x 在第几层
LL Base = 1LL<<(Lay-);///这一层有多少个节点
) move %= Base;///如果非第二种操作
else move = ( (move % Base) * (times % Base) ) % Base;///第二种操作
Move1[Lay] = (( Move1[Lay] + move) + Base ) % Base;///正偏移量直接移动即可
Move2[Lay] = (( Move2[Lay] - move) + Base ) % Base;///反偏移量要反向移动
}
inline void op2(LL move, LL x)
{
;
; i<; i++,j++)///最多到60层
op1(i, move, , 1LL<<j);
}
inline void op3(LL x)
{
if(x == 1LL){
puts(");
return;
}
printf("%I64d", x);
;
LL Base = 1LL<<(Lay-);
LL pos = (( (x - Base) + Move1[Lay] ) + Base) % Base + Base;
while(!(pos == 3LL || pos == 2LL)){
) pos = (pos - )>>;///找到当前节点的父亲节点
;
Lay = log2(pos) + ;
Base = 1LL<<(Lay-);
printf(" %I64d", ( (pos - Base + Move2[Lay]) + Base ) % Base + Base);///通过反向偏移量来获取在这个节点位置的值
}puts(");
}
int main(void)
{
int Q;
scanf("%d", &Q);
while(Q--){
int command;
LL X, K;
scanf("%d", &command);
){
scanf("%I64d %I64d", &X, &K);
op1(-, K, X, -);
}){
scanf("%I64d %I64d", &X, &K);
op2(K, X);
}else{
scanf("%I64d", &X);
op3(X);
}
}
;
}