4275: Paths in a Complete Binary Tree
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：3
通过：2
题目描述
D. Paths in a Complete Binary Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
T is a complete binary tree consisting of n vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn't have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So n is a number such that n+1 is a power of 2.
In the picture you can see a complete binary tree with n=15.
Vertices are numbered from 1 to n in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.
You have to write a program that for given n answers q queries to the tree.
Each query consists of an integer number ui (1≤ui≤n) and a string si, where ui is the number of vertex, and si represents the path starting from this vertex. String si doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from si have to be processed from left to right, considering that ui is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by si ends.
For example, if ui=4 and si=«UURL», then the answer is 10.
In the picture you can see a complete binary tree with n=15.
Vertices are numbered from 1 to n in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.You have to write a program that for given n answers q queries to the tree.
Each query consists of an integer number ui (1≤ui≤n) and a string si, where ui is the number of vertex, and si represents the path starting from this vertex. String si doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from si have to be processed from left to right, considering that ui is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by si ends.
For example, if ui=4 and si=«UURL», then the answer is 10.
Input
The first line contains two integer numbers n and q (1≤n≤1018, 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 105.
Output
Print q numbers, i-th number must be the answer to the i-th query.
Example
Input
15 2 4 UURL 8 LRLLLLLLLL
Output
10 5
在图片中，你可以看到一个n＝15的完整二叉树。
顶点以一种特殊的递归方式从1到n编号：我们递归地将数字分配给左子树中的所有顶点（如果当前顶点不是叶），然后将数字分配到当前顶点，然后递归地将数值分配给右子树中的全部顶点（如果存在）。使用该算法对图片中的顶点进行精确编号。很明显，对于一个完整的二叉树的每一个大小，都有一种方法可以为所有顶点提供数字。这种编号方式称为对称。
你必须编写一个程序，针对给定的n个答案，对树进行q个查询。
每个查询由一个整数ui（1≤ui≤n）和一个字符串si组成，其中ui是顶点的数量，si表示从该顶点开始的路径。字符串si不包含除“L”、“R”和“U”之外的任何字符，这意味着分别遍历到左侧子级、右侧子级和父级。考虑到ui是路径开始的顶点，si中的字符必须从左到右进行处理。如果不可能处理一个字符（例如，转到叶子的左侧子级），那么必须跳过它。答案是si表示的路径结束的顶点数。
例如，如果ui=4，si=«UURL»，则答案为10。
输入格式
第一行包含两个整数n和q（1≤n≤1018，q≥1）。n使得n+1是2的幂。
接下来的2q行表示查询；每个查询由两个连续的行组成。这两行中的第一行包含ui（1≤ui≤n），第二行包含非空字符串si。si不包含除“L”、“R”和“U”以外的任何字符。
保证si的长度总和（对于每个i，1≤i≤q）不超过105。
接下来的2q行表示查询；每个查询由两个连续的行组成。这两行中的第一行包含ui（1≤ui≤n），第二行包含非空字符串si。si不包含除“L”、“R”和“U”以外的任何字符。
保证si的长度总和（对于每个i，1≤i≤q）不超过105。
输出格式
打印q个数字，第i个数字必须是第i个查询的答案。
输入样例 复制
15 2
4
UURL
8
LRLLLLLLLL输出样例 复制
10
5