# CFR 792 D. Paths in a Complete Binary Tree ( Ad hoc, Binary Search )

Problem - D - Codeforces

The first line contains two integer numbers n and q (1 ≤ n ≤ 1e18, q ≥ 1). n is such that n + 1 is a power of 2.
The next 2q lines represent queries; each query consists of two consecutive lines. The first of these two lines contains ui (1 ≤ ui ≤ n), the second contains non-empty string si. si doesn't contain any characters other than 'L', 'R' and 'U'.
It is guaranteed that the sum of lengths of si (for each i such that 1 ≤ i ≤ q) doesn't exceed 1e5.

O( Q lg^2 N ) / O( 1 )

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

signed main(){
ios::sync_with_stdio( 0 );
ll n; int q; cin >> n >> q;
for( int qi = 0; qi < q; ++qi ){
ll u; cin >> u;
string op; cin >> op;
for( int i = 0, hei = __builtin_ctzll( u ); i < op.size(); ++i ){
if( op[ i ] == 'U' ){
if( u == n + 1 >> 1 ) continue;
for( ll j = n + 1 >> 1, k = __builtin_ctzll( n + 1 ) - 1; ; ){
if( k == hei + 1 ){
u = j;
break;
}
if( j < u ){
j += 1LL << k - 1;
} else{
j -= 1LL << k - 1;
}
--k;
}
++hei;
} else if( op[ i ] == 'L' ){
if( hei == 0 ) continue;
u -= 1LL << hei - 1;
--hei;
} else{
if( hei == 0 ) continue;
u += 1LL << hei - 1;
--hei;
}
}
cout << u << "\n";
}
return 0;
}
```