RMQ with Shifts （线段树）

RMQ with Shifts （线段树）

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。