poj 2104 K-th Number(主席树
2024-10-14 06:16:39
Time Limit: 20000MS | Memory Limit: 65536K | |
Total Submissions: 59058 | Accepted: 20529 | |
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.
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).
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
主席树板子题
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = ;
int ls[N*],rs[N*],sum[N*];
int n,m,a[N],hash[N],cnt,root[N];
int x,y,k;
void lsh()
{
sort(hash+,hash+n+);
cnt=unique(hash+,hash+n+)-(hash+);
for(int i=;i<=n;i++)a[i]=lower_bound(hash+,hash+cnt+,a[i])-hash;
}
int tot=;
void build(int l,int r,int &rt,int pre,int w)
{
rt=++tot;
sum[rt]=sum[pre]+;
if(l==r)return;
int mid=(l+r)>>;
if(w<=mid)rs[rt]=rs[pre],build(l,mid,ls[rt],ls[pre],w);
else ls[rt]=ls[pre],build(mid+,r,rs[rt],rs[pre],w);
}
int query(int l,int r,int x,int y,int k)
{
if(l==r)return l;
int mid=l+r>>,tmp=sum[ls[y]]-sum[ls[x]];
if(tmp>=k)return query(l,mid,ls[x],ls[y],k);
else return query(mid+,r,rs[x],rs[y],k-tmp);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",a+i),hash[i]=a[i];
lsh();
// printf("%d\n",cnt);for(int i=1;i<=cnt;i++) printf("%d ",hash[i]);
for(int i=;i<=n;i++) build(,cnt,root[i],root[i-],a[i]);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",hash[query(,cnt,root[x-],root[y],k)]);
}
return ;
}
最新文章
- [2016湖南长沙培训Day4][前鬼后鬼的守护 chen] (动态开点线段树+中位数 or 动规 or 贪心+堆优化)
- Jquery网页加载进度条(随笔,当然要随便写,当日记动态心情写咯)
- 【BZOJ】3434: [Wc2014]时空穿梭
- 常用dom对象
- Intellij IDEA 14的注册机
- 自定义progressBar的旋转圆圈
- tif图片编辑利器
- Test Tools
- IDL中File_Search函数用法详解(转)
- 【toplink】 位居第一的Java对象关系可持续性体系结构
- mysql服务启动 但端口未监听
- 数据市中心全省中国mysql脚本
- Knockout js 绑定 radio 时,当绑定整形的时候,绑定不生效
- Unity编程标准导引-Unity中的基本概念-2.1界面概览
- java集合系列——List集合之Vector介绍(四)
- SecureCRT8.0设置语法高亮
- spark ML pipeline 学习
- 常用模块collections
- JustOj 2009: P1016 (dp)
- 希尔排序之python