[POJ2104]K-th Number

时间:2022-11-10 18:55:45
  1. K-th Number
Time Limit: 20000MS   Memory Limit: 65536K
Total Submissions: 34048   Accepted: 10810
Case Time Limit: 2000MS

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. 
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 first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). 
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

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

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

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

Source

Northeastern Europe 2004, Northern Subregion
一句话题意:题目意思很简单,多次询问区间k小值
分析:没什么好分析的,模板题,原本想用划分树做,然后去贴吧问……结果被喷“时代的默泪”,ORZ……然后默默的去看主席树了
(主席树资料网上很多,大家百度一下)
这里说下主要思想,就是对1~n每个位置建立一颗线段树,表示从开头到此位置每个数字在各个区间出现次数(当然要先离散……),当然这样空间不行,但是可以发现所有线段树形状一样只是sum域不同,且第i颗和第i-1颗相比,只是在第i-1颗的基础上插入了第i个点(即只修改了第i-1颗线段树的一条从上到下的路径,其他都没改变),因此只要建立一个主线段树,没变的指一条边过去就可以了。
然后询问[a,b]可以发现线段树可以减,即[a,b]的线段树相当于[1,b]线段树(对应第b颗线段树)-[1,a-1]线段树(对应第a-1颗),然后判断下左子树大小和k的关系就行了
code:
 #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的更多相关文章

  1. &lbrack;POJ2104&rsqb; K – th Number &lpar;可持久化线段树 主席树&rpar;

    题目背景 这是个非常经典的主席树入门题--静态区间第K小 数据已经过加强,请使用主席树.同时请注意常数优化 题目描述 如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值. 输入输 ...

  2. 【POJ2104】K-th Number

    aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABToAAAJ2CAIAAADwi6oDAAAgAElEQVR4nOy9a5Pj1nnvi0/Q71Llj3

  3. C&plus;&plus;之路进阶——poj2104(K-th Number)

    K-th Number Time Limit: 20000MS   Memory Limit: 65536K Total Submissions: 44537   Accepted: 14781 Ca ...

  4. 【poj2104】K-th Number 主席树

    题目描述 You are working for Macrohard company in data structures department. After failing your previou ...

  5. 【POJ2104】K-th Number(主席树)

    题意:有n个数组成的序列,要求维护数据结构支持在线的下列两种操作: 1:单点修改,将第x个数修改成y 2:区间查询,询问从第x个数到第y个之间第K大的数 n<=100000,a[i]<=1 ...

  6. poj2104:K-th Number

    思路:可持久化线段树,利用权值线段树,把建树过程看成插入,插入第i个元素就在第i-1棵树的基础上新建结点然后得到第i棵树,那么询问区间[l,r]就是第r棵树上的信息对应减去第l-1棵树上的信息,然后再 ...

  7. POJ2104:K-th Number——题解

    http://poj.org/problem?id=2104 题目大意:求区间第k小. —————————————————————————— 主席树板子题. ……我看了半天现在还是一知半解的状态所以应 ...

  8. poj2104 K大数 划分树

    题意:给定一个数列,求一个区间的第K大数 模板题, 其中的newl, newr 有点不明白. #include <iostream> #include <algorithm> ...

  9. ACM-ICPC 2018 沈阳赛区网络预赛 K&period; Supreme Number

    A prime number (or a prime) is a natural number greater than 11 that cannot be formed by multiplying ...

  10. 整体二分初识--POJ2104:K-th Number

    n<=100000个数有m<=5000个询问,每次问区间第k大. 方法一:主席树!…… 方法二:整体二分. 整体二分一次性计算半个值域对一个区间的询问的贡献,然后根据“这半边的贡献在某个询 ...

随机推荐

  1. activeMq 消费者整合spring

    package com.mq.consumer; import javax.jms.JMSException;import javax.jms.Message;import javax.jms.Mes ...

  2. 优秀前端开发教程:超炫的 Mobile App 3D 演示

    今天,我们想与您分享一个实验性的3D效果.它涉及到一个3D移动设备和一些移动应用程序截图.点击切换按钮时,我们将让移动设备转动并移动每个画面,使我们能看到一个分层的视图.你可能之前没见过这种应用程序演 ...

  3. Problems encountered while deleting resources&period;

    Error The project was not built due to “Problems encountered while deleting resources.”. Fix the pro ...

  4. NDK安装 eclipse 不出现NDK目录问题

    android adt自带eclipse无法设置ndk路径 具体情况是 我在mac上搭建android环境 到android sdk官网下载r23版本的adt时自带的eclipse没有设置ndk路径的 ...

  5. CoreData Multiple Context性能分析-读书笔记

    From: http://floriankugler.com/blog/2013/4/29/concurrent-core-data-stack-performance-shootout  http: ...

  6. 图解:SQL Server SSIS包和job的部署攻略

    原文:图解:SQL Server SSIS包和job的部署攻略 以下将建立一个SQL Server SSIS包 然后在job中使用这个包,并将job部署到目标机器 1. 首先建立ssis包,使用sql ...

  7. pip&colon; unsupported locale setting

    在终端里输入 $ export LC_ALL=C 可解决 http://*.com/questions/36394101/pip-install-locale-error-un ...

  8. 云计算概述和KVM虚拟化

    前言: 近些年一直听着 虚拟化.云计算.公有云.私有云.混合云这些个概念,一直想着....这些概念要用什么技术实现? 一.云计算的概念 1.传统IDC机房面都会临什么问题? 任何新事物都是由需求催生的 ...

  9. 【设计模式】jdbc桥连接过程解析

    读多少源码,便知自己有多无知! 想温习一下桥链接模式,然后觉得自己已然吃透了,因为自己写的博客,觉得还是应该更具体一些. 类似于这样的结构: 个人理解:    模式类型:概述:角色:模式的应用场景:结 ...

  10. &lt&semi;转&gt&semi; 解决异常:IllegalStateException&colon; Fragment &lt&semi;ThisFragment&gt&semi; is not currently in the FragmentManager

    上午敲代码时出现这个问题,简单记录一下解决办法,有时间详细描述一下深层原因. 问题出现在这: @Override public void onSaveInstanceState(Bundle outS ...