uva 12299 RMQ with Shifts（线段树单点更新初步应用）

                              uva 12299 RMQ with Shifts

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

shift( i ₁, i ₂, i ₃,..., i _k)( i ₁ < i ₂ < ... < i _k, k > 1)

we do a left ``circular shift" of

A[i₁],

A[i₂], ...,

A[i_k].

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)

Input 

There will be only one test case, beginning with two integers

n,

q (

1n100, 000,

1q250, 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:

Output 

For each query, print the minimum value (rather than index) in the requested range.

Sample Input 

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)

Sample Output 

1 4 6

题目大意：第一行输入两个整数（数据个数，操作个数）， query(a,b)为查找区间a到b的最小值，并输出。shift(a,b,c,d...)为将a,b,c,d...全部左移，最左边的移动到最右边。

解题思路：线段树的单点更新。

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100000 * 4
int S[N], V[N], R[N], L[N];
void build(int n, int l, int r) {       //建树
	L[n] = l;
	R[n] = r;
	if (l == r) {
		S[n] = V[l];
		return ;
	}
	int mid = (l + r) / 2;
	build(n * 2, l, mid);
	build(n * 2 + 1, mid + 1, r);
	S[n] = min(S[n * 2], S[n * 2 + 1]);
}

void modify(int n, int x, int v) {       //更新

	if (L[n] == x && R[n] == x) {
		S[n] = v;
		return;
	}
	int mid = (L[n] + R[n]) / 2;

	if (x <= mid) 
		modify(n * 2, x, v);
	else 
		modify(n * 2 + 1, x, v);
	
	S[n] = min(S[n * 2], S[n * 2 + 1]);
}
 
int find(int n, int l, int r) {           //区间查找

	if (l <= L[n] && R[n] <= r) {
		return S[n];
	}
	int mid = (L[n] + R[n]) / 2;
	if(r <= mid) {
		return find(n * 2, l, r);	
	}
	else if (l > mid) {
		return find(n * 2 + 1, l, r);
	}
	else {
		return min( find(n * 2, l , r), find(2 * n + 1, l , r));
	}
}
int main() {
	int m, n;
	scanf("%d%d", &m, &n);
	int i;
	for (i = 1; i <= m; i++) 
		scanf("%d", &V[i]);
	
	build(1, 1, m);
	char s[100];
	while(n--){
		scanf("%s", s);
		if (s[0] == 'q') {
			int temp[2];
			sscanf(s,"query(%d,%d)",&temp[0],&temp[1]);
			printf("%d\n", find(1, temp[0], temp[1]));
		}
		else {
			int temp2[30] = {0}, cnt = 0,num;

			for (int k = 6; s[k] != ')'; k++) {
				if(s[k] == ',') {
					cnt++;
					continue;	
				}
				temp2[cnt] = (temp2[cnt] * 10) + s[k] - '0';
				
			}

			num = V[temp2[0]];
			for (int k = 0; k < cnt; k++) {
				modify(1, temp2[k], V[temp2[k + 1]]);
				V[temp2[k]] = V[temp2[k + 1]];
				}
			modify(1,temp2[cnt],num);
			V[temp2[cnt]] = num;
			}
	}
	return 0;
}