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

Problem - D - Codeforces

題意：
給一個完滿二元樹，用最大編號描述。二元樹上的編號是遞迴配置的，如圖：

給 Q 筆詢問，每筆詢問給起點編號，以及操作字串，字串由 { 'U', 'L', 'R' } 組成，對於不可執行的操作無視之。問終點編號為何。

資料規模：
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.

解法：
首先可以發現同一層的相鄰節點之間的編號差是 2**( 高度 + 1 )。因此向左向右的轉移很顯然。向上也不難，從根節點二分下來即可。

時間 / 空間複雜度：
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;
}