传送门:洛谷 - P3834
题目描述
求静态区间第K小
输入描述
第一行包含两个正整数 $n$,$m$,分别表示序列的长度和查询的个数
第二行包含 $n$ 个整数,表示这个序列各项的数字
接下来 $m$ 行每行包含三个整数 $l$, $r$, $k$ 表示查询区间 $[l, r]$ 内的第 $k$ 小值。
输出描述
输出包含 $m$ 行,每行一个整数,依次表示每一次查询的结果
思路分析
对于每一个前缀建立一颗权值线段树,类似于前缀和,计算的时候$R-(l-1)$就是答案了,用主席树来减少空间
样例输入
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
样例输出
6405
15770
26287
25957
26287
AC代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define fun function
#define ll long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
struct node {
int l, r, sum;
} tree[N * 40];
int cnt, root[N], a[N];
vector<int> v;
void ins(int l, int r, int pre, int &now, int pos) {
tree[++cnt] = tree[pre]; //复制前驱
now = cnt;
tree[now].sum++;
if (l == r)
return;
int mid = l + r >> 1;
if (pos <= mid)
ins(l, mid, tree[pre].l, tree[now].l, pos);
else
ins(mid + 1, r, tree[pre].r, tree[now].r, pos);
}
int query(int l, int r, int L, int R, int k) {
if (l == r)
return l;
int mid = l + r >> 1;
int temp = tree[tree[R].l].sum - tree[tree[L].l].sum;
if (k <= temp)
return query(l, mid, tree[L].l , tree[R].l, k);
else
return query(mid + 1, r, tree[L].r, tree[R].r, k - temp); //减去左子树的大小
}
int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main() {
IOS;
#ifdef xiaofan
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
v.push_back(a[i]);
}
sort(all(v));
v.erase(unique(all(v)), v.end());
int tot = v.size();
for (int i = 1; i <= n; i++)
ins(1, tot, root[i - 1], root[i], getid(a[i]));
while (m--) {
int l, r, k;
cin >> l >> r >> k;
cout << v[query(1, tot, root[l - 1], root[r], k) - 1] << endl;
}
return 0;
}