255. 第K小数

本文主要是介绍255. 第K小数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：255. 第K小数

算法分析

据说这道题可以用来练习多种高级数据结构，本题是用可持久化线段树解的。算法分析可参考进阶指南。需要注意的是：

1. 线段树的空间开销。离散化后，取值区间最大为[1,n]。这是值域。在值域上建立初始线段树，因为不是按照层次编号，所以开销为$2\ast n$。后面$n$个数字分别插进去，建可持久化树，每次开销为$logn$，共$n$次。$n$最大为100000，所以空间总开销$2\ast n+18\ast n=20n$足矣。

2. 时间开销每次插入和查询都是log级别的，因此为$O((n+m)logn)$。

3. 用$val[]$记录离散化后原来的大小，最后输出时需要还原。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define ll long long 
const int N = 1e5 + 10;
int a[N], lsh[N], val[N];
int n, m;
struct node
{int lc, rc, dat; // dat是该点的数字个数  
}tr[2*N+18*N];
int root[N], tot;
int re()
{int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f; 
}
int szbuild(int l, int r)
{int p = ++tot;if (l == r){tr[p].dat = 0; return p;}int mid = (l + r) >> 1;tr[p].lc = szbuild(l, mid);tr[p].rc = szbuild(mid + 1, r);tr[p].dat = tr[tr[p].lc].dat+ tr[tr[p].rc].dat;return p;
}
int szchange(int cur, int l, int r, int x, int val)
{int p = ++tot;tr[p] = tr[cur];if (l == r){tr[p].dat += val; return p;  // 有可能有重复的  }int mid = (l + r) >> 1;if (x <= mid)tr[p].lc = szchange(tr[cur].lc, l, mid, x, val);else tr[p].rc = szchange(tr[cur].rc, mid + 1, r, x, val);tr[p].dat = tr[tr[p].lc].dat + tr[tr[p].rc].dat;return p;
}
int szask(int pr, int ql, int l, int r, int k)
{if (l == r) return val[l];  // 因为是对值域建树，所以直接范围的l就是值，还原回原先的数  int mid = (l + r) >> 1;int num = tr[tr[pr].lc].dat - tr[tr[ql].lc].dat;  // [l,r]区间有多少数  if (num >= k) return szask(tr[pr].lc, tr[ql].lc, l, mid, k);else return szask(tr[pr].rc, tr[ql].rc, mid + 1, r, k - num);
}
int main()
{n = re(); m = re();for (int i = 1; i <= n; ++i) a[i] = lsh[i] = re();// 离散化  sort(lsh + 1, lsh + n + 1);int cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1;  // 离散化后取值范围是[1, cnt]  for (int i = 1; i <= n; ++i){int t = a[i];a[i] = lower_bound(lsh + 1, lsh + n + 1, a[i]) - lsh;val[a[i]] = t;}	// 初始建树 root[0] = szbuild(1, cnt); // 将1 ~ n个数字构建可持久化线段树，相当于单点修改 for (int i = 1; i <= n; ++i) root[i] = szchange(root[i-1], 1, cnt, a[i], 1);// m个查询 int l, r, k;for (int i = 1; i <= m; ++i){l = re(); r = re(); k = re();printf("%d\n", szask(root[r], root[l-1], 1, cnt, k));} return 0;
}

反思与总结

数据结构题码量大、思维要求低，细节多。得多练。

这篇关于255. 第K小数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---