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) (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( i 1, i 2, i 3,..., i k)( i 1 < i 2 < ... < i k, k > 1) we do a left ``circular shift" of A[ i 1], A[ i 2], ..., 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 ( 1
n
100, 000, 1
q
250, 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; }