做3d同人的网站是什么app系统软件开发

做3d同人的网站是什么,app系统软件开发,wordpress 主页图片,重庆中小企业网站建设公司线段树#xff1a;主要是用于高效解决区间查询和更新的问题#xff0c;它通过分治思想和用空间换取时间的方法#xff0c;将数组区间进行递归二分#xff0c;使其构成一颗逻辑上的二叉树#xff0c;最后使得对区间范围的操作能够在对数时间O(logN)内完成。 1、算法概述 线…线段树主要是用于高效解决区间查询和更新的问题它通过分治思想和用空间换取时间的方法将数组区间进行递归二分使其构成一颗逻辑上的二叉树最后使得对区间范围的操作能够在对数时间O(logN)内完成。1、算法概述线段树主要是用于高效解决区间查询和更新的问题它通过分治思想和用空间换取时间的方法将数组区间进行递归二分使其构成一颗逻辑上的二叉树最后使得对区间范围的操作能够在对数时间O(logN)内完成。线段树解决的问题范畴大范围信息可以只由左、右两侧信息加工出而不必遍历左右两个子范围的具体状况线段树的操作思想1构建线段树的思想用线段树解决问题的思想本质上就是把原来的数组当做一个二叉树的叶子节点然后根据范围构建上层的节点这样使得新建出来的线段树数组的根节点能够表示整个区间二分之后的位置能够表示它所包含的区间这样一层一层下来就达到了缓存的效果。因为数组能够利用下标直接表示一颗二叉树所以我们只需要空充一下原来数组的大小就可以完整的表示出一个逻辑上的二叉树。2延迟更新(懒更新)的思想线段树的另一个比较重要的思想就是延迟更新我们在构建线段树的时候已经用范围将原来的数组进行了扩充。这样如果在后续操作的时候如果要操作的范围已经完全包含了二叉树的某一个节点的范围这样我们就可以直接用缓存计算出这里的结果而不需要再往下拆分除非到不得不进行拆分的时候。当下一次操作到该位置的时候我们先查看之前有没有延迟更新的操作有的话就先下发执行然后继续延迟当前的操作。通过这种方式我们就将原来要立即执行的操作进行了延迟节省了时间。3空间换时间的思想线段树操作是用空间换时间的方法来的其构成的线段树数组必然占用更多的空间。4构建的线段树的数组的多少是根据题目的要求来定的并不是统一的,根据不同题目的要求可以加不同的方法但是一般都会有查询的方法。几个重要的参数1线段树的二叉树下标表示方式从1开始左子节点下标2i右子节点下标2i1父节点下标i/2用数组来表示二叉树有两种表示方法一种是起始索引为0左子节点下标为2i1右子节点下标为2i2父节点下标为(i-1)/2;另一种是起始索引为1左子节点下标2i右子节点下标2i1父节点下标i/2因为在线段树中要频繁计算父子节点的索引所以我们直接用起始索引为1的方法因为这个方法可以直接用位运算来计算效率比较高。2线段树数组的大小一般为4*n线段树在逻辑上是一棵完全二叉树但在用数组存储时我们通常按照“根节点为1左孩子为2i右孩子为2i1”的规则进行编号假设数组下标从1开始。当原序列长度n不是2的整数次幂时构建的线段树不是一棵满二叉树其最后一层的节点会分散在数组的不同位置。最消耗空间的情况发生在 n的值刚好超过某个2的整数次幂时例如 n 2^k 1。在这种情况下线段树需要几乎两倍的叶子节点空间再加上所有中间节点总的节点数在最坏情况下会接近 4n - 1。因此分配 4 * n的空间是一个安全且通用的经验值可以确保在任何情况下都不会发生数组越界。2、同时支持范围加和更新的线段树实现同时支持范围加和更新的线段树实现思路要同时支持范围内的加和更新还要支持查询某个范围内的累加和。根据线段树的思想我们需要如下的线段数组1sum数组用来统计各个空间的累加和供随时查询和增加使用。2lazy数组用来标记当前位置有没有已经存在累加和的懒更新有值表示存在累加的懒更新为0表示没有3update数组用来区分lazy的位置的值是否为更新操作为1表示是更新操作0表示是增加操作。4change数组用来记录当前位置懒更新的值。sum数组是直接放结果的lazy、update、change数组是为了懒更新准备的。其中lazy是为了累加和的懒更新准备的update和change是为了更新操作的懒更新准备的。操作的流程如下1在新建的时候我们根据传入的原始数组进行构建线段树的sum数组。2在执行add和update操作时我们根据范围下发操作到下发的范围已经包含了当前线段树节点代表的范围的时候我们先查看有没有前面的懒更新如果有先下发执行之前的懒更新然后我们直接更新这个范围的sum值将下发操作在这个位置懒住不再下发在这种情况下在这个范围上的查询是没有问题的但是如果在这个位置往下要继续执行其他操作的时候因为下面的节点的操作懒住了所以下面的节点是错误的需要先执行这个懒住的操作然后继续执行需要的操作。/** * 同时支持范围加和更新的线段树实现 * 思路 * 要同时支持范围内的加和更新还要支持查询某个范围内的累加和。 * 根据线段树的思想我们需要如下的线段数组 * 1sum数组用来统计各个空间的累加和供随时查询和增加使用。 * 2lazy数组用来标记当前位置有没有已经存在累加和的懒更新有值表示存在累加的懒更新为0表示没有 * 3update数组用来区分lazy的位置的值是否为更新操作为1表示是更新操作0表示是增加操作。 * 4change数组用来记录当前位置懒更新的值。 * sum数组是直接放结果的lazy、update、change数组是为了懒更新准备的。 * 其中lazy是为了累加和的懒更新准备的update和change是为了更新操作的懒更新准备的。 * 操作的流程如下 * 1在新建的时候我们根据传入的原始数组进行构建线段树的sum数组。 * 2在执行add和update操作时我们根据范围下发操作到下发的范围已经包含了当前线段树节点代表的范围的时候我们先查看有没有前面的懒更新 * 如果有先下发执行之前的懒更新然后我们直接更新这个范围的sum值将下发操作在这个位置懒住不再下发 * 在这种情况下在这个范围上的查询是没有问题的但是如果在这个位置往下要继续执行其他操作的时候因为下面的节点的操作懒住了所以下面的节点 * 是错误的需要先执行这个懒住的操作然后继续执行需要的操作。 */publicstaticclassAddUpdateSegmentTree{// 用来记录右侧边界左边界为1这个边界不是线段树数组的右侧下标是初始设置的时候的原来的右侧边界privateintrightBoard;// sum[]:模拟线段树维护区间和privateint[]sum;//lazy[]为累加和懒惰标记,有值表示存在累加的懒更新为0表示没有privateint[]lazy;// change[]为更新的值privateint[]change;// update[]为更新慵懒标记,1表示是更新操作0表示是增加操作。privateboolean[]update;publicAddUpdateSegmentTree(int[]origin){intnorigin.length;// 原始数组的有边界从0到n-1,我们从1开始算的话就是从1到nthis.rightBoardn;// 以 4*n 的大小来新建数组this.sumnewint[n2];this.lazynewint[n2];this.changenewint[n2];this.updatenewboolean[n2];// origin从0开始我们新建一个从1开始的数组用来构建sum数组int[]arrnewint[n1];for(inti1;iarr.length;i){arr[i]origin[i-1];}// 初始化构建sum数组build(1,n,1,arr);}/** * 查询L..R范围上的累加和 */publiclongquery(intL,intR){// 在整个范围上查找returnquery(L,R,1,this.rightBoard,1);}/** * 在leftBoard到rightBoard的范围查询包含在L..R上的累加和 * L和R是想要更新的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatelongquery(intL,intR,intleftBoard,intrightBoard,inti){// 全包含直接返回if(LleftBoardrightBoardR){returnsum[i];}// 没有全包含先清理懒操作然后左右查找intmid(leftBoardrightBoard)1;pushDown(i,mid-leftBoard1,rightBoard-mid);longans0;if(Lmid){ansquery(L,R,leftBoard,mid,i1);}if(Rmid){ansquery(L,R,mid1,rightBoard,i1|1);}returnans;}/** * 更新L..R范围的值为C */publicvoidupdate(intL,intR,intC){// 从整个边界开始更新update(L,R,C,1,this.rightBoard,1);}/** * 更新L..R范围的值为C * L和R是想要更新的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatevoidupdate(intL,intR,intC,intleftBoard,intrightBoard,inti){// 想要更新的范围L..R全部包含了目前的边界leftBoard..rightBoard,将这个位置懒更新if(LleftBoardrightBoardR){update[i]true;change[i]C;sum[i]C*(rightBoard-leftBoard1);// 以前累计的累加更新不需要了直接清空lazy[i]0;return;}// 当前任务躲不掉无法懒更新要继续往下发// 先将当前位置的懒操作往下发intmid(leftBoardrightBoard)1;pushDown(i,mid-leftBoard1,rightBoard-mid);// 往左右两侧进行尝试if(Lmid){update(L,R,C,leftBoard,mid,i1);}if(Rmid){update(L,R,C,mid1,rightBoard,i1|1);}// 操作完左右子树后更新当前位置pushUp(i);}/** * L..R范围每个值加上C */publicvoidadd(intL,intR,intC){// 从整个边界开始尝试add(L,R,C,1,this.rightBoard,1);}/** * L..R范围每个值加上C * L和R是想要增加的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatevoidadd(intL,intR,intC,intleftBoard,intrightBoard,inti){// 当前尝试范围被全包了懒增加if(LleftBoardrightBoardR){sum[i]C*(rightBoard-leftBoard1);lazy[i]C;return;}// 任务没有全包尝试左右边界intmid(leftBoardrightBoard)1;// 先把前面的懒操作清了pushDown(i,mid-leftBoard1,rightBoard-mid);// 尝试左右子树if(Lmid){add(L,R,C,leftBoard,mid,i1);}if(Rmid){add(L,R,C,mid1,rightBoard,i1|1);}// 操作完左右子树后更新当前位置pushUp(i);}/** * 在初始化阶段构建sum数组 * 在arr[l~r]范围上去build1~n * i : 这个范围在sum中的下标 */privatevoidbuild(intl,intr,inti,int[]arr){// 到叶子节点和就是其本身if(lr){sum[i]arr[l];return;}// 不是叶子节点需要先构建下面的节点然后计算出当前节点// 中间节点的下标 mid(lr)/2intmid(lr)1;// 构建左子节点,2*ibuild(l,mid,i1,arr);// 构建右子节点,i 1 | 1 i * 2 1build(mid1,r,i1|1,arr);// 根据左右子节点计算当前节点的和pushUp(i);}/** * 根据左右子节点计算当前节点的和 * i 要求的当前节点的下标 */privatevoidpushUp(inti){// sum[i] sum[2*i] sum[2*11]sum[i]sum[i1]sum[i1|1];}/** * 之前的所有懒增加和懒更新从父范围发给左右两个子范围 * * param i :当前节点的下标 * param leftCount 左子树的节点个数 * param rightCount : 右子树的节点个数 */publicvoidpushDown(inti,intleftCount,intrightCount){// 处理更新操作的懒更新if(update[i]){// 推到左侧update[i1]true;change[i1]change[i];// 推到右侧update[i1|1]true;change[i1|1]change[i];// 已经更新了就不需要记录原来的累加和的操作了直接清空左右子树的累加和懒更新lazy[i1]0;lazy[i1|1]0;// 求左右两个节点的和sum[i1]change[i]*leftCount;sum[i1|1]change[i]*rightCount;// 清楚懒更新标记update[i]false;}// 处理累加操作的懒更新,if(lazy[i]!0){// 更新左子树lazy[i1]lazy[i];sum[i1]lazy[i]*leftCount;// 更新右子树lazy[i1|1]lazy[i];sum[i1|1]lazy[i]*rightCount;// 清空标记lazy[i]0;}}}整体代码和测试如下/** * 线段树主要是用于高效解决区间查询和更新的问题它通过分治思想和用空间换取时间的方法将数组区间进行递归二分使其构成一颗逻辑上的二叉树 * 最后使得对区间范围的操作能够在对数时间O(logN)内完成。 * 线段树解决的问题范畴大范围信息可以只由左、右两侧信息加工出而不必遍历左右两个子范围的具体状况 * br * 线段树的操作思想 * 1构建线段树的思想用线段树解决问题的思想本质上就是把原来的数组当做一个二叉树的叶子节点然后根据范围构建上层的节点 * 这样使得新建出来的线段树数组的根节点能够表示整个区间二分之后的位置能够表示它所包含的区间这样一层一层下来就达到了缓存的效果。 * 因为数组能够利用下标直接表示一颗二叉树所以我们只需要空充一下原来数组的大小就可以完整的表示出一个逻辑上的二叉树。 * 2延迟更新(懒更新)的思想线段树的另一个比较重要的思想就是延迟更新我们在构建线段树的时候已经用范围将原来的数组进行了扩充。这样如果在后续操作的时候 * 如果要操作的范围已经完全包含了二叉树的某一个节点的范围这样我们就可以直接用缓存计算出这里的结果而不需要再往下拆分除非到不得不进行拆分的时候。 * 当下一次操作到该位置的时候我们先查看之前有没有延迟更新的操作有的话就先下发执行然后继续延迟当前的操作。 * 通过这种方式我们就将原来要立即执行的操作进行了延迟节省了时间。 * 3空间换时间的思想线段树操作是用空间换时间的方法来的其构成的线段树数组必然占用更多的空间。 * 4构建的线段树的数组的多少是根据题目的要求来定的并不是统一的,根据不同题目的要求可以加不同的方法但是一般都会有查询的方法。 * br * 几个重要的参数 * 1线段树的二叉树下标表示方式从1开始左子节点下标2*i右子节点下标2*i1父节点下标i/2 * 用数组来表示二叉树有两种表示方法 * 一种是起始索引为0左子节点下标为2*i1右子节点下标为2*i2父节点下标为(i-1)/2; * 另一种是起始索引为1左子节点下标2*i右子节点下标2*i1父节点下标i/2 * 因为在线段树中要频繁计算父子节点的索引所以我们直接用起始索引为1的方法因为这个方法可以直接用位运算来计算效率比较高。 * 2线段树数组的大小一般为4*n * 线段树在逻辑上是一棵完全二叉树但在用数组存储时我们通常按照“根节点为1左孩子为2i右孩子为2i1”的规则进行编号假设数组下标从1开始。 * 当原序列长度n不是2的整数次幂时构建的线段树不是一棵满二叉树其最后一层的节点会分散在数组的不同位置。 * 最消耗空间的情况发生在 n的值刚好超过某个2的整数次幂时例如 n 2^k 1。 * 在这种情况下线段树需要几乎两倍的叶子节点空间再加上所有中间节点总的节点数在最坏情况下会接近 4n - 1。 * 因此分配 4 * n的空间是一个安全且通用的经验值可以确保在任何情况下都不会发生数组越界。 * */publicclassSegmentTree{/** * 同时支持范围加和更新的线段树实现 * 思路 * 要同时支持范围内的加和更新还要支持查询某个范围内的累加和。 * 根据线段树的思想我们需要如下的线段数组 * 1sum数组用来统计各个空间的累加和供随时查询和增加使用。 * 2lazy数组用来标记当前位置有没有已经存在累加和的懒更新有值表示存在累加的懒更新为0表示没有 * 3update数组用来区分lazy的位置的值是否为更新操作为1表示是更新操作0表示是增加操作。 * 4change数组用来记录当前位置懒更新的值。 * sum数组是直接放结果的lazy、update、change数组是为了懒更新准备的。 * 其中lazy是为了累加和的懒更新准备的update和change是为了更新操作的懒更新准备的。 * 操作的流程如下 * 1在新建的时候我们根据传入的原始数组进行构建线段树的sum数组。 * 2在执行add和update操作时我们根据范围下发操作到下发的范围已经包含了当前线段树节点代表的范围的时候我们先查看有没有前面的懒更新 * 如果有先下发执行之前的懒更新然后我们直接更新这个范围的sum值将下发操作在这个位置懒住不再下发 * 在这种情况下在这个范围上的查询是没有问题的但是如果在这个位置往下要继续执行其他操作的时候因为下面的节点的操作懒住了所以下面的节点 * 是错误的需要先执行这个懒住的操作然后继续执行需要的操作。 */publicstaticclassAddUpdateSegmentTree{// 用来记录右侧边界左边界为1这个边界不是线段树数组的右侧下标是初始设置的时候的原来的右侧边界privateintrightBoard;// sum[]:模拟线段树维护区间和privateint[]sum;//lazy[]为累加和懒惰标记,有值表示存在累加的懒更新为0表示没有privateint[]lazy;// change[]为更新的值privateint[]change;// update[]为更新慵懒标记,1表示是更新操作0表示是增加操作。privateboolean[]update;publicAddUpdateSegmentTree(int[]origin){intnorigin.length;// 原始数组的有边界从0到n-1,我们从1开始算的话就是从1到nthis.rightBoardn;// 以 4*n 的大小来新建数组this.sumnewint[n2];this.lazynewint[n2];this.changenewint[n2];this.updatenewboolean[n2];// origin从0开始我们新建一个从1开始的数组用来构建sum数组int[]arrnewint[n1];for(inti1;iarr.length;i){arr[i]origin[i-1];}// 初始化构建sum数组build(1,n,1,arr);}/** * 查询L..R范围上的累加和 */publiclongquery(intL,intR){// 在整个范围上查找returnquery(L,R,1,this.rightBoard,1);}/** * 在leftBoard到rightBoard的范围查询包含在L..R上的累加和 * L和R是想要更新的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatelongquery(intL,intR,intleftBoard,intrightBoard,inti){// 全包含直接返回if(LleftBoardrightBoardR){returnsum[i];}// 没有全包含先清理懒操作然后左右查找intmid(leftBoardrightBoard)1;pushDown(i,mid-leftBoard1,rightBoard-mid);longans0;if(Lmid){ansquery(L,R,leftBoard,mid,i1);}if(Rmid){ansquery(L,R,mid1,rightBoard,i1|1);}returnans;}/** * 更新L..R范围的值为C */publicvoidupdate(intL,intR,intC){// 从整个边界开始更新update(L,R,C,1,this.rightBoard,1);}/** * 更新L..R范围的值为C * L和R是想要更新的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatevoidupdate(intL,intR,intC,intleftBoard,intrightBoard,inti){// 想要更新的范围L..R全部包含了目前的边界leftBoard..rightBoard,将这个位置懒更新if(LleftBoardrightBoardR){update[i]true;change[i]C;sum[i]C*(rightBoard-leftBoard1);// 以前累计的累加更新不需要了直接清空lazy[i]0;return;}// 当前任务躲不掉无法懒更新要继续往下发// 先将当前位置的懒操作往下发intmid(leftBoardrightBoard)1;pushDown(i,mid-leftBoard1,rightBoard-mid);// 往左右两侧进行尝试if(Lmid){update(L,R,C,leftBoard,mid,i1);}if(Rmid){update(L,R,C,mid1,rightBoard,i1|1);}// 操作完左右子树后更新当前位置pushUp(i);}/** * L..R范围每个值加上C */publicvoidadd(intL,intR,intC){// 从整个边界开始尝试add(L,R,C,1,this.rightBoard,1);}/** * L..R范围每个值加上C * L和R是想要增加的范围边界 * leftBoard和rightBoard是线段树二分的左右边界 * i是sum数组的下标位置 * 也就是说leftBoard和rightBoard是i下标对应的范围 */privatevoidadd(intL,intR,intC,intleftBoard,intrightBoard,inti){// 当前尝试范围被全包了懒增加if(LleftBoardrightBoardR){sum[i]C*(rightBoard-leftBoard1);lazy[i]C;return;}// 任务没有全包尝试左右边界intmid(leftBoardrightBoard)1;// 先把前面的懒操作清了pushDown(i,mid-leftBoard1,rightBoard-mid);// 尝试左右子树if(Lmid){add(L,R,C,leftBoard,mid,i1);}if(Rmid){add(L,R,C,mid1,rightBoard,i1|1);}// 操作完左右子树后更新当前位置pushUp(i);}/** * 在初始化阶段构建sum数组 * 在arr[l~r]范围上去build1~n * i : 这个范围在sum中的下标 */privatevoidbuild(intl,intr,inti,int[]arr){// 到叶子节点和就是其本身if(lr){sum[i]arr[l];return;}// 不是叶子节点需要先构建下面的节点然后计算出当前节点// 中间节点的下标 mid(lr)/2intmid(lr)1;// 构建左子节点,2*ibuild(l,mid,i1,arr);// 构建右子节点,i 1 | 1 i * 2 1build(mid1,r,i1|1,arr);// 根据左右子节点计算当前节点的和pushUp(i);}/** * 根据左右子节点计算当前节点的和 * i 要求的当前节点的下标 */privatevoidpushUp(inti){// sum[i] sum[2*i] sum[2*11]sum[i]sum[i1]sum[i1|1];}/** * 之前的所有懒增加和懒更新从父范围发给左右两个子范围 * * param i :当前节点的下标 * param leftCount 左子树的节点个数 * param rightCount : 右子树的节点个数 */publicvoidpushDown(inti,intleftCount,intrightCount){// 处理更新操作的懒更新if(update[i]){// 推到左侧update[i1]true;change[i1]change[i];// 推到右侧update[i1|1]true;change[i1|1]change[i];// 已经更新了就不需要记录原来的累加和的操作了直接清空左右子树的累加和懒更新lazy[i1]0;lazy[i1|1]0;// 求左右两个节点的和sum[i1]change[i]*leftCount;sum[i1|1]change[i]*rightCount;// 清楚懒更新标记update[i]false;}// 处理累加操作的懒更新,if(lazy[i]!0){// 更新左子树lazy[i1]lazy[i];sum[i1]lazy[i]*leftCount;// 更新右子树lazy[i1|1]lazy[i];sum[i1|1]lazy[i]*rightCount;// 清空标记lazy[i]0;}}}/** * 用暴力方法实现的对数器 */publicstaticclassComparator{publicint[]arr;publicComparator(int[]origin){arrnewint[origin.length1];for(inti0;iorigin.length;i){arr[i1]origin[i];}}publicvoidupdate(intL,intR,intC){for(intiL;iR;i){arr[i]C;}}publicvoidadd(intL,intR,intC){for(intiL;iR;i){arr[i]C;}}publiclongquery(intL,intR){longans0;for(intiL;iR;i){ansarr[i];}returnans;}}publicstaticvoidmain(String[]args){intlen100;intmax1000;inttestTimes5000;intaddOrUpdateTimes1000;intqueryTimes500;System.out.println(开始测试);for(inti0;itestTimes;i){int[]origingenarateRandomArray(len,max);AddUpdateSegmentTreesegnewAddUpdateSegmentTree(origin);intNorigin.length;ComparatorrignewComparator(origin);for(intj0;jaddOrUpdateTimes;j){intnum1(int)(Math.random()*N)1;intnum2(int)(Math.random()*N)1;intLMath.min(num1,num2);intRMath.max(num1,num2);intC(int)(Math.random()*max)-(int)(Math.random()*max);if(Math.random()0.5){seg.add(L,R,C);rig.add(L,R,C);}else{seg.update(L,R,C);rig.update(L,R,C);}}for(intk0;kqueryTimes;k){intnum1(int)(Math.random()*N)1;intnum2(int)(Math.random()*N)1;intLMath.min(num1,num2);intRMath.max(num1,num2);longans1seg.query(L,R);longans2rig.query(L,R);if(ans1!ans2){System.out.println(查询错误);System.out.printf(segmentAns:%d,comparatorAns:%d\n,ans1,ans2);break;}}}System.out.println(结束测试);}publicstaticint[]genarateRandomArray(intlen,intmax){intsize(int)(Math.random()*len)1;int[]originnewint[size];for(inti0;isize;i){origin[i](int)(Math.random()*max)-(int)(Math.random()*max);}returnorigin;}}3、题目掉落的方块题目掉落的方块想象一下标准的俄罗斯方块游戏X轴是积木最终下落到底的轴线下面是这个游戏的简化版1只会下落正方形积木2[a,b] - 代表一个边长为b的正方形积木积木左边缘沿着X a这条线从上方掉落3认为整个X轴都可能接住积木也就是说简化版游戏是没有整体的左右边界的4没有整体的左右边界所以简化版游戏不会消除积木因为不会有哪一层被填满。给定一个N*2的二维数组matrix可以代表N个积木依次掉落返回每一次掉落之后的最大高度测试链接https://leetcode.cn/problems/falling-squares/线段树的解法思路本题目是一个一个的正方形往下落[a,b] 代表一个边长为b的正方形积木积木左边缘沿着X a这条线从上方掉落,因为没有消除所以我们可以转换成对线段树的操作比如[a,b]就代表了在[a,ab-1]这个区间上的高度都增加了b不能包含ab否则会让一侧的掉不下来。因为题目求的是最大的宽度所以在线段树统计的时候父节点不再是统计累加和而是左右子节点的最大值。同时因为这里每次落下来都是增加一个高度所以我们可以只写一个update方法每次计算出来高度以后直接更新到线段树中。还有一个问题就是线段树的范围的问题因为题目并没有给定具体的x轴的大小所以我们就要将所有的方块先遍历一遍然后将其用到的范围离散转化到一个区间内。这个过程我们可以用TreeSet来排序计算出每个方块的左右边界然后统计出每个点的累计值放到一个map中这样从map中取到某个坐标的累计值就是转换成的点的坐标这样做的好处是将离散的点转成了连续的节省空间。importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.TreeSet;/** * 题目掉落的方块 * 想象一下标准的俄罗斯方块游戏X轴是积木最终下落到底的轴线 * 下面是这个游戏的简化版 * 1只会下落正方形积木 * 2[a,b] - 代表一个边长为b的正方形积木积木左边缘沿着X a这条线从上方掉落 * 3认为整个X轴都可能接住积木也就是说简化版游戏是没有整体的左右边界的 * 4没有整体的左右边界所以简化版游戏不会消除积木因为不会有哪一层被填满。 * 给定一个N*2的二维数组matrix可以代表N个积木依次掉落 * 返回每一次掉落之后的最大高度 * 测试链接https://leetcode.cn/problems/falling-squares/ */publicclassQ1_FallingSquares{/** * 线段树的解法 * 思路 * 本题目是一个一个的正方形往下落[a,b] 代表一个边长为b的正方形积木积木左边缘沿着X a这条线从上方掉落, * 因为没有消除所以我们可以转换成对线段树的操作比如[a,b]就代表了在[a,ab-1]这个区间上的高度都增加了b不能包含ab否则会让一侧的掉不下来。 * 因为题目求的是最大的宽度所以在线段树统计的时候父节点不再是统计累加和而是左右子节点的最大值。 * 同时因为这里每次落下来都是增加一个高度所以我们可以只写一个update方法每次计算出来高度以后直接更新到线段树中。 * 还有一个问题就是线段树的范围的问题因为题目并没有给定具体的x轴的大小所以我们就要将所有的方块先遍历一遍然后将其用到的范围离散转化到一个区间内。 * 这个过程我们可以用TreeSet来排序计算出每个方块的左右边界然后统计出每个点的累计值放到一个map中这样从map中取到某个坐标的累计值 * 就是转换成的点的坐标这样做的好处是将离散的点转成了连续的节省空间。 */publicListIntegerfallingSquares(int[][]positions){// 先将所有的坐标连续化方便线段树的操作HashMapInteger,Integermapindex(positions);intNmap.size();SegmentTreesegmentTreenewSegmentTree(N);intmax0;ListIntegerresnewArrayList();// 每落一个正方形收集一下所有东西组成的图像最高高度是什么for(int[]arr:positions){intLmap.get(arr[0]);intRmap.get(arr[0]arr[1]-1);// 查询当前区间的最大值计算出新的坐标intheightsegmentTree.query(L,R,1,N,1)arr[1];maxMath.max(max,height);res.add(max);// 更新当前区间的最大值segmentTree.update(L,R,height,1,N,1);}returnres;}/** * 将离散的坐标转为连续的坐标方便线段树的操作 */publicHashMapInteger,Integerindex(int[][]positions){TreeSetIntegerposnewTreeSet();for(int[]arr:positions){pos.add(arr[0]);pos.add(arr[0]arr[1]-1);}HashMapInteger,IntegermapnewHashMap();intcount0;for(Integerindex:pos){map.put(index,count);}returnmap;}/** * 支持最大值的线段树 */publicstaticclassSegmentTree{privateint[]max;privateint[]change;privateboolean[]update;publicSegmentTree(intsize){intNsize1;maxnewint[N2];changenewint[N2];updatenewboolean[N2];}privatevoidpushUp(intrt){max[rt]Math.max(max[rt1],max[rt1|1]);}// ln表示左子树元素结点个数rn表示右子树结点个数privatevoidpushDown(intrt,intln,intrn){if(update[rt]){update[rt1]true;update[rt1|1]true;change[rt1]change[rt];change[rt1|1]change[rt];max[rt1]change[rt];max[rt1|1]change[rt];update[rt]false;}}publicvoidupdate(intL,intR,intC,intl,intr,intrt){if(LlrR){update[rt]true;change[rt]C;max[rt]C;return;}intmid(lr)1;pushDown(rt,mid-l1,r-mid);if(Lmid){update(L,R,C,l,mid,rt1);}if(Rmid){update(L,R,C,mid1,r,rt1|1);}pushUp(rt);}publicintquery(intL,intR,intl,intr,intrt){if(LlrR){returnmax[rt];}intmid(lr)1;pushDown(rt,mid-l1,r-mid);intleft0;intright0;if(Lmid){leftquery(L,R,l,mid,rt1);}if(Rmid){rightquery(L,R,mid1,r,rt1|1);}returnMath.max(left,right);}}}后记个人学习总结笔记不能保证非常详细轻喷