首页 > 代码库 > 湖南省第七届大学生计算机程序设计竞赛 RMQ with Shifts (线段树)
湖南省第七届大学生计算机程序设计竞赛 RMQ with Shifts (线段树)
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
- 来源
湖南省第七届大学生计算机程序设计竞赛
算是线段树的基础题了,单点更新,基本的操作都没有什么难度,这道题主要要搞清楚那个循环左移的,对于这个操作,开始不知道怎么操作,还有输入的时候也要注意,考验很多细节的处理,还有处理问题的一些技巧,对于这种变形还要多加练习,积累一些处理问题的经验。
可以归纳总结自己的一些模板,很多基本操作的时候可以套用,具体问题都是考察一些细节和技巧的处理。
下面是代码:
#include <cstdio> #include <algorithm> using namespace std; const int maxn=100000+10; int a[maxn]; int index[maxn]; struct node//线段树的节点结构 { int l,r,val; }t[maxn*3]; void build(int root,int l,int r)//建树 { t[root].l=l; t[root].r=r; if(l==r) { t[root].val=a[l]; return ; } int m=(l+r)>>1; build(root<<1,l,m); build(root<<1|1,m+1,r); t[root].val=min(t[root<<1].val,t[root<<1|1].val); } void update(int root,int l,int r,int val)//更新操作 { if(t[root].l==l && t[root].r==r) { t[root].val=val; return ; } int m=(t[root].l+t[root].r)>>1; if(m>=r) update(root<<1,l,r,val); else update(root<<1|1,l,r,val); t[root].val=min(t[root<<1].val,t[root<<1|1].val); } int query(int root,int l,int r)//查询 { if(t[root].l==l && t[root].r==r) return t[root].val; int m=(t[root].l+t[root].r)>>1; if(m>=r) return query(root<<1,l,r); else if(l>m) return query(root<<1|1,l,r); else return min(query(root<<1,l,m),query(root<<1|1,m+1,r)); } int main() { int n,q,l,r; char s[100]; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(int i=0;i<q;i++) { scanf("%s",s); if(s[0]=='q') { sscanf(s+5,"(%d,%d)",&l,&r); printf("%d\n",query(1,l,r)); } else//主要是对循环左移的操作 { int k,l=0,t=0; for(k=0;s[k];k++) if(s[k]=='(') break; for(int j=k+1;s[j];j++)//处理输入的字符,提出需要的数字 { while(s[j]!=',' && s[j]!=')') { t=t*10+s[j]-'0'; j++; } index[l++]=t; t=0; } t=a[index[0]]; for(int k=0;k<l;k++)//处理循环左移 { if(k==0) update(1,index[l-1],index[l-1],a[index[0]]); else update(1,index[k-1],index[k-1], a[index[k]]) ; } for(int k=0;k<l-1;k++) a[ index[k]]=a[index[k+1]]; a[index[l-1]]=t; } } return 0; }
湖南省第七届大学生计算机程序设计竞赛 RMQ with Shifts (线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。