杰克逊被邀请参加电视节目“超强记忆”,参与者会玩一个记忆游戏。主持人先告诉参与者一个数字序列 {A1 , A2 , …, An },然后对该序列执行一系列操作或查询:
① ADD x y D ,表示对子序列 {Ax , …, Ay } 的每个数字都增加 D ,例如在序列 {1, 2, 3, 4, 5} 上执行 ADD 2 4 1,结果为 {1, 3, 4, 5, 5};
② REVERSE x y ,表示反转子序列 {Ax , …, Ay},例如在序列 {1, 2,3, 4, 5} 上执行 REVERSE 2 4,结果为 {1, 4, 3, 2, 5};
③ REVOLVE x y T ,表示旋转子序列 {Ax , …, Ay } T 次,例如在序列 {1, 2, 3, 4,5} 上执行 REVOLVE 2 4 2,结果为 {1, 3, 4, 2, 5};
④ INSERT x P ,表示在 Ax 后插入 P ,例如在序列 {1, 2, 3, 4, 5} 上执行 INSERT 2 4,结果为 {1, 2, 4, 3, 4, 5};
⑤ DELETE x ,表示删除 Ax ,例如在序列 {1, 2, 3, 4, 5} 上执行 DELETE 2,结果为 {1, 3, 4, 5};
⑥ MIN x y,表示查询子序列 {Ax , …, Ay } 的最小数值,例如在序列 {1, 2, 3,4, 5} 上执行 MIN 2 4,结果为 2。
为了使节目更有趣,参与者有机会求助他人。请写一个程序,正确回答每个问题,以便在杰克逊打电话时帮助他。
第 1 行输入数字 n(n≤10^5 );接下来输入 n 行描述数字序列;接着输入数字 M(M≤10^5 ),表示操作或查询的数量;然后输入 M 行描述操作或查询。
对每个 MIN 查询都输出正确的答案。
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
5
本问题涉及 6 种操作:插入、删除、区间查询、区间修改、区间反转、区间旋转,完美诠释了伸展树的神通广大。
在第 pos 个元素后插入一个元素 val,将 Apos 旋转到根部,再将 Apos+1 旋转到 Apos 下方,最后在 Apos+1 的左子树中插入新节点 val 即可。
删除第 pos 个元素,将 pos-1 旋转到根部,再将 Apos+1 旋转到 Apos-1 下方,此时 Apos 就是 Apos+1 的左子树,直接删除即可。
查询 [l , r] 区间的最小值时,只需将 Al-1 旋转到根,然后将 Ar+1 旋转到 Al-1 的下方,此时需要查询的 [l , r] 区间就是 Ar+1 的左子树,输出该节点的最小值即可。
和区间查询类似,将 [l , r] 区间的所有元素都增加 val,只需将 Al-1 旋转到根,然后将 Ar+1 旋转到 Al-1 的下方,此时需要增加的 [l , r] 区间就是 Ar+1 的左子树,修改该 [l,r] 区间的根节点(值、区间最小值、懒标记),懒标记会在下次访问时下传。
和区间查询类似,反转 [l,r] 区间时,只需将 Al-1 旋转到根,然后将 Ar+1 旋转到 Al-1 的下方,此时需要反转的 [l, r ]区间就是 Ar+1 的左子树,在该区间的根节点打上反转懒标记即可。
旋转[l,r] 区间 T 次,即将 [l,r] 区间循环右移 T 次,相当于将 [r-T+1,r] 区间的元素移动到 Al-1 之后。
可以将该 [r-T+1,r] 区间暂存后删除,再插入Al-1 之后。首先将 Ar-T 旋转到根,然后将 Ar+1 旋转到 Ar-T 的下方,此时 [r-T+1 , r] 区间就是 Ar+1 的左子树,将其暂存给 tmp 后删除。
然后将 tmp 插入 Al-1 之后。只需将 Al-1 旋转到根,然后将 Al 旋转到 Al-1 的下方,将 tmp 挂接到 Al 的左子树上,即可完成插入操作。
因为 T 有可能超过 [l , r]区间的长度(m=r-l +1),所以只需 T=T%m 。若 T 有可能为负值,则可以通过 T=(T+m )%m 处理。
- package com.platform.modules.alg.alglib.poj3580;
-
- public class Poj3580 {
- public String output = "";
- private int maxn = 200100;
- private int inf = 0x3f3f3f3f;
- int n, cnt, root; // 结点数,结点存储下标累计,树根
- int a[] = new int[maxn];
- String op;
- private node tr[] = new node[maxn];
-
- public String cal(String input) {
- int m, l, r, val;
- String[] line = input.split("\n");
- n = Integer.parseInt(line[0]);
- for (int i = 1; i <= n; i++) {
- a[i] = Integer.parseInt(line[i]);
- }
-
- Init();
- m = Integer.parseInt(line[n + 1]);
- int count = n + 2;
- while (m-- > 0) {
- String[] command = line[count++].split(" ");
- op = command[0];
-
- if (op.charAt(0) == 'A') {
- l = Integer.parseInt(command[1]);
- r = Integer.parseInt(command[2]);
- val = Integer.parseInt(command[3]);
-
- Add(++l, ++r, val);
- } else if (op.charAt(0) == 'M') {
- l = Integer.parseInt(command[1]);
- r = Integer.parseInt(command[2]);
- output += Min(++l, ++r) + "\n";
- } else if (op.charAt(0) == 'I') {
- l = Integer.parseInt(command[1]);
- val = Integer.parseInt(command[2]);
- Insert(++l, val);
- } else if (op.charAt(0) == 'D') {
- l = Integer.parseInt(command[1]);
-
- Delete(++l);
- } else if (op.charAt(0) == 'E') {
- l = Integer.parseInt(command[1]);
- r = Integer.parseInt(command[2]);
- Reverse(++l, ++r);
- } else {
- l = Integer.parseInt(command[1]);
- r = Integer.parseInt(command[2]);
- val = Integer.parseInt(command[3]);
- Revolve(++l, ++r, val);
- }
- }
-
- return output;
- }
-
-
- public Poj3580() {
- for (int i = 0; i < tr.length; i++) {
- tr[i] = new node();
- }
- }
-
- void Update(int x) {
- tr[x].minv = tr[x].val;
- tr[x].size = 1;
- if (tr[x].son[0] > 0) {
- tr[x].size += tr[tr[x].son[0]].size;
- tr[x].minv = Math.min(tr[x].minv, tr[tr[x].son[0]].minv);
- }
- if (tr[x].son[1] > 0) {
- tr[x].size += tr[tr[x].son[1]].size;
- tr[x].minv = Math.min(tr[x].minv, tr[tr[x].son[1]].minv);
- }
- }
-
- void Pushdown(int x) {
- if (tr[x].rev == 1) { // 下传翻转标记
- tr[x].rev ^= 1;
- int temp = tr[x].son[0];
- tr[x].son[0] = tr[x].son[1];
- tr[x].son[1] = temp;
- if (tr[x].son[0] > 0)
- tr[tr[x].son[0]].rev ^= 1;
- if (tr[x].son[1] > 0)
- tr[tr[x].son[1]].rev ^= 1;
- }
- if (tr[x].add == 1) { // 下传加标记
- if (tr[x].son[0] > 0) {
- tr[tr[x].son[0]].add += tr[x].add;
- tr[tr[x].son[0]].val += tr[x].add;
- tr[tr[x].son[0]].minv += tr[x].add;
- }
- if (tr[x].son[1] > 0) {
- tr[tr[x].son[1]].add += tr[x].add;
- tr[tr[x].son[1]].val += tr[x].add;
- tr[tr[x].son[1]].minv += tr[x].add;
- }
- tr[x].add = 0;//清除标记
- }
- }
-
- // 生成新结点
- int New(int father, int val) {
- tr[++cnt].fa = father;
- tr[cnt].val = val;
- tr[cnt].minv = val;
- tr[cnt].size = 1;
- tr[cnt].add = tr[cnt].rev = 0;
- tr[cnt].son[0] = tr[cnt].son[1] = 0;
- return cnt;
- }
-
- // 旋转
- void Rotate(int x) {
- Pushdown(x);
- int y = tr[x].fa, z = tr[y].fa;
- int c = (tr[y].son[0] == x) ? 1 : 0;
- tr[y].son[1 - c] = tr[x].son[c];
- tr[tr[x].son[c]].fa = y;
- tr[x].fa = z;
- if (z > 0)
- tr[z].son[tr[z].son[1] == y ? 1 : 0] = x;
- tr[x].son[c] = y;
- tr[y].fa = x;
- Update(y);
- Update(x);
- }
-
- // 将 x 旋转为 goal 的儿子
- void Splay(int x, int goal) {
- while (tr[x].fa != goal) {
- int y = tr[x].fa, z = tr[y].fa;
- if (z != goal) {
- if (((tr[z].son[0] == y ? 1 : 0) ^ (tr[y].son[0] == x ? 1 : 0)) == 0) {
- Rotate(y);
- } else {
- Rotate(x);
- }
- }
- Rotate(x);
- }
- // 如果 goal 是 0,则更新根为 x
- if (goal == 0) root = x;
- }
-
- int Findk(int x, int k) {
- while (true) {
- Pushdown(x);
- int sn = tr[x].son[0] > 0 ? tr[tr[x].son[0]].size + 1 : 1;
- if (k == sn)
- return x;
- if (k > sn) {
- k -= sn;
- x = tr[x].son[1];
- } else
- x = tr[x].son[0];
- }
- }
-
- // 插入值 val
- void Insert(int pos, int val) {
- int x = Findk(root, pos), y = Findk(root, pos + 1);
- Splay(x, 0);
- Splay(y, x);
- tr[y].son[0] = New(y, val);
- Update(y);
- Update(x);
- }
-
- // 删除
- void Delete(int pos) {
- int x = Findk(root, pos - 1), y = Findk(root, pos + 1);
- Splay(x, 0);
- Splay(y, x);
- tr[y].son[0] = 0;
- Update(y);
- Update(x);
- }
-
- // 找 [l,r] 区间最小值
- int Min(int l, int r) {
- int x = Findk(root, l - 1), y = Findk(root, r + 1);
- Splay(x, 0);
- Splay(y, x);
- return tr[tr[y].son[0]].minv;
- }
-
- int Build(int l, int r, int t, int fa) {
- if (l > r)
- return t;
- int mid = l + r >> 1;
- t = New(fa, a[mid]);
- tr[t].son[0] = Build(l, mid - 1, tr[t].son[0], t);
- tr[t].son[1] = Build(mid + 1, r, tr[t].son[1], t);
- Update(t);
- return t;
- }
-
- void Init() {
- cnt = root = 0;
- tr[0].son[0] = tr[0].son[1] = 0;
- root = New(0, -inf); // 创建虚结点1
- tr[root].son[1] = New(root, inf); // 创建虚结点2
- tr[root].size = 2;
- tr[tr[root].son[1]].son[0] = Build(1, n, tr[tr[root].son[1]].son[0], tr[root].son[1]);
- Update(tr[root].son[1]);
- Update(root);
- }
-
- // [l,r] 区间加上 val
- void Add(int l, int r, int val) {
- int x = Findk(root, l - 1), y = Findk(root, r + 1);
- Splay(x, 0);
- Splay(y, x);
- tr[tr[y].son[0]].val += val;
- tr[tr[y].son[0]].minv += val;
- tr[tr[y].son[0]].add += val;
- Update(y);
- Update(x);
- }
-
- // [l,r] 区间翻转
- void Reverse(int l, int r) {
- int x = Findk(root, l - 1), y = Findk(root, r + 1);
- Splay(x, 0);
- Splay(y, x);
- tr[tr[y].son[0]].rev ^= 1; // 加翻转标记
- }
-
- // 偏移 T 位
- void Revolve(int l, int r, int T) {
- T %= r - l + 1;
- if (T == 0) return;
- int x = Findk(root, r - T), y = Findk(root, r + 1);
- Splay(x, 0);
- Splay(y, x);
- int tmp = tr[y].son[0];
- tr[y].son[0] = 0;
- Update(y);
- Update(x);
- x = Findk(root, l - 1);
- y = Findk(root, l);
- Splay(x, 0);
- Splay(y, x);
- tr[y].son[0] = tmp;
- tr[tmp].fa = y;
- Update(y);
- Update(x);
- }
- }
-
- class node {
- int son[] = new int[2];//左右孩子0,1
- int val, fa; // 值,父亲
- int minv; // 最小值
- int size, add, rev; // 大小,加标记,翻转标记
- }