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 is no longer static: we need to support another operation

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) yields 8, 6, 4, 5, 4, 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: The dataset is large, better to use faster I/O methods.

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
#include
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;
}