# Data Structure Basis-Tree and Binary Tree-Boxes in a Line

https://vjudge.net/problem/UVA-12657

```You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4
kinds of commands:
• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
• 3 X Y : swap box X and Y
• 4: reverse the whole line.
Commands are guaranteed to be valid, i.e. X will be not equal to Y .
For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing
2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1.
Then after executing 4, then line becomes 1 3 5 4 6 2
Input
There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m
(1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.
Output
For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n
from left to right.
Sample Input
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
Sample Output
Case 1: 12
Case 2: 9
Case 3: 2500050000```

Just notice that the left and right sub-node numbers of node K are 2*k and 2*k+1, respectively.

At first, it can be written by simulation, but you will find that it will be timeout, which is a bit heavy.

```#include<bits/stdc++.h>
using namespace std;
const int maxd = 20;
int s [1<<maxd];    //Maximum number of nodes pow(2, maxd)-1
int main(){
int D,I,n;
cin >> n;
while(n--){
scanf("%d%d",&D,&I);
memset(s,0,sizeof(s));   //Analog switch
int k,n = (1<<D)-1;  //n is the largest number
for(int i=0;i<I;i++){
k=1;      // 0 to the left and 1 to the right
for(;;){
s[k] = !s[k];//Controlling the Direction of Falling
k = s[k] ? k*2 : k*2+1;
if(k >n)
break;
}
}
printf("%d\n",k/2);
}
return 0;
}```

Then you will find that when the number "I" is odd, he will go to the left of the first (I+2)/2 ball;

When "I" is even, he will go right to the first I/2 ball.

```#include<bits/stdc++.h>
using namespace std;
const int maxd = 20;

int main(){
int D,I,n;
cin >>n;
while(n--){
scanf("%d%d",&D,&I);
int k=1;
for(int i=0;i<D-1;i++){
if(I%2){
k = k*2;
I = (I+1)/2;
}else{
k = k*2+1;
I /= 2;
}
}
printf("%d\n",k);
}
return 0;
}```

The basic numbering problem in the binary tree is OK. When I see the hierarchical traversal of the binary tree, my whole person is not very good at qwq.

Added by MAXIEDECIMAL on Sun, 06 Oct 2019 09:06:22 +0300