RMQ with Shifts

In the traditional RMQ (Range Minimum Query) problem, we have a static array A. Then for each query (L, R) (LR), 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

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 ( 1n100, 000, 1q250, 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 30 characters, with no space characters inside. All operations are guaranteed to be valid.

Warning: The dataset is large, better to use faster I/O methods.

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

#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
int tree[524289], M;
int A[262145];
void setTree() {
    int i;
    for(i = 2*M-1; i > 0; i--) {
        if(i >= M) {
            tree[i] = A[i-M];
        } else {
            tree[i] = min(tree[i<<1], tree[i<<1|1]);
        }
    }
}
int query(int s, int t) {
    static int i, ans;
    ans = 0xfffffff;
    for(s = s+M-1, t = t+M+1; (s^t) != 1; ) {
        if(~s&1) {
            ans = min(ans, tree[s^1]);
        }
        if(t&1) {
            ans = min(ans, tree[t^1]);
        }
        s >>= 1, t >>= 1;
    }
    return ans;
}
void clear(int s) {
    while(s > 0) {
        tree[s] = 0xfffffff;
        s >>= 1;
    }
}
void update(int s) {
    while(s > 0) {
        tree[s] = min(tree[s<<1], tree[s<<1|1]);
        s >>= 1;
    }
}
int main() {
    int n, m, i, j;
    char cmd[1000];
    while(scanf("%d %d", &n, &m) == 2) {
        for(M = 1; M < n+2; M <<= 1);
        memset(A, 63, sizeof(A));
        for(i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        setTree();
        getchar();
        int a[50], tmp, g, idx;
        while(m--) {
            gets(cmd);
            if(cmd[0] == 'q') {
                sscanf(cmd+6, "%d,%d", &i, &j);
                printf("%d\n", query(i, j));
            } else {
                tmp = 0, g = 0, idx = 0;
                for(i = 6; cmd[i]; i++) {
                    if(cmd[i] >= '0' && cmd[i] <= '9')
                        tmp = tmp*10 + cmd[i]-'0', g = 1;
                    else {
                        if(g) {
                            a[idx++] = tmp;
                            clear(tmp+M);
                        }
                        tmp = 0, g = 0;
                    }
                }
                tmp = A[a[0]];
                for(i = 1; i < idx; i++) {
                    A[a[i-1]] = A[a[i]];
                }
                A[a[idx-1]] = tmp;
                for(i = 0; i < idx; i++) {
                    tree[a[i]+M] = A[a[i]];
                    update((a[i]+M)>>1);
                }
            }
        }
    }
    return 0;
}