首页 > 其他分享 >你能回答这些问题吗

你能回答这些问题吗

时间:2024-05-15 12:53:05浏览次数:19  
标签:函数 递归 int 代码 回答 问题 区间 这些 ask

连续区间问题的代码都像打卡代码那样子写,是最有通用性的

这道题目的查询也没办法像老板那样子写,还是因为我们没有办法判断左端/右端的最大连续子段和是否超过了当前区间

还有理解这个代码的时候,不要去纠结递归的细节问题,就把函数看成一个问题,即

int ask(int p,int l,int r,int x,int y)表示询问\(p\)在区间\([x,y]\)上的连续最大子段和

那么肯定就是三种情况

要么在左子节点中,为ask(p<<1,l,mid,x,y)

要么在右子节点中,为ask(p<<1|1,mid+1,r,x,y)

要么在中间,但这个时候为了判断边界,要单独写一个函数

最后来分析一下这个代码的时间复杂度。实际上我们由蓝书上的推断不难得出,我们划分区间的时候最开始应该是情况\(4(1)\),然后某一次到了情况\(4(2)\),之后就都是情况\(2\)或\(3\)了

那么对于这道题目,temp进入的那个函数显然就是情况\(4(2)\),所以至多只会有一次,而单独写的函数显然每次只会向一边递归,最多递归\(O(logn)\)次,所以总的时间复杂度仍然是\(O(nlogn)\)

标签:函数,递归,int,代码,回答,问题,区间,这些,ask
From: https://www.cnblogs.com/dingxingdi/p/18193618

相关文章

  • ubuntu linux安装MySQL后遇到的一些问题和解决方法
    Ubuntulinux安装MySQL后遇到的一些问题和解决方法版本信息ubuntu:Ubuntu24.04mysql:Ver8.0.36-2ubuntu3forLinuxonx86_64((Ubuntu))登陆安装后直接sudomysql就可以登陆分析为什么可以不用sudomysql-uroot-p呢?原因有三点直接执行mysql命令它是可以根据......
  • 解决ajax请求参数过多导致参数被截断的问题
    最近发现了个问题:ajaxpost请求查询参数数量动态变化有200-250000个,当参数超过一定数量N时,post传到后台接的参数就只有N个,多出的参数都没附到请求中,这也是奇怪的事情,浏览器对参数的个数有限制。jsconstpayload={date:"2024-05-10",sn:[]};for(leti=1;i<1000......
  • 使用c#强大的表达式树实现对象的深克隆之解决循环引用的问题
    在上一期博客里,我们提到使用使用c#强大的表达式树实现对象的深克隆,文章地址:https://www.cnblogs.com/gmmy/p/18186750。但是文章里没有解决如何实现循环引用的问题。循环引用在C#中,循环引用通常发生在两个或更多的对象相互持有对方的引用,从而形成一个闭环。这种情况在使用面向对......
  • python算法:年龄问题
    一,认识递归函数1,什么是递归?递归的工作原理是,如果函数需要处理的问题大小合适,则直接求解并返回结果,否则将问题分解成两个或多个更小的子问题,并对子问题进行相同的处理,直到问题无法分解为止2,什么是递归函数:递归函数(recursivefunction)是指在函数体中可以调用自己的函数3,语......
  • 如何优化Unity发布iOS编译出来的Framework文件过大问题
    1)如何优化Unity发布iOS编译出来的Framework文件过大问题2)ScriptableBuildPipeline打包ScritptableObject报错3)APK在OPPO上报编译错误4)如何在Sequence中模拟我的蓝图这是第385篇UWA技术知识分享的推送,精选了UWA社区的热门话题,涵盖了UWA问答、社区帖子等技术知识点,助力大家更全......
  • tui-image-editor中跨域问题
    如何安装tui-image-editor等就不再赘述,参考这篇博客即可,https://blog.csdn.net/weixin_44867717/article/details/128212251简单版参考:https://blog.csdn.net/Bonsoir777/article/details/134153807官网:https://ui.toast.com/tui-image-editor 下面说说我碰到的问题,跨域......
  • 前端问题记录
    1.前端npminstall时报错:PSD:\project\myProject\other\spring-boot-vue-master\spring-boot-vue-master\exam>npminstallnpmWARNconfigglobal`--global`,`--local`aredeprecated.Use`--location=global`instead.npmERR!codeERESOLVEnpmERR!ERESOLVE......
  • P2765 魔术球问题(最小路径点覆盖)
    link这个题目很不同,它给出的是柱子的数量,要反推球的数量。可以这样认为,给出边数,求上面的点数。每次只能在某根柱子的最上面放球->点的连接方式是一串串的,易发现图是个DAG;然后好像没什么可推的性质了。题目没给出点数,那肯定要去不断试不同的点数n,每次进行判定是否符合......
  • oracle 备份与恢复常见的七大问题
    为了最大限度保障数据的安全性,同时能在不可预计灾难的情况下保证数据的快速恢复,需要根据数据的类型和重要程度制定相应的备份和恢复方案。在这个过程中,DBA的职责就是要保证数据库(其它数据由其它岗位负责)的高可用和高性能,以下典型问题及解答可供参考。1、Oracle的几种备份方式简介......
  • N皇后问题
    递归方式N皇后#include<stdio.h>#include<math.h>#defineN5//皇后个数intq[N+1];//存储每个皇后所在的列数下标从1开始intnum=1;//记录方案数//输出当前方案的函数voidprintQ(){ printf("方案%-3d:",num); for(inti=1;i<=N;i++){ ......