题目简述:
给出n个数q个询问。对于query(a,b),输出区间(a,b)的数的最小值;对于shift(a0,a1,a2,......,an),则将第a1个数的值赋给a0,第a2个数赋给a1......,第an个数赋给an-1,第a0个数赋给an
主要思路:三叉 线段树 (单点修改,区间求最值)
其实就是一道比较裸的线段树模板题,因为题目中shift操作的字符长不超过30 char,也就是说没几个数,我们完全可以直接暴力的每个操作。
我们可以用一个数组a[]来存储原数组,这样便于交换位置时直接赋值。记得把一开始的值先存下来QAQ
然后比较麻烦的就是字符串的操作,实际也不是很麻烦,就像写快读那样写就好。
我这里用了一个自己琢磨的三叉线段树(动态开点),如有不适,自己码正常的线段树,或者在我的板子库里找找线段树那一栏。
code:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <map> using namespace std; #define go(i, j, n, k) for(int i = j; i <= n; i += k) #define fo(i, j, n, k) for(int i = j; i >= n; i -= k) #define rep(i, x) for(int i = h[x]; i; i = e[i].nxt) #define mn 500010 #define inf 1 << 30 #define ll long long #define root 1, n, rot #define lson l, m1, z[rt].l #define mson m1 + 1, m2, z[rt].m #define rson m2 + 1, r, z[rt].r #define bson l, r, rt inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct tree { int l, m, r; int x; } z[mn << 1]; // 不需要4倍,2倍就好(动态开点的服利) int cnt, n, m, rot, a[mn]; // rot 就是根节点编号(其实就是1,,,) inline void update(int rt) { // 更新这里似乎不能直接全部求最小,可能不存在这个节点 z[rt].x = inf; if(z[rt].l) z[rt].x = min(z[z[rt].l].x, z[rt].x); if(z[rt].m) z[rt].x = min(z[z[rt].m].x, z[rt].x); if(z[rt].r) z[rt].x = min(z[z[rt].r].x, z[rt].x); } void build(int l, int r, int &rt) { rt = ++cnt; if(l == r) { z[rt].x = a[l]; return; } if(r - l == 1) { build(l, l, z[rt].l), build(r, r, z[rt].r); update(rt); return; } int t = (r - l + 1) / 3 + ((r - l + 1) % 3 == 2 ? 1 : 0), m2 = l + t + t - 1, m1 = l + t - 1; build(lson), build(mson), build(rson); update(rt); } void modify(int l, int r, int rt, int now, int v) { if(l == r) { z[rt].x = v; return; } if(r - l == 1) { if(now == l) modify(l, l, z[rt].l, now, v); else if(now == r) modify(r, r, z[rt].r, now, v); update(rt); return; } int t = (r - l + 1) / 3 + ((r - l + 1) % 3 == 2 ? 1 : 0), m2 = l + t + t - 1, m1 = l + t - 1; if(now <= m1) modify(lson, now, v); else if(now <= m2) modify(mson, now, v); else modify(rson, now, v); update(rt); } int query(int l, int r, int rt, int nowl, int nowr) { if(nowl <= l && r <= nowr) return z[rt].x; if(r - l == 1) { // 如果只能有两个子节点 int ans = 0; if(nowl <= l && l <= nowr) ans += z[z[rt].l].x; if(nowl <= r && r <= nowr) ans += z[z[rt].r].x; return ans; } int t = (r - l + 1) / 3 + ((r - l + 1) % 3 == 2 ? 1 : 0), m2 = l + t + t - 1, m1 = l + t - 1; int ans = inf, f1 = 0, f2 = 0; if(nowl <= m1) ans = min(query(lson, nowl, nowr), ans), f1 = 1; if(m2 < nowr) ans = min(query(rson, nowl, nowr), ans), f2 = 1; if(!(f1 || f2) || (f1 && m1 < nowr) || (f2 && nowl <= m2)) ans = min(query(mson, nowl, nowr), ans); return ans; } // 以上代码与普通线段树的单点修改区间求最值没啥差别 // 我只是写成了三叉的而已 char s[35]; int b[35]; inline void solve() { n = read(), m = read(); go(i, 1, n, 1) a[i] = read(); build(root); go(i, 1, m, 1) { scanf("%s", s); if(s[0] == 'q') { int now = 5, x = 0, y = 0; while(s[++now] <= '9' && s[now] >= '0') x = x * 10 + s[now] - '0'; // 相当于输入x while(s[++now] <= '9' && s[now] >= '0') y = y * 10 + s[now] - '0'; // 相当于输入y printf("%d\n", query(root, x, y)); } else { int nn = 0, now = 5, x = 0, last = 0; // printf("Shift %d:\n", i); while(s[now] != ')') { x = 0; while(s[++now] <= '9' && s[now] >= '0') x = x * 10 + s[now] - '0'; b[++nn] = x; // cout << x << " "; } // puts(""); int t = a[b[1]]; go(j, 1, nn - 1, 1) { modify(root, b[j], a[b[j + 1]]); a[b[j]] = a[b[j + 1]]; } modify(root, b[nn], t); a[b[nn]] = t; } // printf("Case %d:\n", i); // go(j, 1, n, 1) // printf("%d ", a[j]); // puts(""); } } int main(){ solve(); return 0; }