<commit_before>---
layout: post
title: 区间k小数（1）
tags: [OI,数据结构]
category: 笔记
---

在线段树的学习当中，我们会了解到线段树的应用之一就是求<ruby>**区间极值**<rt><rp>(</rp>Range Maxinum/Minium Query<rp>)</rp></rt></ruby>，比如区间最大值，区间最小值等等。这一类值都有一个性质就是满足区间加法的性质，即两个区间的区间最大值等于两个区间各自的最大值中较大的一个，但是，如果是求<ruby>区间k小数<rt><rp>(</rp>Range K-th number<rp>)</rp></rt></ruby>的话，就不能用简单的区间加法实现。

但是，我们注意到，在归并排序的过程中，我们其实实现了类似于区间加法的区间合并的操作，因而，我们可以在归并排序的过程中建<ruby>线段树<rt><rp>(</rp>Segment Tree<rp>)</rp></rt></ruby>，用$$T_{i,j}$$表示递归第$$i$$层中第$$j$$位的数字。

同时用$$S_{i,j}$$表示在归并第$$i$$层中位置$$j$$的左侧数字数量（即，比它小的数字数量）

然后，在<ruby>询问<rt><rp>(</rp>Query<rp>)</rp></rt></ruby>过程中我们二分即可。

例题：POJ 2104 K-th Number（这明明是OI题好么？）

{% highlight cpp %}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;<commit_msg>201402181554<commit_after>---
layout: post
title: 区间k小数（1）
tags: [OI,数据结构]
category: 笔记
---

在线段树的学习当中，我们会了解到线段树的应用之一就是求<ruby>**区间极值**<rt>Range Maxinum/Minium Query</rt></ruby>，比如区间最大值，区间最小值等等。这一类值都有一个性质就是满足区间加法的性质，即两个区间的区间最大值等于两个区间各自的最大值中较大的一个，但是，如果是求<ruby>区间k小数<rt>Range K-th number</rt></ruby>的话，就不能用简单的区间加法实现。

但是，我们注意到，在归并排序的过程中，我们其实实现了类似于区间加法的区间合并的操作，因而，我们可以在归并排序的过程中建<ruby>线段树<rt>Segment Tree</rt></ruby>，用$$T_{i,j}$$表示递归第$$i$$层中第$$j$$位的数字。

同时用$$S_{i,j}$$表示在归并第$$i$$层中位置$$j$$的左侧数字数量（即，比它小的数字数量）

然后，在<ruby>询问<rt>Query</rt></ruby>过程中我们二分即可。

例题：POJ 2104 K-th Number（这明明是OI题好么？）

{% highlight cpp %}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
{'fraction_non_alphanumeric': 0.21480026195153898, 'fraction_numerical': 0.014407334643091027, 'mean_word_length': 10.488721804511279, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 61, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7243172', 'n_tokens_mistral': 1010, 'n_tokens_neox': 1067, 'n_words': 73}