{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 55%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Ho:好麻烦啊~~~~~\u003c/p\u003e \n \u003cp\u003e小Hi:小Ho你在干嘛呢?\u003c/p\u003e \n \u003cp\u003e小Ho:我在干活啊!前几天老师让我帮忙管理一下团队的人员,但是感觉好难啊。\u003c/p\u003e \n \u003cp\u003e小Hi:说来听听?\u003c/p\u003e \n \u003cp\u003e小Ho:事情是这样的。我们有一个运动同好会,每天都有人加入或者退出,所以老师让我帮忙管理一下人员。每个成员有一个互不相同的id和他对我们同好会的兴趣值val,每隔一段时间一些成员的兴趣值就会发生变化。老师有时候也会问我一些成员的兴趣值。\u003c/p\u003e \n \u003cp\u003e小Hi:所以你就需要一个表格来管理信息咯?\u003c/p\u003e \n \u003cp\u003e小Ho:是啊,但是我们同好会的成员实在是太多了!我感觉完全搞不定啊。\u003c/p\u003e \n \u003cp\u003e小Hi:这样啊,那不如让我来帮帮你吧!\u003c/p\u003e \n \u003cp\u003e小Ho:真的吗?\u003c/p\u003e \n \u003cp\u003e小Hi:当然是真的啦,小Ho,你先告诉我有多少种需要完成的事情?\u003c/p\u003e \n \u003cp\u003e小Ho:一共有4种情况:\u003c/p\u003e \n \u003cp\u003e1. 加入:一个新的成员加入同好会,我会分配给他一个没有使用的id,并且询问他的兴趣值val。\u003c/p\u003e \n \u003cp\u003e2. 修改:id在区间[a,b]内的成员,兴趣值同时改变k,k有可能是负数,表示他们失去了对同好会的兴趣。\u003c/p\u003e \n \u003cp\u003e3. 退出:id在区间[a,b]内的成员要退出同好会,虽说是区间,也有可能只有1个人。\u003c/p\u003e \n \u003cp\u003e4. 询问:老师会问我在区间[a,b]内的成员总的兴趣值。\u003c/p\u003e \n \u003cp\u003e小Hi:我明白了,让我想一想该如何解决。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:Splay\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:Splay\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:对于小Ho你遇到的问题,我觉得可以用splay来解决。\u003c/p\u003e \n \u003cp\u003e小Ho:我也想过splay,但是感觉有的操作还是很麻烦。比如统计区间内的总值之类的。\u003c/p\u003e \n \u003cp\u003e小Hi:你说的没错,所以我们需要用特殊的方法来处理这些情况。\u003c/p\u003e \n \u003cp\u003e小Ho:那应该怎么做呢?\u003c/p\u003e \n \u003cp\u003e小Hi:我们从简单的问题开始入手好了,先考虑如何来求一个区间的总值。\u003c/p\u003e \n \u003cp\u003e首先我们要改造我们的节点信息,因为每个成员有id和兴趣值val两个属性,所以节点所包含的信息肯定不止一个key了。\u003c/p\u003e \n \u003cp\u003e我们将节点改造为:\u003c/p\u003e \n \u003cpre\u003eNode:\r\n\tid, // 成员的id\r\n\tval, // 成员的兴趣值val\r\n\ttotalVal, // 以当前结点为根的子树的总兴趣值\r\n\tnum, // 以当前结点为根的子树的节点总数\u003c/pre\u003e \n \u003cp\u003e由于在splay中,树的结构是不断变化的,因此我们需要在树变化时对相关节点的totalVal和num进行更新,从而使得每个节点的totalVal和num始终保持正确值。\u003c/p\u003e \n \u003cp\u003e我们需要一个update函数来更新节点的信息:\u003c/p\u003e \n \u003cpre\u003eupdate(x):\r\n\tx.num \u003d 1\t// 初始化假设只有一个节点\r\n\tx.totalVal \u003d x.val\t// 初始化为当前结点的值\r\n\r\n\t// 将左子树的信息加入\r\n\tIf (x.left is not empty) Then\r\n\t\tx.num \u003d x.num + x.left.num\r\n\t\tx.totalVal \u003d x.totalVal + x.left.totalVal\r\n\tEnd If\r\n\t\r\n\t// 将右子树的信息加入\r\n\tIf (x.right is not empty) Then\r\n\t\tx.num \u003d x.num + x.right.num\r\n\t\tx.totalVal \u003d x.totalVal + x.right.totalVal\r\n\tEnd If\u003c/pre\u003e \n \u003cp\u003e而会改变树形态的有2种情况,一是rotate函数,因此我们需要在rotate函数中去更新信息:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\tupdate(p) // 更新p节点\r\n\tupdate(x) // 更新x节点\u003c/pre\u003e \n \u003cp\u003e此处一定要注意,由于旋转之后p节点为x的儿子,所以需要先更新p节点,再更新x的节点,才能保证数据的正确性。left-rotate(x)做对应的修改即可,不再赘述。\u003c/p\u003e \n \u003cp\u003e第二个是插入节点,需要将原来的bst_insert函数改为:\u003c/p\u003e \n \u003cpre\u003ebst_insert(root, id, val):\r\n\tIf (id \u0026lt; root.id) Then\r\n\t\tIf (root.lch is empty) Then\r\n\t\t\troot.lch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.lch, id, val)\r\n\t\tEnd If\r\n\tElse\r\n\t\tIf (root.rch is empty) Then\r\n\t\t\troot.rch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.rch, id, val)\r\n\t\tEnd If\r\n\tEnd If\r\n\tupdate(root) // 最后更新信息\r\n\tReturn root\r\n\t\r\ninsert(id, val):\r\n\tnode \u003d bst_insert(root, id, val)\r\n\tsplay(node, NULL) // 插入之后仍然要将插入的节点splay到根\u003c/pre\u003e \n \u003cp\u003e有了更新的操作,就可以直接将询问操作完成:\u003c/p\u003e \n \u003cp\u003e对于区间[a,b],我们找到a的前驱节点prev,b的后继节点next。将prev旋转至根,同时将next旋转至根的儿子。此时next的左子树就包含了[a,b]区间内所有的节点,而这颗子树根节点的totalVal,也即是我们要求的解。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,这个我理解了。但是修改操作该怎么办?\u003c/p\u003e \n \u003cp\u003e每一次修改的也是一个区间[a,b],如果要将每一个值都修改掉,还是需要花费O(n)的时间,有办法减少么?\u003c/p\u003e \n \u003cp\u003e小Hi:有的,解决办法采用了之前我们在线段树中有讲过的\u003cb\u003e懒标记\u003c/b\u003e。\u003c/p\u003e \n \u003cp\u003e首先我们再修改一次节点信息:\u003c/p\u003e \n \u003cpre\u003eNode:\r\n\tid, // 成员的id\r\n\tval, // 成员的兴趣值val\r\n\ttotalVal, // 以当前结点为根的子树的总兴趣值\r\n\tnum, // 以当前结点为根的子树的节点总数\r\n\tlazy, // 以当前结点为根的子树中,所有节点的val值都增加lazy\u003c/pre\u003e \n \u003cp\u003e在修改操作中,我们找到区间[a,b]中a的前驱节点prev,b的后继节点next。将prev旋转至根,同时将next旋转至根的儿子。此时next的左子树就包含了[a,b]区间内所有的节点。\u003c/p\u003e \n \u003cp\u003e使用函数marking来给next的左儿子打上懒标记:\u003c/p\u003e \n \u003cpre\u003emarking(node, delta):\r\n\t// 原来可能就有懒标记,因此是在lazy的基础上增加delta\r\n\tnode.lazy \u003d node.lazy + delta\r\n\t// 同时对当前结点应用上懒标记\r\n\tnode.totalVal \u003d node.totalVal + node.num * delta\r\n\tnode.val \u003d node.val + delta\r\n\u003c/pre\u003e \n \u003cp\u003e有了懒标记,接下来就要考虑什么时候将懒标记怎样将传递出去。\u003c/p\u003e \n \u003cp\u003e传递懒标记的函数为send:\u003c/p\u003e \n \u003cpre\u003esend(node):\r\n\tIf (node.left is not empty) Then\r\n\t\tmarking(node.left, node.lazy)\r\n\tEnd If\r\n\tIf (node.right is not empty) Then\r\n\t\tmarking(node.right, node.lazy)\r\n\tEnd If\r\n\tnode.lazy \u003d 0 // 清空懒标记\r\n\tupdate(node) // 同时别忘了更新一下当前结点\r\n\u003c/pre\u003e \n \u003cp\u003e最后是考虑什么时候传递懒标记。和更新操作一样,每当一个节点的信息有可能发生改变时,就需要将其懒标记传递给儿子。修改旋转和插入两个函数:\u003c/p\u003e \n \u003cp\u003e1. 旋转操作时,我们会访问p和x两个节点,由于会旋转这两个节点,其信息一定会发生改变,因此需要传递懒标记。将旋转操作修改为:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\t// left-rotate(x)做对应的修改即可\r\n\tp \u003d x.father\r\n\tsend(p)\t// 传递p节点的懒标记\r\n\tsend(x) // 传递x节点的懒标记\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\tupdate(p)\r\n\tupdate(x)\u003c/pre\u003e \n \u003cp\u003e同样,由于p和x的父子关系,需要先传递p节点的懒标记,再传递x节点的懒标记。\u003c/p\u003e \n \u003cp\u003e2. 插入操作时,我们会加入一个信息的节点,这会使得整个路径上的节点信息都发生改变,因此需要传递懒标记。则将插入操作修改为:\u003c/p\u003e \n \u003cpre\u003ebst_insert(root, id, val):\r\n\tsend(root)\r\n\tIf (id \u0026lt; root.id) Then\r\n\t\tIf (root.lch is empty) Then\r\n\t\t\troot.lch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.lch, id, val)\r\n\t\tEnd If\r\n\tElse\r\n\t\tIf (root.rch is empty) Then\r\n\t\t\troot.rch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.rch, id, val)\r\n\t\tEnd If\r\n\tEnd If\r\n\tupdate(root) // 同时也别忘了最后更新信息\r\n\tReturn root\r\n\t\r\ninsert(id, val):\r\n\tnode \u003d bst_insert(root, id, val)\r\n\tsplay(node, NULL) // 插入之后仍然要将插入的节点splay到根\r\n\u003c/pre\u003e \n \u003cp\u003e通过懒标记的方法,我们就将修改操作的复杂度降低了,不需要花费O(n)的时间去进行修改。\u003c/p\u003e \n \u003cp\u003e那么最后总结一下这4个操作分别的对应方法:\u003c/p\u003e \n \u003cp\u003e1. 插入:\u003c/p\u003e \n \u003cp\u003e直接将新的成员插入splay;插入操作中传递懒标记并且更新节点信息;最后把插入的节点splay到根。\u003c/p\u003e \n \u003cp\u003e2. 修改:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,对next的左儿子打上懒标记;旋转操作中传递懒标记并且更新节点信息。\u003c/p\u003e \n \u003cp\u003e3. 删除:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,将next的左儿子删除,并依次更新next和prev节点;旋转操作中传递懒标记并且更新节点信息。\u003c/p\u003e \n \u003cp\u003e4. 询问:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,获取next的左子树的实际总价值。\u003c/p\u003e \n \u003cp\u003e小Ho:这样好像就将所有操作的时间复杂度降低到O(log n)的水平了,我明白了!\u003c/p\u003e \n \u003cp\u003e小Hi:没错,合理地利用更新函数和懒标记就可以使得在对区间进行操作时更加快速,这也是充分利用了splay的特性。小Ho,这有帮到你了么?\u003c/p\u003e \n \u003cp\u003e小Ho:当然有了!谢谢你小Hi,我这就去实现它!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数n,表示操作数量,100≤n≤200,000\u003c/p\u003e \n \u003cp\u003e第2..n+1行:可能包含下面4种规则:\u003c/p\u003e \n \u003cp\u003e1个字母\u0027I\u0027,紧接着2个数字id,val,表示一个编号为id的新成员加入,其兴趣值为val,1≤id≤100,000,000,1≤val≤10,000,000,保证在团队中的每个人id都不相同。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027Q\u0027,紧接着2个数字a,b。表示询问团队中id在区间[a,b]的所有成员总兴趣值,保证区间内至少有一个成员,结果有可能超过int的范围。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027M\u0027,紧接着3个数字a,b,d,表示将团队中id在区间[a,b]的成员兴趣值都改变d,其中d有可能为负数。保证操作之后每个成员的兴趣值仍然在0~10,000,000。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027D\u0027,紧接着2个数字a,b,表示将团队中id在区间[a,b]的成员除去。\u003c/p\u003e \n \u003cp\u003e注意有可能出现一个id为1的成员加入团队,被除去之后,又有一个新的id为1的成员加入团队的情况。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e若干行:每行1个整数,表示针对询问的回答,保证一定有合法的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e9\r\nI 1 1\r\nI 2 2\r\nI 3 3\r\nQ 1 3\r\nM 1 2 2\r\nQ 1 3\r\nD 2 3\r\nI 4 2\r\nQ 1 4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\r\n10\r\n5\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 55%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Ho:好麻烦啊~~~~~\u003c/p\u003e \n \u003cp\u003e小Hi:小Ho你在干嘛呢?\u003c/p\u003e \n \u003cp\u003e小Ho:我在干活啊!前几天老师让我帮忙管理一下团队的人员,但是感觉好难啊。\u003c/p\u003e \n \u003cp\u003e小Hi:说来听听?\u003c/p\u003e \n \u003cp\u003e小Ho:事情是这样的。我们有一个运动同好会,每天都有人加入或者退出,所以老师让我帮忙管理一下人员。每个成员有一个互不相同的id和他对我们同好会的兴趣值val,每隔一段时间一些成员的兴趣值就会发生变化。老师有时候也会问我一些成员的兴趣值。\u003c/p\u003e \n \u003cp\u003e小Hi:所以你就需要一个表格来管理信息咯?\u003c/p\u003e \n \u003cp\u003e小Ho:是啊,但是我们同好会的成员实在是太多了!我感觉完全搞不定啊。\u003c/p\u003e \n \u003cp\u003e小Hi:这样啊,那不如让我来帮帮你吧!\u003c/p\u003e \n \u003cp\u003e小Ho:真的吗?\u003c/p\u003e \n \u003cp\u003e小Hi:当然是真的啦,小Ho,你先告诉我有多少种需要完成的事情?\u003c/p\u003e \n \u003cp\u003e小Ho:一共有4种情况:\u003c/p\u003e \n \u003cp\u003e1. 加入:一个新的成员加入同好会,我会分配给他一个没有使用的id,并且询问他的兴趣值val。\u003c/p\u003e \n \u003cp\u003e2. 修改:id在区间[a,b]内的成员,兴趣值同时改变k,k有可能是负数,表示他们失去了对同好会的兴趣。\u003c/p\u003e \n \u003cp\u003e3. 退出:id在区间[a,b]内的成员要退出同好会,虽说是区间,也有可能只有1个人。\u003c/p\u003e \n \u003cp\u003e4. 询问:老师会问我在区间[a,b]内的成员总的兴趣值。\u003c/p\u003e \n \u003cp\u003e小Hi:我明白了,让我想一想该如何解决。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:Splay\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:Splay\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:对于小Ho你遇到的问题,我觉得可以用splay来解决。\u003c/p\u003e \n \u003cp\u003e小Ho:我也想过splay,但是感觉有的操作还是很麻烦。比如统计区间内的总值之类的。\u003c/p\u003e \n \u003cp\u003e小Hi:你说的没错,所以我们需要用特殊的方法来处理这些情况。\u003c/p\u003e \n \u003cp\u003e小Ho:那应该怎么做呢?\u003c/p\u003e \n \u003cp\u003e小Hi:我们从简单的问题开始入手好了,先考虑如何来求一个区间的总值。\u003c/p\u003e \n \u003cp\u003e首先我们要改造我们的节点信息,因为每个成员有id和兴趣值val两个属性,所以节点所包含的信息肯定不止一个key了。\u003c/p\u003e \n \u003cp\u003e我们将节点改造为:\u003c/p\u003e \n \u003cpre\u003eNode:\r\n\tid, // 成员的id\r\n\tval, // 成员的兴趣值val\r\n\ttotalVal, // 以当前结点为根的子树的总兴趣值\r\n\tnum, // 以当前结点为根的子树的节点总数\u003c/pre\u003e \n \u003cp\u003e由于在splay中,树的结构是不断变化的,因此我们需要在树变化时对相关节点的totalVal和num进行更新,从而使得每个节点的totalVal和num始终保持正确值。\u003c/p\u003e \n \u003cp\u003e我们需要一个update函数来更新节点的信息:\u003c/p\u003e \n \u003cpre\u003eupdate(x):\r\n\tx.num \u003d 1\t// 初始化假设只有一个节点\r\n\tx.totalVal \u003d x.val\t// 初始化为当前结点的值\r\n\r\n\t// 将左子树的信息加入\r\n\tIf (x.left is not empty) Then\r\n\t\tx.num \u003d x.num + x.left.num\r\n\t\tx.totalVal \u003d x.totalVal + x.left.totalVal\r\n\tEnd If\r\n\t\r\n\t// 将右子树的信息加入\r\n\tIf (x.right is not empty) Then\r\n\t\tx.num \u003d x.num + x.right.num\r\n\t\tx.totalVal \u003d x.totalVal + x.right.totalVal\r\n\tEnd If\u003c/pre\u003e \n \u003cp\u003e而会改变树形态的有2种情况,一是rotate函数,因此我们需要在rotate函数中去更新信息:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\tp \u003d x.father\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\tupdate(p) // 更新p节点\r\n\tupdate(x) // 更新x节点\u003c/pre\u003e \n \u003cp\u003e此处一定要注意,由于旋转之后p节点为x的儿子,所以需要先更新p节点,再更新x的节点,才能保证数据的正确性。left-rotate(x)做对应的修改即可,不再赘述。\u003c/p\u003e \n \u003cp\u003e第二个是插入节点,需要将原来的bst_insert函数改为:\u003c/p\u003e \n \u003cpre\u003ebst_insert(root, id, val):\r\n\tIf (id \u0026lt; root.id) Then\r\n\t\tIf (root.lch is empty) Then\r\n\t\t\troot.lch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.lch, id, val)\r\n\t\tEnd If\r\n\tElse\r\n\t\tIf (root.rch is empty) Then\r\n\t\t\troot.rch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.rch, id, val)\r\n\t\tEnd If\r\n\tEnd If\r\n\tupdate(root) // 最后更新信息\r\n\tReturn root\r\n\t\r\ninsert(id, val):\r\n\tnode \u003d bst_insert(root, id, val)\r\n\tsplay(node, NULL) // 插入之后仍然要将插入的节点splay到根\u003c/pre\u003e \n \u003cp\u003e有了更新的操作,就可以直接将询问操作完成:\u003c/p\u003e \n \u003cp\u003e对于区间[a,b],我们找到a的前驱节点prev,b的后继节点next。将prev旋转至根,同时将next旋转至根的儿子。此时next的左子树就包含了[a,b]区间内所有的节点,而这颗子树根节点的totalVal,也即是我们要求的解。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,这个我理解了。但是修改操作该怎么办?\u003c/p\u003e \n \u003cp\u003e每一次修改的也是一个区间[a,b],如果要将每一个值都修改掉,还是需要花费O(n)的时间,有办法减少么?\u003c/p\u003e \n \u003cp\u003e小Hi:有的,解决办法采用了之前我们在线段树中有讲过的\u003cb\u003e懒标记\u003c/b\u003e。\u003c/p\u003e \n \u003cp\u003e首先我们再修改一次节点信息:\u003c/p\u003e \n \u003cpre\u003eNode:\r\n\tid, // 成员的id\r\n\tval, // 成员的兴趣值val\r\n\ttotalVal, // 以当前结点为根的子树的总兴趣值\r\n\tnum, // 以当前结点为根的子树的节点总数\r\n\tlazy, // 以当前结点为根的子树中,所有节点的val值都增加lazy\u003c/pre\u003e \n \u003cp\u003e在修改操作中,我们找到区间[a,b]中a的前驱节点prev,b的后继节点next。将prev旋转至根,同时将next旋转至根的儿子。此时next的左子树就包含了[a,b]区间内所有的节点。\u003c/p\u003e \n \u003cp\u003e使用函数marking来给next的左儿子打上懒标记:\u003c/p\u003e \n \u003cpre\u003emarking(node, delta):\r\n\t// 原来可能就有懒标记,因此是在lazy的基础上增加delta\r\n\tnode.lazy \u003d node.lazy + delta\r\n\t// 同时对当前结点应用上懒标记\r\n\tnode.totalVal \u003d node.totalVal + node.num * delta\r\n\tnode.val \u003d node.val + delta\r\n\u003c/pre\u003e \n \u003cp\u003e有了懒标记,接下来就要考虑什么时候将懒标记怎样将传递出去。\u003c/p\u003e \n \u003cp\u003e传递懒标记的函数为send:\u003c/p\u003e \n \u003cpre\u003esend(node):\r\n\tIf (node.left is not empty) Then\r\n\t\tmarking(node.left, node.lazy)\r\n\tEnd If\r\n\tIf (node.right is not empty) Then\r\n\t\tmarking(node.right, node.lazy)\r\n\tEnd If\r\n\tnode.lazy \u003d 0 // 清空懒标记\r\n\tupdate(node) // 同时别忘了更新一下当前结点\r\n\u003c/pre\u003e \n \u003cp\u003e最后是考虑什么时候传递懒标记。和更新操作一样,每当一个节点的信息有可能发生改变时,就需要将其懒标记传递给儿子。修改旋转和插入两个函数:\u003c/p\u003e \n \u003cp\u003e1. 旋转操作时,我们会访问p和x两个节点,由于会旋转这两个节点,其信息一定会发生改变,因此需要传递懒标记。将旋转操作修改为:\u003c/p\u003e \n \u003cpre\u003eright-rotate(x):\r\n\t// left-rotate(x)做对应的修改即可\r\n\tp \u003d x.father\r\n\tsend(p)\t// 传递p节点的懒标记\r\n\tsend(x) // 传递x节点的懒标记\r\n\tx.father \u003d p.father\r\n\tIf (p.father is not empty) Then\r\n\t\tIf (p.father.left \u003d\u003d p) Then\r\n\t\t\tp.father.left \u003d x\r\n\t\tElse\r\n\t\t\tp.father.right \u003d x\r\n\t\tEnd If\r\n\tElse\r\n\t\troot \u003d x\r\n\tEnd If\r\n\tp.left \u003d x.right\r\n\tx.right.father \u003d p\r\n\tx.right \u003d p\r\n\tp.father \u003d x\r\n\tupdate(p)\r\n\tupdate(x)\u003c/pre\u003e \n \u003cp\u003e同样,由于p和x的父子关系,需要先传递p节点的懒标记,再传递x节点的懒标记。\u003c/p\u003e \n \u003cp\u003e2. 插入操作时,我们会加入一个信息的节点,这会使得整个路径上的节点信息都发生改变,因此需要传递懒标记。则将插入操作修改为:\u003c/p\u003e \n \u003cpre\u003ebst_insert(root, id, val):\r\n\tsend(root)\r\n\tIf (id \u0026lt; root.id) Then\r\n\t\tIf (root.lch is empty) Then\r\n\t\t\troot.lch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.lch, id, val)\r\n\t\tEnd If\r\n\tElse\r\n\t\tIf (root.rch is empty) Then\r\n\t\t\troot.rch \u003d new node(id, val)\r\n\t\tElse \r\n\t\t\tbst_insert(root.rch, id, val)\r\n\t\tEnd If\r\n\tEnd If\r\n\tupdate(root) // 同时也别忘了最后更新信息\r\n\tReturn root\r\n\t\r\ninsert(id, val):\r\n\tnode \u003d bst_insert(root, id, val)\r\n\tsplay(node, NULL) // 插入之后仍然要将插入的节点splay到根\r\n\u003c/pre\u003e \n \u003cp\u003e通过懒标记的方法,我们就将修改操作的复杂度降低了,不需要花费O(n)的时间去进行修改。\u003c/p\u003e \n \u003cp\u003e那么最后总结一下这4个操作分别的对应方法:\u003c/p\u003e \n \u003cp\u003e1. 插入:\u003c/p\u003e \n \u003cp\u003e直接将新的成员插入splay;插入操作中传递懒标记并且更新节点信息;最后把插入的节点splay到根。\u003c/p\u003e \n \u003cp\u003e2. 修改:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,对next的左儿子打上懒标记;旋转操作中传递懒标记并且更新节点信息。\u003c/p\u003e \n \u003cp\u003e3. 删除:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,将next的左儿子删除,并依次更新next和prev节点;旋转操作中传递懒标记并且更新节点信息。\u003c/p\u003e \n \u003cp\u003e4. 询问:\u003c/p\u003e \n \u003cp\u003e找到a的前驱prev,b的后继next,然后将prev旋转至根,next旋转至根的儿子,获取next的左子树的实际总价值。\u003c/p\u003e \n \u003cp\u003e小Ho:这样好像就将所有操作的时间复杂度降低到O(log n)的水平了,我明白了!\u003c/p\u003e \n \u003cp\u003e小Hi:没错,合理地利用更新函数和懒标记就可以使得在对区间进行操作时更加快速,这也是充分利用了splay的特性。小Ho,这有帮到你了么?\u003c/p\u003e \n \u003cp\u003e小Ho:当然有了!谢谢你小Hi,我这就去实现它!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数n,表示操作数量,100≤n≤200,000\u003c/p\u003e \n \u003cp\u003e第2..n+1行:可能包含下面4种规则:\u003c/p\u003e \n \u003cp\u003e1个字母\u0027I\u0027,紧接着2个数字id,val,表示一个编号为id的新成员加入,其兴趣值为val,1≤id≤100,000,000,1≤val≤10,000,000,保证在团队中的每个人id都不相同。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027Q\u0027,紧接着2个数字a,b。表示询问团队中id在区间[a,b]的所有成员总兴趣值,保证区间内至少有一个成员,结果有可能超过int的范围。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027M\u0027,紧接着3个数字a,b,d,表示将团队中id在区间[a,b]的成员兴趣值都改变d,其中d有可能为负数。保证操作之后每个成员的兴趣值仍然在0~10,000,000。\u003c/p\u003e \n \u003cp\u003e1个字母\u0027D\u0027,紧接着2个数字a,b,表示将团队中id在区间[a,b]的成员除去。\u003c/p\u003e \n \u003cp\u003e注意有可能出现一个id为1的成员加入团队,被除去之后,又有一个新的id为1的成员加入团队的情况。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e若干行:每行1个整数,表示针对询问的回答,保证一定有合法的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e9\r\nI 1 1\r\nI 2 2\r\nI 3 3\r\nQ 1 3\r\nM 1 2 2\r\nQ 1 3\r\nD 2 3\r\nI 4 2\r\nQ 1 4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\r\n10\r\n5\u003c/pre\u003e \n\u003c/dd\u003e"}}]}