UVA12299 - RMQ with Shifts（線段樹）
題目鏈接
題目大意:要求你查詢某一段的最小值，但是還有一個shift操作，將（a0, a1, a2, a3..ak)這個K個位置的數(shù)字互相對掉，例如a0位置的值變成a1,a1位置的值變成a2...ak位置的值變成a0.
解題思路：因為shift后面的操作數(shù)最多30個，所以可以用線段樹單點修改。復(fù)雜度n*logn。用sscanf函數(shù)挺耗時的，還是自己寫處理函數(shù)。
代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int M = 35;
const int INF = 0x3f3f3f3f;
int n, q;
int v[4 * N];
int A[N];
int s[M], num[M];
int Query (int o, int l, int r, int ql, int qr) {
int m = l + (r - l)/ 2;
int ans = INF;
if (ql <= l && r <= qr)
return v[o];
if (ql <= m)
ans = min (ans, Query (2 * o, l, m, ql, qr));
if (qr > m)
ans = min (ans, Query (2 * o + 1, m + 1, r, ql, qr));
return ans;
}
void Update (int o, int l, int r, int p, int val) {
int m = l + (r - l) / 2;
if (l == r)
v[o] = val;
else {
if (p <= m)
Update (2 * o, l, m, p, val);
else
Update (2 * o + 1, m + 1, r, p, val);
v[o] = min (v[2 * o] , v[2 * o + 1]);
}
}
int get_number (char* str) {
int dex = 0;
int len = strlen (str);
s[dex] = 0;
bool flag = 0;
for (int i = 0; i < len; i++) {
if (str[i] >= '0' && str[i] <= '9') {
s[dex] = s[dex] * 10 + str[i] - '0';
flag = 1;
} else if (flag)
s[++dex] = 0;
}
return dex;
}
void solve () {
char str[N];
int x, y;
while (q--) {
scanf ("%s", str);
int dex = get_number(str);
if (str[0] == 'q') {
//memcpy (str, str + 6, sizeof (str));
//sscanf (str, "%d,%d", &x, &y);
printf ("%d
", Query (1, 1, n, s[0], s[1]));
} else {
/* memcpy (str, str + 6, sizeof (str));
sscanf (str, "%d%s", &s[dex], str);
num[dex++] = A[s[dex]];
while (sscanf (str, ",%d%s", &s[dex], str)) {
num[dex++] = A[s[dex]];
}*/
for (int i = 0; i < dex; i++)
num[i] = A[s[i]];
for (int i = 0; i < dex; i++) {
if (i + 1 < dex)
A[s[i]] = num[i + 1];
else
A[s[i]] = num[0];
Update (1, 1, n, s[i], A[s[i]]);
}
}
}
}
int main () {
while (scanf ("%d%d", &n, &q) != EOF) {
memset (v, 0, sizeof (v));
for (int i = 1; i <= n; i++) {
scanf ("%d", &A[i]);
Update (1, 1, n, i, A[i]);
}
solve();
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
