C. RMQ with Shifts

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 131072KB

64-bit integer IO format: %lld Java class name: Main

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

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 ( 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

解题：RMQ问题，更新比较有新意。。。。。。。。。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 using namespace std;

 const int maxn = ;

 struct node{

     int lt,rt,minVal;

 }tree[maxn<<];

 int d[maxn],u[],cnt;

 void build(int lt,int rt,int v){

     tree[v].lt = lt;

     tree[v].rt = rt;

     if(lt == rt){

         tree[v].minVal = d[lt];

         return;

     }

     int mid = (lt+rt)>>;

     build(lt,mid,v<<);

     build(mid+,rt,v<<|);

     tree[v].minVal = min(tree[v<<].minVal,tree[v<<|].minVal);

 }

 int query(int lt,int rt,int v){

     if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].minVal;

     int mid = (tree[v].lt+tree[v].rt)>>;

     if(rt <= mid) return query(lt,rt,v<<);

     else if(lt > mid) return query(lt,rt,v<<|);

     else return min(query(lt,mid,v<<),query(mid+,rt,v<<|));

 }

 void update(int lt,int rt,int v){

     if(tree[v].lt == tree[v].rt){

         tree[v].minVal = d[tree[v].lt];

         return;

     }

     int mid = (tree[v].lt+tree[v].rt)>>;

     if(u[rt] <= mid) update(lt,rt,v<<);

     else if(u[lt] > mid) update(lt,rt,v<<|);

     else{

         int i;

         for(i = lt; u[i] <= mid; i++);

         update(lt,i-,v<<);

         update(i,rt,v<<|);

     }

     tree[v].minVal = min(tree[v<<].minVal,tree[v<<|].minVal);

 }

 int main(){

     int n,m,i,j,len,temp;

     char str[];

     while(~scanf("%d%d",&n,&m)){

         for(i = ; i <= n; i++)

             scanf("%d",d+i);

             build(,n,);

         for(i = ; i < m; i++){

             scanf("%s",str);

             len = strlen(str);

             for(cnt = j = ; j < len;){

                 if(str[j] < '' || str[j] > '') {j++;continue;}

                 temp = ;

                 while(j < len && str[j] >= '' && str[j] <= '') {temp = temp* + (str[j]-'');j++;}

                 u[cnt++] = temp;

             }

             if(str[] == 'q'){

                 printf("%d\n",query(u[],u[],));

             }else{

                 temp = d[u[]];

                 for(cnt--,j = ; j < cnt; j++)

                     d[u[j]] = d[u[j+]];

                 d[u[j]]  = temp;

                 update(,cnt,);

             }

         }

     }

     return ;

 }

巴特西

C. RMQ with Shifts

C. RMQ with Shifts

Input

Output

Sample Input

Sample Output

最新文章

热门文章