poj 2104 主席树(区间第k大)
2024-10-12 08:42:07
K-th Number
Time Limit: 20000MS | Memory Limit: 65536K | |
Total Submissions: 44940 | Accepted: 14946 | |
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
因为保存的是前i个数的情况,求[a,b]区间时,只需要T[b]-T[a-1]
/*
poj2104
主席树-求解区间第k大
hhh-2016-02-18 13:09:24
*/ #include <functional>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld; using namespace std;
const int maxn = 100010;
int tot;
int n,m;
int a[maxn],t[maxn];
int T[maxn],lson[maxn*30],rson[maxn*30],c[maxn*30]; int build(int l,int r)
{
int root = tot++;
if(l != r)
{
int mid = (l+r)>>1;
lson[root] = build(l,mid);
rson[root] = build(mid+1,r);
}
return root;
} void ini_hash() //排序去重
{
for(int i = 1;i <= n;i++)
t[i] = a[i];
sort(t+1,t+n+1);
m = unique(t+1,t+n+1)-(t+1);
} int Hash(int x) //得到位置
{
return lower_bound(t+1,t+m+1,x)-t;
} //如果那里发生改变则新建一个节点而非像平常修改那个节点的值
int update(int root,int pos,int val)
{
int newroot = tot++;
int tmp = newroot;
c[newroot] = c[root] + val;
int l = 1,r = m;
while(l < r)
{
int mid = (l+r)>>1;
if(pos <= mid)
{
lson[newroot] = tot++;rson[newroot] = rson[root];
newroot = lson[newroot]; root = lson[root];
r = mid;
}
else
{
lson[newroot] = lson[root]; rson[newroot] = tot++;
newroot = rson[newroot]; root = rson[root];
l = mid+1;
}
c[newroot] = c[root] + val;
}
return tmp;
} int query(int lt,int rt,int k)
{
int l = 1, r = m;
while(l < r)
{
int mid = (l+r)>>1;
if(c[lson[rt]] - c[lson[lt]] >= k)
{
r = mid;
lt = lson[lt];
rt = lson[rt];
}
else
{
l = mid+1;
k -= (c[lson[rt]] - c[lson[lt]]);
lt = rson[lt];
rt = rson[rt];
}
}
return l;
} int main()
{
int q;
while(scanf("%d%d",&n,&q) !=EOF)
{
tot = 0;
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
ini_hash();
T[0] = build(1,m);
for(int i = 1;i <= n;i++)
{
int pos = Hash(a[i]);
T[i] = update(T[i-1],pos,1);
}
while(q--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",t[query(T[l-1],T[r],k)]);
}
}
return 0;
}
最新文章
- 【转】MySQL性能优化的最佳21条经验
- centos 7 挂载大硬盘
- Linux系统中配置jdk
- oracle win7下 卸载
- asp.net identity 2.2.0 中角色启用和基本使用(四)
- BZOJ4155 : [Ipsc2015]Humble Captains
- 转 关于ruby gem无法连接到rubygems.org的解决方案
- 破解ckfinder2.3 去除版本号和标题提示
- 第四章_PHP基本语法
- [Angular2 Form] Use RxJS Streams with Angular 2 Forms
- POJ3034+DP
- Cron运行原理
- TEA加密算法的C/C++实现
- 【译】Asp.Net Identity Cookies 格式化-中英对照版
- 启动eclipse时候提示错误Error:Could not create the Java Virtual Machine. Error:A Fatal exception has occurred,Program will exit.
- Linux系统下rm删除文件后空间没有释放问题解决办法
- 五十五、linux 编程——TCP 连接和关闭过程及服务器的并发处理
- [转] JavaScript中in操作符(for..in)、Object.keys()和Object.getOwnPropertyNames()的区别
- Django中间件2
- 【CSS】环形进度条