Problem11219--洛谷P11186 - 三目运算

11219: 洛谷P11186 - 三目运算

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

三目运算是一种比较特殊的运算，功能类似于 `if` 语句，其语法格式如下：

`条件?数值1:数值2`，三目运算得到的结果也是数值。当条件成立时得到的结果是数值 1，不成立时得到的结果为数值 2。

例如，x>5?8:6 就是一种三目运算表达式（也是分段常数表达式，见下文）。当 $x=7$ 时，该表达式的结果为 $8$，而 $x=3$ 时，该表达式的结果为 $6$。

本题中，称满足下列条件中至少一条的字符串 $S$ 是分段常数表达式：

- 十进制正整数 $a$，如 `243`，是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x>}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。
- 如果 $a$ 为一个十进制正整数，$p,q$ 为两个分段常数表达式，则 $\texttt{x<}a\texttt{?}p\texttt{:}q$ 是分段常数表达式。

（后两条条件中， $x>a$ 和 $x<a$ 是条件，$p,q$ 为数值，该表达式是三目运算表达式。）

例如，x>154?220:x<37?16:10 是一个分段常数表达式，因为 `220` 和 x<37?16:10 都是分段常数表达式，从而整个表达式由第 2 条规则也是分段常数表达式。

给出一个分段常数表达式 $S$，保证出现的正整数均不超过 $m$。

yummy 有 $q$ 个询问，每次给出一个自然数 $x$ 的值，希望你求出分段常数表达式的值。

Input

输入的第一行有两个正整数 $m,q$，分别表示表达式出现数字的最大可能值和询问个数。

第二行有一个字符串 $S$，表示这个分段常数表达式。

之后有 $q$ 行，每行有一个自然数 $x$，表示一次询问。

Output

对于每个询问输出一行一个正整数，表示表达式的结果。

Constraints

设 $n$ 为 $S$ 中三目运算符的个数。（选手可以通过 $n$ 来估计 $S$ 的串长。）

对于全体数据，保证 $0\le n\le 10^5$，$1\le m\le 10^5$，$1\le q\le 10^5$，$1\le x\le 10^9$，且 $S$ 是分段常数表达式。

Sample 1 Input 

20 5
x>12?x<15?4:10:x<12?14:7
15
12
14
7
1000000

Sample 1 Output 

10
7
4
14
10
如果我们进行适当的换行和缩进可以得到： 
x>12?    //如果 x>12
  x<15?  //那么判断 x<15 是否成立
    4    //如果是则得到 4
    :10  //如果不是则得到 10
  :x<12? //否则（如果 x<=12) 判断 x<12 是否成立
    14   //如果是则返回 14
    :7   //如果不是则返回 7
按照这个思路模拟即可得到样例输出。

Sample 2 Input 

100000 10
x>99997?x>99998?99757:x<99998?x<99998?44121:74275:x<99998?19293:x<99998?78841:x<99998?x>99997?98175:82915:33658:x<99997?x>1?x>4?x>99994?x>99994?x>99995?x>99995?29202:x<99996?56848:12122:36426:x>99994?9114:4658:x<99994?x<10?x>4?99457:x>4?92117:50925:x>11?x<12?x>11?x>11?x>11?59616:x<12?8135:42284:x<12?1857:98644:x<12?1908:8470:x>99992?52502:x<99992?x>12?x<99991?x<18?59569:x<99989?x<18?15871:x>18?x>18?x>18?x<99986?x<99983?x<26?96999:x>26?x>99979?65694:x<27?36968:x>28?x<31?42803:x<32?26772:x>36?x<37?50549:x<38?12100:x>37?x>42?x<99978?x>99976?35142:x>43?x>43?x>99975?75881:x<99974?x<44?9884:x>99971?3445:x>44?x<50?67500:x>49?x<99970?x<99968?x<99967?x>61860?34042:x<42900?x<37062?x>11236?9657:91054:55043:27802:59132:4073:15302:1340:73712:44961:99551:87954:18093:16841:3374:41041:97702:66310:11413:15334:5392:79431:11135:36980:20146:26300:9098:87097:x<99994?x>99993?19972:x>99993?93045:50909:x>99993?91358:64562:84872:x>1?x<2?x>1?x<2?x>1?26609:x<2?67772:95373:x>1?14829:34298:30074:x<2?25512:58293:x<2?7362:68458:x<99997?x>99996?x>99996?27144:97208:x<99997?x<99997?43419:44912:x>99996?x>99996?21319:81551:x<99997?24724:89440:x>99996?x>99996?x<99997?68379:93454:49382:x>99996?x>99996?23808:x<99997?x>99996?90273:99767:x>99996?28121:67320:11971
1000000000
13609
83404
8522
1486
69359
73564
90623
35190
23048

Sample 2 Output 

99757
9657
34042
91054
91054
34042
34042
34042
9657
9657

HINT

洛谷P11186.

Source/Category

 
Submit