Rockdu's Blog

题目背景

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

题目描述

如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数$l,r,k$ , 表示查询区间$[l,r]$内的第k小值。

输出格式：

输出包含k行，每行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

说明

数据范围：

对于20%的数据满足：$1\le N,M\le 10$

对于50%的数据满足：1 \leq N, M \leq 10^31≤N,M≤10​3​​

对于80%的数据满足：1 \leq N, M \leq 10^51≤N,M≤10​5​​

对于100%的数据满足：1 \leq N, M \leq 2\cdot 10^51≤N,M≤2⋅10​5​​

对于数列中的所有数a_ia​i​​，均满足-{10}^9 \leq a_i \leq {10}^9−10​9​​≤a​i​​≤10​9​​

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为$[25957,6405,15770,26287,26465]$

第一次查询为$[2,2]$区间内的第一小值，即为6405

第二次查询为$[3,4]$区间内的第一小值，即为15770

第三次查询为$[4,5]$区间内的第一小值，即为26287

第四次查询为$[1,2]$区间内的第二小值，即为25957

第五次查询为$[4,4]$区间内的第一小值，即为26287

今天复习了一发线段树，看见洛谷居然更新了，顺便就复习了一发主席树

大致思路已经很经典了，首先离散化，建立一棵空权值线段树，对每一个位置更新权值线段树的一条链。下面代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
inline int read() {
	int ret = 0;char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c <= '9' && c >= '0') ret = ret * 10 + c - '0', c = getchar();
	return ret;
}
struct DATA{
	int id, num;
	bool operator < (const DATA &a) const {return num < a.num;}
}data[maxn];
int num[maxn], n, m;
namespace Prestree{
	struct node{
		int l, r, ch[2], sum;
	}tree[maxn * 25];
	int root[maxn], cnt;
	void push_up(int rt) {
		tree[rt].sum = tree[tree[rt].ch[0]].sum + tree[tree[rt].ch[1]].sum;
	}
	void build(int & rt, int l, int r, int x) {
		tree[++cnt] = tree[rt], rt = cnt;
		tree[rt].l = l, tree[rt].r = r;
		if(l == r) {tree[rt].sum += 1;return;}
		int mid = (l + r) >> 1;
		if(x <= mid) build(tree[rt].ch[0], l, mid, x);
		else build(tree[rt].ch[1], mid + 1, r, x);
		push_up(rt);
	}
	void init(int n) {
		root[0] = ++cnt;
		for(register int i = 1; i <= n; ++i) 
			root[i] = root[i - 1], build(root[i], 1, n, num[i]);
	}
	int query(int l, int r, int k) {
		int tl = tree[r].l, tr = tree[r].r;
		if(tl == tr)return tl;
		int mid = (tl + tr) >> 1;
		int sum = tree[tree[r].ch[0]].sum - (l ? tree[tree[l].ch[0]].sum : 0);
		if(sum < k) return query(tree[l].ch[1], tree[r].ch[1], k - sum);
		else return query(tree[l].ch[0], tree[r].ch[0], k);
	}
}

int main() {
	n = read(), m = read();
	for(register int i = 1; i <= n; ++i) data[i].num = read(), data[i].id = i;
	sort(data + 1, data + n + 1);
	for(register int i = 1; i <= n; ++i) num[data[i].id] = i;
	Prestree::init(n);
	int a, b, c;
	while(m--) {
		a = read(), b = read(), c = read();
		printf("%d\n", data[Prestree::query(Prestree::root[a - 1], Prestree::root[b], c)].num);
	}
	return 0;
}