一 问题描述
杰克逊被邀请参加电视节目“超强记忆”，参与者会玩一个记忆游戏。主持人先告诉参与者一个数字序列 {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 查询都输出正确的答案。
四 输入和输出样例
1 输入样例
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
2 输出样例
5
五 分析
本问题涉及 6 种操作：插入、删除、区间查询、区间修改、区间反转、区间旋转，完美诠释了伸展树的神通广大。
六 设计
1 插入
在第 pos 个元素后插入一个元素 val，将 Apos 旋转到根部，再将 Apos+1 旋转到 Apos 下方，最后在 Apos+1 的左子树中插入新节点 val 即可。
2 删除
删除第 pos 个元素，将 pos-1 旋转到根部，再将 Apos+1 旋转到 Apos-1 下方，此时 Apos 就是 Apos+1 的左子树，直接删除即可。
3 区间查询
查询 [l , r] 区间的最小值时，只需将 Al-1 旋转到根，然后将 Ar+1 旋转到 Al-1 的下方，此时需要查询的 [l , r] 区间就是 Ar+1 的左子树，输出该节点的最小值即可。
4 区间修改
和区间查询类似，将 [l , r] 区间的所有元素都增加 val，只需将 Al-1 旋转到根，然后将 Ar+1 旋转到 Al-1 的下方，此时需要增加的 [l , r] 区间就是 Ar+1 的左子树，修改该 [l,r] 区间的根节点（值、区间最小值、懒标记），懒标记会在下次访问时下传。
5 区间反转
和区间查询类似，反转 [l,r] 区间时，只需将 Al-1 旋转到根，然后将 Ar+1 旋转到 Al-1 的下方，此时需要反转的 [l, r ]区间就是 Ar+1 的左子树，在该区间的根节点打上反转懒标记即可。
6 区间旋转
旋转[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; // 大小，加标记，翻转标记
}八 测试
更多推荐
超级记忆节目
发布评论