Time Limit: 20000MS | Memory Limit: 65536K | |
Total Submissions: 44537 | Accepted: 14781 | |
Case Time Limit: 2000MS |
Description
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
Input
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output
Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3
Hint
Source
题目大意:给你一段序列,求给定区间[u,v]中第k小的值
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 1000100 using namespace std; int n,m,sz;
int hash[maxn],a[maxn],root[maxn],ls[maxn*],rs[maxn*],sum[maxn*]; void updata(int l,int r,int x,int &y,int v)
{
y=++sz;
sum[y]=sum[x]+;
if (l==r) return;
ls[y]=ls[x];
rs[y]=rs[x];
int mid=(l+r)>>;
if (v<=mid) updata(l,mid,ls[x],ls[y],v);
else updata(mid+,r,rs[x],rs[y],v);
} int que(int L,int R,int K)
{
int l=,r=n,mid,x,y;
x=root[L-];
y=root[R];
while (l!=r)
{
mid=(l+r)>>;
if (K<=sum[ls[y]]-sum[ls[x]])
{
x=ls[x];
y=ls[y];
r=mid;
}
else
{
K-=(sum[ls[y]]-sum[ls[x]]);
x=rs[x];
y=rs[y];
l=mid+;
}
}
return l;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&a[i]),hash[i]=a[i];
sort(hash+,hash+n+);
for (int i=;i<=n;i++)
{
int w=lower_bound(hash+,hash+n+,a[i])-hash;
updata(,n,root[i-],root[i],w);
}
for (int i=;i<=m;i++)
{
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
printf("%d\n",hash[que(l,r,v)]);
}
return ;
}
C++之路进阶——poj2104(K-th Number)的更多相关文章
-
[POJ2104] K – th Number (可持久化线段树 主席树)
题目背景 这是个非常经典的主席树入门题--静态区间第K小 数据已经过加强,请使用主席树.同时请注意常数优化 题目描述 如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值. 输入输 ...
-
【POJ2104】K-th Number
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABToAAAJ2CAIAAADwi6oDAAAgAElEQVR4nOy9a5Pj1nnvi0/Q71Llj3
-
C++之路进阶——poj3461(Oulipo)
Oulipo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 35694 Accepted: 14424 Descript ...
-
C++之路进阶codevs1269(匈牙利游戏)
1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...
-
c++之路进阶——hdu3507(Print Article)
参考博文:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html//讲的真的很好,有个小错误,博客里的num全为sum,像我这种 ...
-
C++之路进阶——hdu2222(Keywords Search)
/*Keywords Search Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) ...
-
【poj2104】K-th Number 主席树
题目描述 You are working for Macrohard company in data structures department. After failing your previou ...
-
【POJ2104】K-th Number(主席树)
题意:有n个数组成的序列,要求维护数据结构支持在线的下列两种操作: 1:单点修改,将第x个数修改成y 2:区间查询,询问从第x个数到第y个之间第K大的数 n<=100000,a[i]<=1 ...
-
C++之路进阶——HDU1880(魔咒词典)
---恢复内容开始--- New~ 欢迎参加2016多校联合训练的同学们~ 魔咒词典 Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 3 ...
随机推荐
-
js/javascript format json(js/javascript 格式化json字符串)
// format json obj string function format_json(txt, compress) { var indentChar = ' '; if (/^\s*$/ ...
-
POI打印Excel报表
1.将POI组件中的jar包放入项目中路径下的WEB-INF/lib目录中 2.在javabean中创建一个poi的java文件,中间出了创建getXXX(),setXXX()方法外,加入readRe ...
-
Kafka报错-as it has seen zxid 0x83808 our last zxid is 0x0 client must try another server
as it has seen zxid 0x83808 our last zxid is 0x0 client must try another server 停止zookeeper,删除datadi ...
-
JavaWeb Chapter 7 监听器
1. 监听器Session.request.context对象属性的变化: 2. 三个对象都有生命周期和属性改变的监听: 3. Session另外还有会话迁移和对象绑定的监听: 4. Sess ...
-
学习练习 java数据库查询小题
10. 查询Score表中的最高分的学生学号和课程号.(子查询或者排序) 11. 查询每门课的平均成绩. 12.查询Score表中至少有5名学生选修的并以3开头的课程的平均分数. 13.查询分数大于7 ...
-
Linux power supply class hacking
/*************************************************************************** * Linux power supply cl ...
-
php二分查找
// 递归版本 function bin_sch($arr,$low,$high,$val) { if($low<$high){ $mid = intval(($low+$high)/2); i ...
-
《Machine Learning》系列学习笔记之第一周
<Machine Learning>系列学习笔记 第一周 第一部分 Introduction The definition of machine learning (1)older, in ...
-
从EventLoop到宏任务与微任务
1.javascript是单线程的 javascript是单线程的,意思是javascript在同一时间内只能做一件事情. 为什么是单线程的? 因为js的主要用途是用于用户交互和操作DOM,如果是多线 ...
-
img图像标签和超链接标签a
图像标签语法:<img src="" alt="".../> img属性:src="" 显示图像的URLalt="& ...