A1782 [GESP-6.2412.T1] 树上游走

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

// [GESP-6.2412.T1] 树上游走
//
// 编号规则：节点 i 的左儿子是 2i，右儿子是 2i+1，父亲是 i/2（向下取整）。
// 于是三种移动就是三个公式：
//     U：当前编号 > 1 时变成 s / 2（1 是根，没有父亲，原地不动）
//     L：变成 s * 2
//     R：变成 s * 2 + 1
// 逐个字符照着更新当前编号即可，不必真的建出这棵无穷大的树。
//
// 题目只保证「最终」编号不超过 10^12，中途向上移动之前可能累积过大的倍数，
// 所以中间值用 __int128 保存（最终值必然能装进 long long）。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long start;
    cin >> n >> start;
    string t;
    cin >> t;

    __int128 s = start;
    for (int i = 0; i < n; i++) {
        char c = t[i];
        if (c == 'U') {
            if (s > 1) s /= 2;  // 1 是根，没有父亲，留在原地
        } else if (c == 'L') {
            s = s * 2;
        } else {  // 'R'
            s = s * 2 + 1;
        }
    }

    cout << (long long)s << "\n";
    return 0;
}