RMQ with Shifts
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
In the traditional RMQ (Range Minimum Query) problem, we have a static array A. Then for each query (L, R) (L<=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(i1, i2, i3, …, ik) (i1<i2<...<ik, k>1): we do a left “circular shift” of A[i1], A[i2], …, A[ik].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}.
- 输入
- There will be only one test case, beginning with two integers n, q (1<=n<=100,000, 1<=q<=120,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.
- 输出
- For each query, print the minimum value (rather than index) in the requested range.
- 样例输入
-
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) - 样例输出
-
1
4
6 - 来源
- 湖南省第七届大学生计算机程序设计竞赛
- 题目大意：有个shift操作，也就是常见的更新，只是这里的更新比较别致，是交换i和i+1，i+1和i+2，i+2和i+3，etc（也有人理解为移动i、i+1、i+2...对应的数组中的值）。然后就是询问区间内的最小值。
- 解题思路：就是按题意一直更新就好了。
-
#include<bits/stdc++.h>
using namespace std;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn=110000;
const int INF=1e9;
int minv[maxn*4];
int a[maxn],cnt=0;
int b[5000];
char str[100];
void PushUP(int rt){
minv[rt]=min(minv[rt*2],minv[rt*2+1]);
}
void build(int rt,int L,int R){
if(L==R){
scanf("%d",&minv[rt]);
a[cnt++]=minv[rt];
return ;
}
build(lson);
build(rson);
PushUP(rt);
}
int get_b(int st,int en){
int cnt=0;
int tm,tmp=0;
for(int i=st;i<en;i++){
if(str[i]>='0'&&str[i]<='9'){
tm=str[i]-'0';
tmp*=10;
tmp+=tm;
}else{
b[cnt++]=tmp;
tmp=0;
}
}
return cnt;
}
void exchange(int la,int ra){
int tm=a[la];
a[la]=a[ra];
a[ra]=tm;
}
int query(int rt,int L,int R,int l_ran,int r_ran){
if(l_ran<=L&&R<=r_ran){
return minv[rt];
}
int ret_l=INF,ret_r=INF;
if(l_ran<=mid){
ret_l=query(lson,l_ran,r_ran);
}
if(r_ran>mid){
ret_r=query(rson,l_ran,r_ran);
}
return min(ret_l,ret_r);
}
void update(int rt,int L,int R,int pos,int val){
if(L==R){
minv[rt]=val;
return ;
}
if(pos<=mid){
update(lson,pos,val);
}else{
update(rson,pos,val);
}
PushUP(rt);
}
void debug(){
for(int i=1;i<16;i++)
printf("%d %d\n",i,minv[i]);
}
int main(){
int n,q,m,ans;
while(scanf("%d%d",&n,&q)!=EOF){
cnt=0;
build(1,1,n);
for(int i=0;i<q;i++){
scanf("%s",&str);
int len=strlen(str);
m= get_b(6,len);
if(str[0]=='q'){
ans=query(1,1,n,b[0],b[1]);
printf("%d\n",ans);
}else{
b[m]=b[0];
for(int i=0;i<m;i++){ //估计瞌睡了，这里迷糊了好久
update(1,1,n,b[i],a[b[i+1]-1]);
}
for(int i=0;i<m-1;i++){
exchange(b[i]-1,b[i+1]-1);
}
}
}
}
return 0;
}