POJ 2104 K-th Number 平方分割 / 线段树

一、题目大意

长度为n(n<=100000)的数组,进行m次查询(m<=5000),每次查询时,输入为 i j k,返回为数组 [i,j] 的分片里第k大数字(1<=i<=j<=n,k<=j-i+1)

二、解题思路

1、平方分割

如果采用朴素的方法去计算,针对每次的i 和 j,从 i 到 j 循环把数组的元素放在一个tmp数组里,然后给tmp数组排序,输出tmp[k]的话,在最差情况下,时间复杂性为 O ( m * n * log(n) ),也就是10000000000左右,肯定是行不通的。

于是考虑使用平方分割,按 floor(sqrt(n))为一块,分成根号n块,然后把每一块的数字进行排序,根据查询的 i 和 j,找出 i 和 j 范围内所有的块,然后把 块未覆盖到的左边的和右边范围内放在一个 other数组里,把other数组排序。

这时相当于得到多个有序的块,然后我们需要找到这些块合并在一起后的第k大的,朴素的合并多的话,还是会很慢(合并两个有序数组为一个的操作次数,为其中大的数组的长度),所以考虑二分,可以对数组内所有的元素进行排序。

设一开始输入的数组为dat,那么我们把dat排序后作为sortedDat,然后 L = -1,R=n(二分时候的 l 和 r 是达不到的,都取开区间)当L+1 < R时循环,mid = (L+R)/2,然后我们再循环对这些块来使用二分,找到所有块中小于sortedDat[mid]的数量和cnt,如果cnt<k,则L=mid,否则R=mid,这样的话,最终的临界情况就是,所有块中,小于sortedDat[L]的元素为k-1个,小于sortedDat[L+1]的元素为k个,此时,sortedDat[L]就是当前区间里第k大的数。

考虑下复杂性 O(log(n)*sqrt(n)*log(n)*m),好像是可以的,但实际并不如此。

此时我们需要对算法进行优化,如何优化呢?考虑下比较糟糕的情况,假如n=100000,则我们会分316块,假设涉及的区间包含200块,那么每次二分,循环200次,然后200次循环里还有2分,起始也可能会比较慢,所以我们考虑如何把200个小块合并,假设2个相邻的合并成一个,改成100的话,速度可以快一倍。

于是我们可以在起初分桶的时候,按2 * floor(sqrt(n)) 来分一些大块,然后对这些块也都进行排序,一个大块相当于2个小块。

于是我们执行每次查询时需要进行的操作为:

1、根据区间 i j 找到包含的桶

2、根据找到的桶,来处理不在桶内,而且被 i 和 j 包含的区间,对此区域排序并记录长度。

3、循环包含的桶,如果 两个相邻的小桶可以被一个大桶替换的话,则用这个大桶替换掉小桶,依据此思路,把所有的小桶都用大桶替换。

4、 对sortedDat里面的数进行二分,L = -1,R=n,针对每次的mid,循环里利用二分找到所有涉及的小桶、大桶和其他区域里小于 sortedDat[mid]的数量总和cnt,如果cnt小于k,则L=mid,否则R=mid,循环结束时,输出sortedDat[L]即可

(如果不涉及到任何桶,那直接输出other[k-1]即可,不用走二分这个思路)

(然后利用大桶替换小桶时,可以循环涉及的小桶,如果它不是涉及到的最后一个,且它的下标 i是偶数,则它和它的下一个被一个大桶替换,否则的话这个桶保留,简单的思路就是定义一个变量i=0,设当前区间涉及的小桶数量为bucketLen,保存当前区间相关的桶的数组为bucket,然后 i < bucketLen时候循环,如果i+1小于bucketLen且bucket[i]%2==0,那么就把 i /2记录为当前涉及的大桶 bucketBig[bigLen++]=i/2,然后i +=2,否则就把 bucket[i]加到队列里,最后把不在队列里的小桶都去掉,把队列里的小桶记录下来为替换后涉及到的小桶,然后大桶就是bucketBig里的大桶)

(我针对桶的下标从0开始计算,然后下标 i 的小桶的区间为 [ i * 根号n , (i + 1) * 根号n),下标 i 的大桶的区间为[ 2 *  i * 根号n , (i + 1) * 2 * 根号n),这样的话大桶 i /2就代表小桶 i 和 i + 1,需要i%2==0 )

优化之后,就侥幸过了

(做完了之后看下书,发现书里使用平方分割每个桶是1000大小,不过我觉得比赛时靠自己思考很难想到扩到1000吧!我这种思路两个桶变成一个思路倒是容易想到而且可行!)

2、线段树

我做完了这个题目之后,读了下挑战程序设计,发现书中还有一种解决方法是线段树,维护数组的线段树也叫区域树,让叶子节点维护长度为1的有序数组,它的父节点维护长度为2有序数组,然后根节点维护 [ 0 , max(n_,2^i) ) 有序数组,

这个树也挺好创建的,就和线段树的初始化一样,先解决叶子节点,然后把两个叶子节点合并时候,就把小的数字放前面,大的数字放后面即可。

然后两个有序数组合并时,就可以定义两个指针 L和R,然后记录每个的长度lenL,lenR,设父数组的长度为lenPa,设父数组时arrPa,左孩子数组是arrL,右孩子数组是arrR

while L < lenL || R < lenR

     if R >= lenR

        arrPa[lenPa++] = arrL[L++]

    else if L <  lenL && arrL[L]<arrR[R]

        arrPa[lenPa++] = arrL[L++]

    else

        arrPa[lenPa++]=arrR[R++]

简单写了几行不标准的伪代码,两个有序数组合并成一个有序数组,就是这样的,这个效率上和STL和merge是差不多的,所以线段树初始化就可以用这个方法把 i * 2 +1和i*2+2的数组都合并到i的数组。

然后线段树维护这么大的一个数组,定义变量时候肯定没办法直接定义二维数组,我的思路就是定义一个 int *dat[262150],然后在初始化的时候:

1、如果是叶子节点就 dat[i]=new int[1],然后记录len[i]=1

2、如果是父节点,那就 dat[i]=new int[len[i*2 + 1] + len[i*2 + 2]]

初始化结束之后,我们针对每次查询,先查下线段树,找到的所有线段树节点,然后这些节点自己维护的数组肯定是有序的,所以思路也是和平方分割差不多。

把数组排序,二分排好序的数组里所有的元素,对 在区间内的 线段树节点数组 进行循环二分,记录小于 数组第mid项(拍好序数组里mid下标的) 的数量cnt,如果cnt<k,则L=mid,否则R=mid,临界情况就是,区间里小于L+1下标的元素是k个,小于L下标的元素的个数是k-1个,此时,L下标的元素就是区间内第k大的。

我一开始用vector,挂了很多次,因为当时没看书,不知道可以使用resize+merge,所有的元素都是使用循环push_back,结果一直TLE

后来想到可以先定义成指针数组,然后在初始化的时候使用 new int[10]这种,然后这样就可以当作int二维数组来用,放弃了vector之后侥幸过了。

后来我过了之后,看了下书里,发现书中使用了merge和resize,也使用了upper_bound,之后我又对我自己的代码进行调优了下,去掉了一次无用的初始化,然后发现其实不用vector、merge和resize,也不用upper_bound,全都自己实现就行,自己写new int[10]这种可变数组代替vector,自己写上文中的循环那种合并代替merge,自己写binarySearch去找小于number的数量代替upper_bound,也是可以过的,时间上也优化了一些,如下

三、代码

1、平方分割

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int bucket[320][320];
int bucket_1[160][640];
int dat[100009], sortedDat[100009], n, bQue[320], queLen, bQue_1[160], queLen_2, b, otherLen, other[100009];
queue<int> que;
void input()
{for (int i = 0; i < n; i++){scanf("%d", &dat[i]);sortedDat[i] = dat[i];}sort(sortedDat, sortedDat + n);
}
void bucketMethod()
{b = 1;while (b * b <= n){b++;}b--;for (int i = 0; ((i + 1) * b) <= n; i++){for (int j = 0; j < b; j++){bucket[i][j] = dat[j + (i * b)];}sort(bucket[i], bucket[i] + b);}for (int i = 0; ((i + 1) * 2 * b) <= n; i++){for (int j = 0; j < (2 * b); j++){bucket_1[i][j] = dat[j + (i * b * 2)];}sort(bucket_1[i], bucket_1[i] + (2 * b));}
}
void findBucket(int L, int R)
{queLen = 0;for (int i = 0; ((i + 1) * b) <= n; i++){if ((i * b) >= L && ((i + 1) * b) <= R){bQue[queLen++] = i;}}
}
void handleOther(int L, int R)
{otherLen = 0;if (queLen == 0){for (int i = L; i < R; i++){other[otherLen++] = dat[i];}}else{for (int i = L; i < (bQue[0] * b); i++){other[otherLen++] = dat[i];}for (int i = ((bQue[queLen - 1] + 1) * b); i < R; i++){other[otherLen++] = dat[i];}}if (otherLen > 0){sort(other, other + otherLen);}
}
void findBucketPlus()
{queLen_2 = 0;if (queLen == 0){return;}while (!que.empty()){que.pop();}int i = 0;while (i < queLen){if ((i + 1) < queLen && (bQue[i] % 2 == 0)){bQue_1[queLen_2++] = bQue[i] / 2;i += 2;}else{que.push(bQue[i]);i++;}}if (queLen_2 != 0){queLen = 0;while (!que.empty()){int _front = que.front();que.pop();bQue[queLen++] = _front;}}
}
int binarySearch(int *arr, int len, int num)
{int l = -1, r = len;while (l + 1 < r){int mid = (l + r) / 2;if (arr[mid] < num){l = mid;}else{r = mid;}}return (l + 1);
}
void solve(int k)
{if (queLen == 0 && queLen_2 == 0){printf("%d\n", other[k - 1]);return;}int l = -1, r = n;while (l + 1 < r){int mid = (l + r) / 2;int cnt = 0;for (int i = 0; i < queLen; i++){cnt = cnt + binarySearch(bucket[bQue[i]], b, sortedDat[mid]);}for (int i = 0; i < queLen_2; i++){cnt = cnt + binarySearch(bucket_1[bQue_1[i]], 2 * b, sortedDat[mid]);}if (otherLen > 0){cnt = cnt + binarySearch(other, otherLen, sortedDat[mid]);}if (cnt < k){l = mid;}else{r = mid;}}printf("%d\n", sortedDat[l]);
}
int main()
{int m, i, j, k;while (~scanf("%d%d", &n, &m)){input();bucketMethod();while (m--){scanf("%d%d%d", &i, &j, &k);findBucket(i - 1, j);handleOther(i - 1, j);findBucketPlus();solve(k);}}return 0;
}

2、线段树

#include <iostream>
#include <algorithm>
using namespace std;
int *dat[262150];
int num[100009], len[262150], n_, n, inf = 0x3f3f3f3f, nodeQue[262150], queLen, sortedNum[100009];
void input()
{for (int i = 0; i < n_; i++){scanf("%d", &num[i]);}
}
void build()
{n = 1;while (n < n_){n = n * 2;}for (int i = (2 * n - 2); i >= 0; i--){if (i >= (n - 1)){dat[i] = new int[1];len[i] = 1;if ((i - n + 1) < n_){dat[i][0] = num[i - n + 1];}else{dat[i][0] = inf;}}else{int pLen = 0;int lChild = i * 2 + 1;int rChild = i * 2 + 2;pLen = 0;dat[i] = new int[len[lChild] + len[rChild]];int lId = 0;int rId = 0;while (lId < len[lChild] || rId < len[rChild]){if (rId >= len[rChild]){dat[i][pLen++] = dat[lChild][lId++];}else if (lId < len[lChild] && dat[lChild][lId] < dat[rChild][rId]){dat[i][pLen++] = dat[lChild][lId++];}else{dat[i][pLen++] = dat[rChild][rId++];}}len[i] = pLen;}}for (int i = 0; i < n_; i++){sortedNum[i] = dat[0][i];}
}
void query(int l_, int r_, int i, int l, int r)
{if (l_ >= r || r_ <= l){}else if (l >= l_ && r <= r_){nodeQue[queLen++] = i;}else{query(l_, r_, i * 2 + 1, l, (l + r) / 2);query(l_, r_, i * 2 + 2, (l + r) / 2, r);}
}
int binarySearch(int i, int number)
{int l = -1, r = len[i];while (l + 1 < r){int mid = (l + r) / 2;if (dat[i][mid] < number){l = mid;}else{r = mid;}}return (l + 1);
}
void solve(int k)
{if (queLen == 1){printf("%d\n", dat[nodeQue[0]][k - 1]);return;}int l = -1, r = n_;while (l + 1 < r){int mid = (l + r) / 2;int cnt = 0;for (int i = 0; i < queLen; i++){cnt += binarySearch(nodeQue[i], sortedNum[mid]);}if (cnt < k){l = mid;}else{r = mid;}}printf("%d\n", sortedNum[l]);
}
int main()
{int m, i, j, k;scanf("%d%d", &n_, &m);input();build();while (m--){scanf("%d%d%d", &i, &j, &k);queLen = 0;query(i - 1, j, 0, 0, n);solve(k);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/149959.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3 中使用echarts图表——柱状图

柱状图是比较常用的图形结构&#xff0c;所以我先收集一些精美的柱状图 一、柱状图&#xff1a;设置圆角和颜色 <template><div class"box" ref"chartDom"></div> </template> <script setup> import { ref, onMounted } fr…

力扣第100题 相同的数 c++ 二叉 简单易懂+注释

题目 100. 相同的树 简单 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3], q [1,2,3] 输出…

RabbitMQ之Direct(直连)Exchange解读

目录 基本介绍 使用场景 springboot代码演示 演示架构 工程概述 RabbitConfig配置类&#xff1a;创建队列及交换机并进行绑定 MessageService业务类&#xff1a;发送消息及接收消息 主启动类RabbitMq01Application&#xff1a;实现ApplicationRunner接口 基本介绍 在r…

功能测试复习

一。测试流程 1.需求评审 确保各部门需求理解一致 2.计划编写 测什么&#xff0c;谁来测&#xff0c;怎么测 3.用例设计 验证项目是否符合需求的操作文档 4.用例执行 项目模块开发完成开始执行用例文档实施测试 5.缺陷管理 对缺陷进行…

[晕事]今天做了件晕事21;设置代理访问网站的时候需注意的问题

今天在家上班&#xff0c;设置好VPN&#xff0c;通过代理来访问公司内部的一个系统浏览器的反应如下&#xff1a; Hmmm… can’t reach this page ***.com refused to connect. 这个返回的错误&#xff0c;非常的具有迷惑性&#xff0c;提示的意思&#xff1a;拒绝链接&#xf…

李沐深度学习记录2:10多层感知机

一.简要知识记录 x.numel()&#xff1a;看向量或矩阵里元素个数 A.sum()&#xff1a;向量或矩阵求和&#xff0c;axis参数可对某维度求和&#xff0c;keepdims参数设置是否保持维度不变 A.cumsum&#xff1a;axis参数设置沿某一维度计算矩阵累计和x*y:向量的按元素乘法 torch.…

时间序列常用数据处理

1.组合技巧Compose 1.2 实例应用及其解释 # 用于组合多个数据处理方法 class Compose(object):def __init__(self, transforms):self.transforms transformsdef __call__(self, seq):for t in self.transforms:seq t(seq)return seq 这段Python代码定义了一个名为Compose的…

【Spring Boot】日志文件

日志文件 一. 日志文件有什么用二. 日志怎么用三. ⾃定义⽇志打印1. 在程序中得到⽇志对象2. 使⽤⽇志对象打印⽇志3. ⽇志格式说明 四. 日志级别1. ⽇志级别有什么⽤2. ⽇志级别的分类与使⽤ 五. 日志持久化六. 更简单的⽇志输出—lombok1. 添加 lombok 依赖2. 输出⽇志3. lom…

Javascript - 轮播图

轮播图也称banner图、广告图、焦点图、滑片。是指在一个模块或者窗口,通过鼠标点击或手指滑动后,可以看到多张图片。这些图片统称为轮播图,这个模块叫做轮播模块。可以通过运用 javascript去实现定时自动转换图片。以下通过一个小Demo演示如何运用Javascript实现。 <!DOCTYP…

《计算机视觉中的多视图几何》笔记(12)

12 Structure Computation 本章讲述如何在已知基本矩阵 F F F和两幅图像中若干对对应点 x ↔ x ′ x \leftrightarrow x x↔x′的情况下计算三维空间点 X X X的位置。 文章目录 12 Structure Computation12.1 Problem statement12.2 Linear triangulation methods12.3 Geomet…

【Java】内部类

目录 概念&#xff1a; 内部类访问特点 示例代码&#xff1a; 运行结果&#xff1a; 内部类分类 1. 成员内部类 示例代码&#xff1a; 2. 静态内部类 示例代码&#xff1a; 3. 方法内部类(局部内部类) 示例代码&#xff1a; 4. 匿名内部类 示例代码&#xff1a; 概…

【开发篇】十七、消息:模拟订单短信通知

文章目录 1、消息2、JMS3、AMQP4、案例&#xff1a;模拟订单短信通知 相关文章&#xff1a; 【同步通讯与异步通讯】 1、消息 消息的发送方&#xff0c;即生产者。消息的接收方&#xff0c;即消费者。同步通信就行打视频&#xff0c;等着对方接电话才能继续往下&#xff0c;而…

文件编码格式

一、问题场景 笔者在写controller层出现了一些小问题&#xff1a;测试controller层的一些请求的时候&#xff0c;后端控制台打印的是乱码&#xff0c;网上找了很多说改UTF-8的&#xff0c;但是我去设置里面全部都改为UTF-8了&#xff0c;结果仍然无济于事&#xff0c;甚至还把…

泊车功能专题介绍 ———— AVP系统基础数据交互内容

文章目录 系统架构系统功能描述云端子系统车辆子系统场端子系统用户APP 工作流程基础数据交互内容AVP 系统基础数据交互服务车/用户 - 云基础数据交互内容车位查询工作流程技术要求数据交互要求 车位预约工作流程技术要求数据交互要求 取消预约工作流程技术要求数据交互要求 泊…

2023最新ICP备案查询系统源码 附教程 Thinkphp框架

2023最新ICP备案查询系统源码 附教程 thinkphp框架 本系统支持网址备案&#xff0c;小程序备案&#xff0c;APP备案查询&#xff0c;快应用备案查询 优势&#xff1a; 响应速度快&#xff0c;没有延迟&#xff0c;没有缓存&#xff0c;数据与官方同步 源码下载&#xff1a;ht…

关于MAC电脑无法正常登陆H3C iNodes登陆的解决办法

背景 前段时间&#xff0c;单位的网络在做升级改造&#xff0c;网络出口也进行彻底调整同时单位的网络出口设备做了机房物理迁移&#xff0c;迁移后网络正常使用&#xff0c;但是出现自己的MAC电脑无法登陆iNodes问题&#xff0c;总是出现“正在查询SSL 网关参数..查询SSL 网关…

sheng的学习笔记-【中文】【吴恩达课后测验】Course 2 - 改善深层神经网络 - 第二周测验

课程2_第2周_测验题 目录&#xff1a;目录 第一题 1.当输入从第8个mini-batch的第7个的例子的时候&#xff0c;你会用哪种符号表示第3层的激活&#xff1f; A. 【  】 a [ 3 ] { 8 } ( 7 ) a^{[3]\{8\}(7)} a[3]{8}(7) B. 【  】 a [ 8 ] { 7 } ( 3 ) a^{[8]\{7\}(3)} a…

无状态自动配置 DHCPv6无状态配置 DHCPv6有状态配置

1、无状态自动配置 配置命令 AR1 ipv6 #开启路由器ipv6报文转发功能 interface GigabitEthernet0/0/0 ipv6 enable #开启路由器接口IPv6报文转发功能 ipv6 address FC01::1/64 …

怎么将Linux上的文件上传到github上

文章目录 1. 先在window浏览器中创建一个存储项目的仓库2. 复制你的ssh下的地址1) 生成ssh密钥 : 在Linux虚拟机的终端中,运行以下命令生成ssh密钥2)将ssh密钥添加到github账号 : 运行以下命令来获取公钥内容: 3. 克隆GitHub存储库&#xff1a;在Linux虚拟机的终端中&#xff0…

Springboot实现登录功能(token、redis、登录拦截器、全局异常处理)

登录流程&#xff1a; 1、前端调用登录接口&#xff0c;往接口里传入账号&#xff0c;密码 2、根据账号判断是否有这个用户&#xff0c;如果有则继续判断密码是否正确 3、验证成功后&#xff0c;则是根据账号&#xff0c;登录时间生成token&#xff08;用JWT&#xff09; 4、将…