题目详情 - RMQwithShifts - 南阳理工学院OJ

ID: 1051

远端评测题

1000ms

128MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

Hydro

In the traditional RMQ (Range Minimum Query) problem, we have a static array A. Then for each query (L, R)(L $\le$ R), we report the minimum value among A[L], A[L + 1], ..., A[R]. Note that the indices start from 1, i.e. the left-most element is A[1].

In this problem, the array A is no longer static: we need to support another operation

shift(i₁, i₂, i₃,..., i_k)(i₁ < i₂ < ... < i_k, k > 1)

we do a left ``circular shift" of A[i₁], A[i₂], ..., A[i_k].

For example, if A={6, 2, 4, 8, 5, 1, 4}, then shift(2, 4, 5, 7) yields {6, 8, 4, 5, 4, 1, 2}. After that,shift(1, 2) yields 8, 6, 4, 5, 4, 1, 2.

Input

There will be only one test case, beginning with two integers n, q ( 1<=n<=100, 000, 1<=q<=250, 000), the number of integers in array A, and the number of operations. The next line contains n positive integers not greater than 100,000, the initial elements in array A. Each of the next q lines contains an operation. Each operation is formatted as a string having no more than 100 characters, with no space characters inside. All operations are guaranteed to be valid.

Output

For each query, print the minimum value (rather than index) in the requested range.

Sample Input

7 5
6 2 4 8 5 1 4
query(3,7)
shift(2,4,5,7)
query(1,4)
shift(1,2)
query(2,2)

Sample Output

1
4
6

HINT

Source

NYOJ

#P2050. RMQwithShifts

RMQwithShifts

Input

Output

Sample Input

Sample Output

HINT

Source

统计

状态

开发

支持

#P2050. RMQwithShifts

RMQwithShifts

Input

Output

Sample Input

Sample Output

HINT

Source

统计

状态

开发

支持

还没有账户？

登录