首页 > 代码库 > UVA 12299 - RMQ with Shifts(线段树)
UVA 12299 - RMQ with Shifts(线段树)
UVA 12299 - RMQ with Shifts
题目链接
题意:给定一个数组,两种操作,每次query操作输出区间最小值,每次shift操作把选中位置每个位置向左移一位,最左的到最后去
思路:线段树,shift操作中位置个数不会超过30个,那么直接当作点修改来做,那么就变成了简单的线段树了
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f #define lson(x) ((x<<1) + 1) #define rson(x) ((x<<1) + 2) const int N = 100005; int n, m, shif[35], sn, num[N]; char Q[1005]; struct Node { int l, r, Min; } node[4 * N]; void handle(char *Q) { int len = strlen(Q); int num = -1; sn = 0; for (int i = 0; i < len; i++) { if (Q[i] >= '0' && Q[i] <= '9') { if (num == -1) num = Q[i] - '0'; else num = num * 10 + Q[i] - '0'; } else { if (num != -1) { shif[sn++] = num; num = -1; } } } sort(shif, shif + sn); } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; if (l == r) { node[x].Min = num[l]; return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); node[x].Min = min(node[lson(x)].Min, node[rson(x)].Min); } void set(int k, int v, int x = 0) { if (node[x].l == node[x].r) { node[x].Min = v; return; } int mid = (node[x].l + node[x].r) / 2; if (k <= mid) set(k, v, lson(x)); if (k > mid) set(k, v, rson(x)); node[x].Min = min(node[lson(x)].Min, node[rson(x)].Min); } int query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].Min; int mid = (node[x].l + node[x].r) / 2; int ans = INF; if (l <= mid) ans = min(ans, query(l, r, lson(x))); if (r > mid) ans = min(ans, query(l, r, rson(x))); return ans; } int main() { while (~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; i++) scanf("%d", &num[i]); build(1, n); while (m--) { scanf("%s", Q); handle(Q); if (Q[0] == 'q') printf("%d\n", query(shif[0], shif[1])); else { int tmp = num[shif[0]]; set(shif[sn - 1], num[shif[0]]); for (int i = 1; i < sn; i++) { set(shif[i - 1], num[shif[i]]); num[shif[i - 1]] = num[shif[i]]; } num[shif[sn - 1]] = tmp; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。