题意:给定一个数列,求一个区间的第K大数
模板题, 其中的newl, newr 有点不明白.
#include <iostream>
#include <algorithm>
using namespace std;
const int M = ;
int toLeft[][M], tree[][M], sorted[M]; void build(int level, int left, int right)
{
if (left == right) return;
int i, mid = (left + right) >>;
int suppose = mid - left + ;
for (i=left; i<=right; i++)
if (tree[level][i] < sorted[mid])
suppose--;
int lpos = left, rpos = mid+;
for (i=left; i<=right; i++)
{
if (i == left)
toLeft[level][i] = ;
else
toLeft[level][i] = toLeft[level][i-];
if (tree[level][i] < sorted[mid])
{
toLeft[level][i]++;
tree[level+][lpos++] = tree[level][i];
}
else if (tree[level][i] > sorted[mid])
{
tree[level+][rpos++] = tree[level][i];
}
else
{
if (suppose != )
{
suppose--;
toLeft[level][i]++;
tree[level+][lpos++] = tree[level][i];
}
else
tree[level+][rpos++] = tree[level][i];
}
}
build(level+, left, mid);
build(level+, mid+, right);
} int query(int level, int left, int right, int qleft, int qright, int k)
{
if (qleft == qright)
return tree[level][qright];
int s, ss, mid = (left + right)>>;
if (left == qleft)
{
s = ;
ss = toLeft[level][qright];
}
else
{
s = toLeft[level][qleft-];
ss = toLeft[level][qright] - s;
}
int newl, newr;
if (k <= ss)
{
newl = left + s;
newr = left + s + ss -;
return query(level+, left, mid, newl, newr, k);
}
else
{
newl = mid-left++qleft-s;
newr = mid-left++qright-s-ss;
return query(level+, mid+, right, newl, newr, k-ss);
}
} int main()
{
int n, m;
int i;
while (scanf("%d%d", &n, &m) == )
{
for (i=; i<=n; i++)
{
scanf("%d", &tree[][i]);
sorted[i] = tree[][i];
}
sort(sorted+, sorted+n+);
build(,,n);
int ql, qr, k;
for (i=; i<m; i++)
{
scanf("%d%d%d", &ql, &qr, &k);
printf("%d\n", query(, , n, ql, qr, k));
}
}
return ;
}