UVa 12299 RMQ with shifts(セグメントツリー単点修正区間クエリー)


コマンド長が最大30であるため、shift操作に含まれる位置の数は12を超えず、定数と見なすことができる.
各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); */