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 ;
}
上一篇:Java Hour 59 JVM Heap


下一篇:域名注册商namesilo价格便宜,赠送whois保护,最新优惠码:geekradio