本文共 2855 字，大约阅读时间需要 9 分钟。

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 theindices 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 operationshif t(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 shif t(2, 4, 5, 7) yields {6, 8, 4, 5, 4, 1, 2}. After that,shif t(1, 2) yields 8, 6, 4, 5, 4, 1, 2.InputThere 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 positiveintegers not greater than 100,000, the initial elements in array A. Each of the next q lines contains anoperation. Each operation is formatted as a string having no more than 30 characters, with no spacecharacters inside. All operations are guaranteed to be valid.Warning: The dataset is large, better to use faster I/O methods.OutputFor each query, print the minimum value (rather than index) in the requested range.Sample Input7 56 2 4 8 5 1 4query(3,7)shift(2,4,5,7)query(1,4)shift(1,2)query(2,2)Sample Output146

题目大概：

给你n个数，m条询问。每条询问，可以是查询区间最小值，或者是改变某些值的位置，即把第二个数的值放在第一个，第三个数放在第二个，第一个放在最后一个。形成循环，相当于单点更新。

思路：

直接用线段树维护区间最小值就行了，不过输入比较麻烦。

代码：

#include 
   
    using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=1e5+10;const int INF=0x3f3f3f3f;int sum[maxn<<2];int a[maxn];int b[maxn];int cnt=0;char q[100];int get_b(int st,int en){    int cnt=0;    int tm,tmp=0;    for(int i=st;i
    
     ='0'&&q[i]<='9'){           tm=q[i]-'0';           tmp*=10;           tmp+=tm;        }else{            b[cnt++]=tmp;            tmp=0;        }    }    return cnt;}void pushup(int rt){    sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);}void build(int l,int r,int rt){    if(l==r)    {        scanf("%d",&sum[rt]);        a[++cnt]=sum[rt];        return;    }    int m=(l+r)>>1;    build(lson);    build(rson);    pushup(rt);}void update(int p,int sc,int l,int r,int rt){    if(l==r)    {        sum[rt]=sc;        return;    }    int m=(l+r)>>1;    if(p<=m)update(p,sc,lson);    else update(p,sc,rson);    pushup(rt);}int quert(int L,int R,int l,int r,int rt){    if(L<=l&&r<=R)    {        return sum[rt];    }    int m=(l+r)>>1;    int ret=INF;    if(L<=m)ret=min(ret,quert(L,R,lson));    if(R>m)ret=min(ret,quert(L,R,rson));    return ret;}int main(){    int n,m;    scanf("%d%d",&n,&m);    build(1,n,1);    while(m--)    {        scanf("%s",q);        int l=strlen(q);        int le=get_b(6,l);        if(q[0]=='s')        {            int pre=b[0];            int ans1=a[pre];            for(int i=1;i
    
   

转载地址：https://blog.csdn.net/a1046765624/article/details/80752694 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！