• 超级记忆节目


     一 问题描述

    杰克逊被邀请参加电视节目“超强记忆”,参与者会玩一个记忆游戏。主持人先告诉参与者一个数字序列 {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 处理。

    七 代码

    1. package com.platform.modules.alg.alglib.poj3580;
    2. public class Poj3580 {
    3. public String output = "";
    4. private int maxn = 200100;
    5. private int inf = 0x3f3f3f3f;
    6. int n, cnt, root; // 结点数,结点存储下标累计,树根
    7. int a[] = new int[maxn];
    8. String op;
    9. private node tr[] = new node[maxn];
    10. public String cal(String input) {
    11. int m, l, r, val;
    12. String[] line = input.split("\n");
    13. n = Integer.parseInt(line[0]);
    14. for (int i = 1; i <= n; i++) {
    15. a[i] = Integer.parseInt(line[i]);
    16. }
    17. Init();
    18. m = Integer.parseInt(line[n + 1]);
    19. int count = n + 2;
    20. while (m-- > 0) {
    21. String[] command = line[count++].split(" ");
    22. op = command[0];
    23. if (op.charAt(0) == 'A') {
    24. l = Integer.parseInt(command[1]);
    25. r = Integer.parseInt(command[2]);
    26. val = Integer.parseInt(command[3]);
    27. Add(++l, ++r, val);
    28. } else if (op.charAt(0) == 'M') {
    29. l = Integer.parseInt(command[1]);
    30. r = Integer.parseInt(command[2]);
    31. output += Min(++l, ++r) + "\n";
    32. } else if (op.charAt(0) == 'I') {
    33. l = Integer.parseInt(command[1]);
    34. val = Integer.parseInt(command[2]);
    35. Insert(++l, val);
    36. } else if (op.charAt(0) == 'D') {
    37. l = Integer.parseInt(command[1]);
    38. Delete(++l);
    39. } else if (op.charAt(0) == 'E') {
    40. l = Integer.parseInt(command[1]);
    41. r = Integer.parseInt(command[2]);
    42. Reverse(++l, ++r);
    43. } else {
    44. l = Integer.parseInt(command[1]);
    45. r = Integer.parseInt(command[2]);
    46. val = Integer.parseInt(command[3]);
    47. Revolve(++l, ++r, val);
    48. }
    49. }
    50. return output;
    51. }
    52. public Poj3580() {
    53. for (int i = 0; i < tr.length; i++) {
    54. tr[i] = new node();
    55. }
    56. }
    57. void Update(int x) {
    58. tr[x].minv = tr[x].val;
    59. tr[x].size = 1;
    60. if (tr[x].son[0] > 0) {
    61. tr[x].size += tr[tr[x].son[0]].size;
    62. tr[x].minv = Math.min(tr[x].minv, tr[tr[x].son[0]].minv);
    63. }
    64. if (tr[x].son[1] > 0) {
    65. tr[x].size += tr[tr[x].son[1]].size;
    66. tr[x].minv = Math.min(tr[x].minv, tr[tr[x].son[1]].minv);
    67. }
    68. }
    69. void Pushdown(int x) {
    70. if (tr[x].rev == 1) { // 下传翻转标记
    71. tr[x].rev ^= 1;
    72. int temp = tr[x].son[0];
    73. tr[x].son[0] = tr[x].son[1];
    74. tr[x].son[1] = temp;
    75. if (tr[x].son[0] > 0)
    76. tr[tr[x].son[0]].rev ^= 1;
    77. if (tr[x].son[1] > 0)
    78. tr[tr[x].son[1]].rev ^= 1;
    79. }
    80. if (tr[x].add == 1) { // 下传加标记
    81. if (tr[x].son[0] > 0) {
    82. tr[tr[x].son[0]].add += tr[x].add;
    83. tr[tr[x].son[0]].val += tr[x].add;
    84. tr[tr[x].son[0]].minv += tr[x].add;
    85. }
    86. if (tr[x].son[1] > 0) {
    87. tr[tr[x].son[1]].add += tr[x].add;
    88. tr[tr[x].son[1]].val += tr[x].add;
    89. tr[tr[x].son[1]].minv += tr[x].add;
    90. }
    91. tr[x].add = 0;//清除标记
    92. }
    93. }
    94. // 生成新结点
    95. int New(int father, int val) {
    96. tr[++cnt].fa = father;
    97. tr[cnt].val = val;
    98. tr[cnt].minv = val;
    99. tr[cnt].size = 1;
    100. tr[cnt].add = tr[cnt].rev = 0;
    101. tr[cnt].son[0] = tr[cnt].son[1] = 0;
    102. return cnt;
    103. }
    104. // 旋转
    105. void Rotate(int x) {
    106. Pushdown(x);
    107. int y = tr[x].fa, z = tr[y].fa;
    108. int c = (tr[y].son[0] == x) ? 1 : 0;
    109. tr[y].son[1 - c] = tr[x].son[c];
    110. tr[tr[x].son[c]].fa = y;
    111. tr[x].fa = z;
    112. if (z > 0)
    113. tr[z].son[tr[z].son[1] == y ? 1 : 0] = x;
    114. tr[x].son[c] = y;
    115. tr[y].fa = x;
    116. Update(y);
    117. Update(x);
    118. }
    119. // 将 x 旋转为 goal 的儿子
    120. void Splay(int x, int goal) {
    121. while (tr[x].fa != goal) {
    122. int y = tr[x].fa, z = tr[y].fa;
    123. if (z != goal) {
    124. if (((tr[z].son[0] == y ? 1 : 0) ^ (tr[y].son[0] == x ? 1 : 0)) == 0) {
    125. Rotate(y);
    126. } else {
    127. Rotate(x);
    128. }
    129. }
    130. Rotate(x);
    131. }
    132. // 如果 goal 是 0,则更新根为 x
    133. if (goal == 0) root = x;
    134. }
    135. int Findk(int x, int k) {
    136. while (true) {
    137. Pushdown(x);
    138. int sn = tr[x].son[0] > 0 ? tr[tr[x].son[0]].size + 1 : 1;
    139. if (k == sn)
    140. return x;
    141. if (k > sn) {
    142. k -= sn;
    143. x = tr[x].son[1];
    144. } else
    145. x = tr[x].son[0];
    146. }
    147. }
    148. // 插入值 val
    149. void Insert(int pos, int val) {
    150. int x = Findk(root, pos), y = Findk(root, pos + 1);
    151. Splay(x, 0);
    152. Splay(y, x);
    153. tr[y].son[0] = New(y, val);
    154. Update(y);
    155. Update(x);
    156. }
    157. // 删除
    158. void Delete(int pos) {
    159. int x = Findk(root, pos - 1), y = Findk(root, pos + 1);
    160. Splay(x, 0);
    161. Splay(y, x);
    162. tr[y].son[0] = 0;
    163. Update(y);
    164. Update(x);
    165. }
    166. // 找 [l,r] 区间最小值
    167. int Min(int l, int r) {
    168. int x = Findk(root, l - 1), y = Findk(root, r + 1);
    169. Splay(x, 0);
    170. Splay(y, x);
    171. return tr[tr[y].son[0]].minv;
    172. }
    173. int Build(int l, int r, int t, int fa) {
    174. if (l > r)
    175. return t;
    176. int mid = l + r >> 1;
    177. t = New(fa, a[mid]);
    178. tr[t].son[0] = Build(l, mid - 1, tr[t].son[0], t);
    179. tr[t].son[1] = Build(mid + 1, r, tr[t].son[1], t);
    180. Update(t);
    181. return t;
    182. }
    183. void Init() {
    184. cnt = root = 0;
    185. tr[0].son[0] = tr[0].son[1] = 0;
    186. root = New(0, -inf); // 创建虚结点1
    187. tr[root].son[1] = New(root, inf); // 创建虚结点2
    188. tr[root].size = 2;
    189. tr[tr[root].son[1]].son[0] = Build(1, n, tr[tr[root].son[1]].son[0], tr[root].son[1]);
    190. Update(tr[root].son[1]);
    191. Update(root);
    192. }
    193. // [l,r] 区间加上 val
    194. void Add(int l, int r, int val) {
    195. int x = Findk(root, l - 1), y = Findk(root, r + 1);
    196. Splay(x, 0);
    197. Splay(y, x);
    198. tr[tr[y].son[0]].val += val;
    199. tr[tr[y].son[0]].minv += val;
    200. tr[tr[y].son[0]].add += val;
    201. Update(y);
    202. Update(x);
    203. }
    204. // [l,r] 区间翻转
    205. void Reverse(int l, int r) {
    206. int x = Findk(root, l - 1), y = Findk(root, r + 1);
    207. Splay(x, 0);
    208. Splay(y, x);
    209. tr[tr[y].son[0]].rev ^= 1; // 加翻转标记
    210. }
    211. // 偏移 T 位
    212. void Revolve(int l, int r, int T) {
    213. T %= r - l + 1;
    214. if (T == 0) return;
    215. int x = Findk(root, r - T), y = Findk(root, r + 1);
    216. Splay(x, 0);
    217. Splay(y, x);
    218. int tmp = tr[y].son[0];
    219. tr[y].son[0] = 0;
    220. Update(y);
    221. Update(x);
    222. x = Findk(root, l - 1);
    223. y = Findk(root, l);
    224. Splay(x, 0);
    225. Splay(y, x);
    226. tr[y].son[0] = tmp;
    227. tr[tmp].fa = y;
    228. Update(y);
    229. Update(x);
    230. }
    231. }
    232. class node {
    233. int son[] = new int[2];//左右孩子0,1
    234. int val, fa; // 值,父亲
    235. int minv; // 最小值
    236. int size, add, rev; // 大小,加标记,翻转标记
    237. }

    八 测试

  • 相关阅读:
    java基于PHP+MySQL教务选课管理系统的设计与实现
    c++11 入门基础
    Android11 热点设置永不关闭
    k8s配置StatefulSet解读
    qt creator 设置 项目依赖关系
    第三章 搜索与图论(三)
    JAVA集合2-Vector
    node.js PM2部署项目
    518企业年会抽奖软件,支持撤消、轮空缺席弃奖
    企业数字化转型的关键技术有哪些?_光点科技
  • 原文地址:https://blog.csdn.net/chengqiuming/article/details/128063514