题目地址:http://poj.org/problem?id=2104
题目:
输出区间第k小的数,多次查询,时间2s
解题思路:
注意数组的大小,一般开nlog2(n)n不要RE,开25-40倍
样例前三个数所建的主席树如下:(手动模拟一遍!!)
建立过程中依次有T[5]=T[1], T[9]=T[5], T[10]=T[2], T[11]=T[3]
图中的红色框内的是前三个数的主席树,最左侧的一竖列是第一个数建的主席树,最右侧的一竖列是第二个数建的主席树。。。emmm有点讲不清楚,模拟一下就懂了。
ac代码:
注意数组的大小,一般开nlog2(n)n不要RE,开25-40倍
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int root[maxn], a[maxn], b[maxn];
int m, n, cnt, l, r, k;
struct node{
int l, r, sum;
}T[30*maxn]; //至少开25倍
void update(int l, int r, int &x, int y, int pos)
{
T[++cnt] = T[y];
T[cnt].sum++;
x = cnt;
if(l == r) return ;
int mid =(l + r) >> 1;
if(pos <= mid) update(l, mid, T[x].l, T[y].l, pos);
else update(mid+1, r, T[x].r, T[y].r, pos);
}
int query(int l, int r, int x, int y, int k) // 找区间第k小
{
if(l == r) return l;
int mid = (l + r) >> 1;
int Real = T[T[y].l].sum - T[T[x].l].sum;//普通权值线段树上左节点的值
if(k <= Real) return query(l, mid, T[x].l, T[y].l, k);
else return query(mid+1, r, T[x].r, T[y].r, k - Real);
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(a+1, a+1+n);
int num = unique(a+1, a+1+n) - (a+1);
for(int i = 1; i <= n; i++)
{
int no = lower_bound(a+1, a+1+num, b[i]) - a;
update(1, n, root[i], root[i - 1], no);
}
for(int i = 1; i <= m; i++)
{
scanf("%d %d %d", &l, &r, &k);
int id = query(1, n, root[l-1], root[r], k);
printf("%d\n", a[id]);
}
return 0;
}