UVa 12299 RMQ with shifts(セグメントツリー単点修正区間クエリー)
2290 ワード
コマンド長が最大30であるため、shift操作に含まれる位置の数は12を超えず、定数と見なすことができる.
各shift操作をN個の単点修正とすればよい.
コマンド文字列の解析では、次の操作を行います.
for(int j=0;j比較的便利です.
コード:
各shift操作をN個の単点修正とすればよい.
コマンド文字列の解析では、次の操作を行います.
for(int j=0;j
コード:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#include <algorithm>
#define maxn 100005
int a[maxn<<2];
int n[maxn];
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define INF 10000000
void pushup(int rt){
int lc=rt<<1,rc=rt<<1|1;
a[rt]=min(a[lc],a[rc]);
}
void build(int rt,int l,int r){
if(l==r){
a[rt]=n[l];
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int rt,int l,int r,int pos,int num){
if(l==r){
a[rt]=num;
return ;
}
int mid=(l+r)>>1;
if(mid>=pos) update(lson,pos,num);
else update(rson,pos,num);
pushup(rt);
}
int Query(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R){
return a[rt];
}
int mid=(l+r)>>1;
int res=INF;
if(mid>=L) res=min(res,Query(lson,L,R));
if(mid<R) res=min(res,Query(rson,L,R));
return res;
}
int N,Q;
int main(){
scanf("%d%d",&N,&Q);
for(int i=1;i<=N;i++){
scanf("%d",&n[i]);
}
build(1,1,N);
for(int i=1;i<=Q;i++){
char s[40];
scanf("%s",s);
if(s[0]=='q'){
int pos[2];
int p=0;
int len=strlen(s);
for(int j=0;j<len;j++){
if(isdigit(s[j])){
sscanf(&s[j],"%d",&pos[p++]);
}
while(isdigit(s[j])){
j++;
}
}
printf("%d
",Query(1,1,N,pos[0],pos[1]));
}
else{
int pos[30];
int p=0;
int len=strlen(s);
for(int j=0;j<len;j++){
if(isdigit(s[j])){
sscanf(&s[j],"%d",&pos[p++]);
}
while(isdigit(s[j])){
j++;
}
}
for(int k=0;k<p;k++){
int next=(k+1)%p;
update(1,1,N,pos[k],n[pos[next]]);
}
int tmp=n[pos[0]];
for(int j=0;j<p-1;j++){
n[pos[j]]=n[pos[j+1]];
}
n[pos[p-1]]=tmp;
}
}
return 0;
}
/*
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);
*/