uva 12299 - RMQ with Shift (선분 트 리)
12541 단어 GRADE:D데이터 구조-선분 트 리훈련 지침 - 제3 장UVA
제목 대의: 하나의 배열 을 정 하고 두 가지 조작 이 있 습 니 다.
query l r: l 에서 r 사이 의 최소 값 조회 shift x1 x2 x3: 아래 표 시 된 x1 x2 x3 의 위치 에서 수 순환 으로 길 이 를 이동 합 니 다.
문제 풀이 방향: 선분 트 리 는 최소 값 을 유지 합 니 다. 각 명령 의 길이 가 30 을 초과 하지 않 기 때문에 순환 이동 의 수가 많 지 않 습 니 다. 한 점 으로 수정 하여 처리 합 니 다.
#include
#include
#include
using namespace std;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
const int maxn = 1e5+5;
struct Node {
int l, r, val;
Node (int l = 0, int r = 0, int val = 0) {
this->set(l, r, val);
}
void set (int l, int r, int val) {
this->l = l;
this->r = r;
this->val = val;
}
}node[maxn*4];
int N, M, arr[maxn];
void pushup (int u) {
int val = min(node[lson(u)].val, node[rson(u)].val);
node[u].set(node[lson(u)].l, node[rson(u)].r, val);
}
void build_segTree (int u, int l, int r) {
if (l == r) {
node[u].set(l, r, arr[l]);
return;
}
int mid = (l + r) / 2;
build_segTree(lson(u), l, mid);
build_segTree(rson(u), mid + 1, r);
pushup(u);
}
void insert_segTree (int u, int pos, int v) {
if (node[u].l == pos && node[u].r == pos) {
node[u].val = v;
return;
}
int mid = (node[u].l + node[u].r) / 2;
if (pos <= mid)
insert_segTree(lson(u), pos, v);
else
insert_segTree(rson(u), pos, v);
pushup(u);
}
int query_segTree (int u, int l, int r) {
if (l <= node[u].l && node[u].r <= r)
return node[u].val;
int mid = (node[u].l + node[u].r) / 2;
if (r <= mid)
return query_segTree(lson(u), l, r);
else if (l > mid)
return query_segTree(rson(u), l, r);
else
return min(query_segTree(lson(u), l, r), query_segTree(rson(u), l, r));
}
void get_number (int& n, int* num, char* s) {
n = 0;
int len = strlen(s), u = 0;
for (int i = 0; i < len; i++) {
if (s[i] >= '0' && s[i] <= '9')
u = u * 10 + s[i] - '0';
else if (s[i] == ',' || s[i] == ')') {
num[n++] = u;
u = 0;
} else
u = 0;
}
}
void solve () {
int n, num[50];
char order[50];
scanf("%s", order);
get_number(n, num, order);
if (order[0] == 's') {
int tmp = arr[num[0]];
for (int i = 0; i < n - 1; i++) {
insert_segTree(1, num[i], arr[num[i+1]]);
arr[num[i]] = arr[num[i+1]];
}
insert_segTree(1, num[n-1], tmp);
arr[num[n-1]] = tmp;
} else if (order[0] == 'q')
printf("%d
", query_segTree(1, num[0], num[1]));
}
int main () {
while (scanf("%d%d", &N, &M) == 2) {
for (int i = 1; i <= N; i++)
scanf("%d", &arr[i]);
build_segTree(1, 1, N);
for (int i = 0; i < M; i++)
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 3966 Aragorn 's Story (나무 사슬 분할 + 나무 모양 배열)제목 링크: hdu 3966 Aragorn 's Story 제목: 나무 한 그루 를 정 하고 세 가지 조작 Q x: 노드 x 의 값 조회 I x y w: 노드 x 에서 y 까지 이 경로 의 모든 노드 의 값 증가 w...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.