- K-th Number
Time Limit: 20000MS | Memory Limit: 65536K | |
Total Submissions: 34048 | Accepted: 10810 | |
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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
struct wjmzbmr
{
int l,r,ls,rs,sum;
}f[maxn*];
int tot,root[maxn+],q,b[maxn+],sortb[maxn+];
int build(int l,int r)
{
int k=++tot;
f[k]={l,r,,,};
if(l==r) return tot;
int mid=(l+r)>>;
f[k].ls=build(l,mid);
f[k].rs=build(mid+,r);
return k;
}
int change(int o,int x,int v)
{
int k=++tot;
f[k]=f[o];f[k].sum+=v;
if(f[o].l==x&&f[o].r==x) return k;
int mid=(f[o].l+f[o].r)>>;
if(x<=mid) f[k].ls=change(f[o].ls,x,v);else f[k].rs=change(f[o].rs,x,v);
return k;
}
int ask(int a,int b,int k)
{
if(f[b].l==f[b].r) return f[b].l;
int mid=f[f[b].ls].sum-f[f[a].ls].sum;
if(k<=mid) return ask(f[a].ls,f[b].ls,k);else return ask(f[a].rs,f[b].rs,k-mid);
}
int main()
{
freopen("ce.in","r",stdin);
freopen("ce.out","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=n;++i) scanf("%d",&b[i]),sortb[i]=b[i];
sort(sortb+,sortb++n);
q=;tot=;
for(int i=;i<=n;++i) if(sortb[q]!=sortb[i]) sortb[++q]=sortb[i];
root[]=build(,q);
for(int i=;i<=n;++i)
{
int p=lower_bound(sortb+,sortb+n+,b[i])-sortb;
root[i]=change(root[i-],p,);
}
for(int i=;i<=m;++i)
{
int a,b,k;
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",sortb[ask(root[a-],root[b],k)]);
}
}
return ;
}
[POJ2104]K-th Number的更多相关文章
-
[POJ2104] K – th Number (可持久化线段树 主席树)
题目背景 这是个非常经典的主席树入门题--静态区间第K小 数据已经过加强,请使用主席树.同时请注意常数优化 题目描述 如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值. 输入输 ...
-
【POJ2104】K-th Number
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABToAAAJ2CAIAAADwi6oDAAAgAElEQVR4nOy9a5Pj1nnvi0/Q71Llj3
-
C++之路进阶——poj2104(K-th Number)
K-th Number Time Limit: 20000MS Memory Limit: 65536K Total Submissions: 44537 Accepted: 14781 Ca ...
-
【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 ...
-
poj2104:K-th Number
思路:可持久化线段树,利用权值线段树,把建树过程看成插入,插入第i个元素就在第i-1棵树的基础上新建结点然后得到第i棵树,那么询问区间[l,r]就是第r棵树上的信息对应减去第l-1棵树上的信息,然后再 ...
-
POJ2104:K-th Number——题解
http://poj.org/problem?id=2104 题目大意:求区间第k小. —————————————————————————— 主席树板子题. ……我看了半天现在还是一知半解的状态所以应 ...
-
poj2104 K大数 划分树
题意:给定一个数列,求一个区间的第K大数 模板题, 其中的newl, newr 有点不明白. #include <iostream> #include <algorithm> ...
-
ACM-ICPC 2018 沈阳赛区网络预赛 K. Supreme Number
A prime number (or a prime) is a natural number greater than 11 that cannot be formed by multiplying ...
-
整体二分初识--POJ2104:K-th Number
n<=100000个数有m<=5000个询问,每次问区间第k大. 方法一:主席树!…… 方法二:整体二分. 整体二分一次性计算半个值域对一个区间的询问的贡献,然后根据“这半边的贡献在某个询 ...
随机推荐
-
activeMq 消费者整合spring
package com.mq.consumer; import javax.jms.JMSException;import javax.jms.Message;import javax.jms.Mes ...
-
优秀前端开发教程:超炫的 Mobile App 3D 演示
今天,我们想与您分享一个实验性的3D效果.它涉及到一个3D移动设备和一些移动应用程序截图.点击切换按钮时,我们将让移动设备转动并移动每个画面,使我们能看到一个分层的视图.你可能之前没见过这种应用程序演 ...
-
Problems encountered while deleting resources.
Error The project was not built due to “Problems encountered while deleting resources.”. Fix the pro ...
-
NDK安装 eclipse 不出现NDK目录问题
android adt自带eclipse无法设置ndk路径 具体情况是 我在mac上搭建android环境 到android sdk官网下载r23版本的adt时自带的eclipse没有设置ndk路径的 ...
-
CoreData Multiple Context性能分析-读书笔记
From: http://floriankugler.com/blog/2013/4/29/concurrent-core-data-stack-performance-shootout http: ...
-
图解:SQL Server SSIS包和job的部署攻略
原文:图解:SQL Server SSIS包和job的部署攻略 以下将建立一个SQL Server SSIS包 然后在job中使用这个包,并将job部署到目标机器 1. 首先建立ssis包,使用sql ...
-
pip: unsupported locale setting
在终端里输入 $ export LC_ALL=C 可解决 http://*.com/questions/36394101/pip-install-locale-error-un ...
-
云计算概述和KVM虚拟化
前言: 近些年一直听着 虚拟化.云计算.公有云.私有云.混合云这些个概念,一直想着....这些概念要用什么技术实现? 一.云计算的概念 1.传统IDC机房面都会临什么问题? 任何新事物都是由需求催生的 ...
-
【设计模式】jdbc桥连接过程解析
读多少源码,便知自己有多无知! 想温习一下桥链接模式,然后觉得自己已然吃透了,因为自己写的博客,觉得还是应该更具体一些. 类似于这样的结构: 个人理解: 模式类型:概述:角色:模式的应用场景:结 ...
-
<;转>; 解决异常:IllegalStateException: Fragment <;ThisFragment>; is not currently in the FragmentManager
上午敲代码时出现这个问题,简单记录一下解决办法,有时间详细描述一下深层原因. 问题出现在这: @Override public void onSaveInstanceState(Bundle outS ...