当前位置: 首页 > news >正文

[POJ2104]K-th Number

题目大意:给你一个数列和一些询问,每次询问你一个$[l,r]$区间里第k小数。

解题思路:可持久化线段树,所谓的“主席树”。对每一个$[1,l]$区间开一个线段树,运用主席树的可持久化,没有变化的子树直接用老版本的就行了。

然而你会发现,我代码里有个map,实际上是我用map记录离散值时TLE了。于是我把map换成了lower_bound()。所以STL的容器虽然方便,但速度并不快,能不用尽量不用。

C++ Code:

 

#include<cstdio>
#include<map>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
int n,m,root[N],d[N*20],node=0,mx;
int a[N],b[N];
int ld[N*20],rd[N*20];
map<int,int>mp;
void ins(int& cur,int t,int l,int r,int k){
	cur=++node;
	d[cur]=d[t];
	d[cur]++;
	ld[cur]=ld[t],rd[cur]=rd[t];
	if(l==r)return;
	int m=l+r>>1;
	if(k<=m)ins(ld[cur],ld[t],l,m,k);else
	ins(rd[cur],rd[t],m+1,r,k);
}
int query(int L,int R,int l,int r,int k){
	if (k==0) return 0;
	if(l==r)return l;
	int ls=d[ld[R]]-d[ld[L]],m=l+r>>1;
	if(d[R]-d[L]<k)return 0;
	if(k<=ls)
	return query(ld[L],ld[R],l,m,k);
	return query(rd[L],rd[R],m+1,r,k-ls);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	mx=n;
	memcpy(b,a,sizeof b);
	sort(b+1,b+n+1);
	mx=unique(b+1,b+n+1)-b-1;
	memset(root,0,sizeof root);
	for(int i=1;i<=n;++i)ins(root[i],root[i-1],1,n,lower_bound(b+1,b+mx+1,a[i])-b);
	while(m--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",b[query(root[l-1],root[r],1,n,k)]);
	}
	return 0;
}

 

转载于:https://www.cnblogs.com/Mrsrz/p/7183202.html

相关文章:

  • window10 java 环境变量配置
  • Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) C. String Reconstruction 并查集
  • STC15F2K60S2与USART HMI串口屏之间的通信
  • 关于JAVA中包装类的是什么类型传递这个问题的笔记
  • 【洛谷1607】【USACO09FEB】庙会班车
  • 搭建wordpress-安装xshell
  • python基础2
  • POJ 1830 开关问题(高斯消元求解的情况)
  • Python3的一些基本输入输出
  • 公有属性 公有方法(原型方法) 私有属性 私有方法 特权方法 静态属性 静态方法 对象字面量创建...
  • angularJS指令
  • 头文件assert.h
  • 后台运行命令:amp;和nohup command amp; 以及关闭、查看后台任务
  • 进程间通信之-信号signal--linux内核剖析(九)
  • 入门之快速排序
  • @jsonView过滤属性
  • C++11: atomic 头文件
  • CentOS 7 修改主机名
  • Codepen 每日精选(2018-3-25)
  • iOS动画编程-View动画[ 1 ] 基础View动画
  • JS创建对象模式及其对象原型链探究(一):Object模式
  • Mysql5.6主从复制
  • php中curl和soap方式请求服务超时问题
  • 初识 webpack
  • 从重复到重用
  • 大型网站性能监测、分析与优化常见问题QA
  • 干货 | 以太坊Mist负责人教你建立无服务器应用
  • 实现菜单下拉伸展折叠效果demo
  • 用mpvue开发微信小程序
  • kubernetes资源对象--ingress
  • 东超科技获得千万级Pre-A轮融资,投资方为中科创星 ...
  • 专访Pony.ai 楼天城:自动驾驶已经走过了“从0到1”,“规模”是行业的分水岭| 自动驾驶这十年 ...
  • ​LeetCode解法汇总2182. 构造限制重复的字符串
  • #NOIP 2014# day.1 T3 飞扬的小鸟 bird
  • #pragma once
  • (免费领源码)python#django#mysql公交线路查询系统85021- 计算机毕业设计项目选题推荐
  • (四)docker:为mysql和java jar运行环境创建同一网络,容器互联
  • (四)模仿学习-完成后台管理页面查询
  • (一)Java算法:二分查找
  • (原創) 物件導向與老子思想 (OO)
  • (转)linux下的时间函数使用
  • (转)memcache、redis缓存
  • (转)Scala的“=”符号简介
  • .net core 控制台应用程序读取配置文件app.config
  • .net 流——流的类型体系简单介绍
  • .net 使用ajax控件后如何调用前端脚本
  • .NET6 开发一个检查某些状态持续多长时间的类
  • @Data注解的作用
  • [2016.7 test.5] T1
  • [AI]文心一言爆火的同时,ChatGPT带来了这么多的开源项目你了解吗
  • [C/C++]数据结构 堆的详解
  • [leetcode]114. Flatten Binary Tree to Linked List由二叉树构建链表
  • [office] 怎么在Excel2003菜单栏自定义一个选项卡 #其他#微信#知识分享
  • [Redis源码阅读]当你输入get/set命令的时候,Redis做了什么
  • [Swift] Enum 好用, Enum 可以更易用