26 Oct 10 询问区间内第K大数

下面是我N年前写的东西了。。最近突然很多人问我这个问题，不知道是不是因为天津赛区的原因。。

原题就是给一个数组，然后询问一段区间内的第K大数。。。

发信人: mmd (mmd), 信区: ACM_ICPC
标  题: F题解题报告
发信站: 珞珈山水BBS站 (Tue Apr  1 12:10:07 2008), 转信

解题报告:

F题:

先说一下n log(n)预处理, log(n) ^ 3查询的方法

线段树中的节点不是存的点, 是存一条线段.(也就是很多点, 个数是这条线段的长度)

线段树中的节点是有序的, 序是按key排的.

结构跟归并排序里面的一样的.

这样可以用合并两个有序序列, 来建树, 很明显, 建树的复杂度是n log(n)的.

这样的一个数据结构, 很明显我们是可以查找一个区间中的一个数在有序表中的哪个位
置.

我们如果要找第k个数话, 便可以对这个数进行二分, 然后在区间中查找.

这样总体复杂度应该是n log(n) + log(n) ^ 3

这个方法很明显是非常慢的,.

因为首先要有一个二分, 这个复杂度就比较高, 因为数据是可以无限大的(可以通过离散
化来减小数据范围, 但显的不够优美)

第二要在线段树中对线段进行分割, 麻烦, 常数也比较大.

第三这个线段树的实现比较麻烦, 代码较长, 也容易错.

下面说一下n log(n) + log(n)的方法

这个方法, 与上面所说的方法在数据结构上要有所改变

1.      线段树也是存的一条线段(很多点)

2.      线段树也是有序的, 但是是按position有序的(按在原来数组中的位置有序)

3.      线段树中左孩子节点的key要比右孩子的key小

想清楚这个数据结构后, 可以想一下如何在这种数据结构上进行操作

上面这种结构非常巧妙, 是我无意中看一个外国人说的, 看到这个结构后, 我加了以下
几个简单附加结构, 就可以对这个问题比较完美的处理了.

1.a[n], a[i]表示从1 到 i中有多少个节点在左子树

通过这个数组, 我们可以计算出一个区间s – t中有多少个节点在左子树, 有多少个节点
在右子树, 为什么有这个东西呢?

有了这个东西, 我们就可以对我们要查找的区间进行递归了, 并且每次只会递归到一层
中, 所以复杂度是log(n)的

有了这个东西, 问题就基本解决了.

但我们递归的时候, 区间是变化的, 我们应该如何去应对这个改变呢?

比较简单的方法就是进行一次二分, 但是这样复杂度就变成log(n) ^ 2的.

为了解决这个问题, 我再次对区间进行了记录. 也就是对区间记录一个映射, 记录这个
区间在左孩子中所对应的区间和在右孩子中所对应的区间.

这些记录, 都可以能过合并两个有序序列的方法来建树, 都是n log(n)的.

说到这里, 这个问题就比较完美的解决了, 这个方法常数比较小, 又是单层递归, 可以
写成迭代形式.

参考代码：

//author: momodi@whuacm
class Tree {
	public:
		static const int maxn = 100000;
		struct Seg {
			int s, t;
			struct Acc {
				int b, c, l, r;
			};
			Acc *acc;
		}seg[maxn * 3];
		int n;
		int *dt;
		int id[maxn];
		void init(int _n, int *_dt) {
			n = _n;
			dt = _dt;
			for (int i = 0; i < n; ++i) {
				id[i] = i;
			}
			sort(id, id + n, cmp(dt));
			build(0, n, 0);
		}
		int find(int s, int t, int k, int v = 0) {
			if (s + 1 == t) {
				return dt[seg[v].acc[s].b];
			}
			int tmp = seg[v].acc[t - 1].c - ((s > 0)? seg[v].acc[s - 1].c: 0);
			if (k <= tmp) {
				return find(seg[v].acc[s].l, seg[v].acc[t].l, k, v * 2 + 1);
			}else {
				return find(seg[v].acc[s].r, seg[v].acc[t].r, k - tmp, v * 2 + 2);
			}
		}
	private:
		struct cmp {
			int *dt;
			cmp(int *_dt):dt(_dt){};
			bool operator () (const int &a, const int &b) {
				return dt[a] < dt[b];
			}
		};
		void build(int s, int t, int v) {
			seg[v].s = s;
			seg[v].t = t;
			if (s + 1 == t) {
				delete seg[v].acc;
				seg[v].acc = new Seg::Acc[2];
				seg[v].acc[0].b = id[s];
				return ;
			}
			int m = (s + t + 1) / 2;
			build(s, m, v * 2 + 1);
			build(m, t, v * 2 + 2);
			merge(seg[v].acc, seg[v * 2 + 1].acc, seg[v * 2 + 2].acc, t - s, m - s, t - m);
		}
		void merge(Seg::Acc *&d, const Seg::Acc *l, const Seg::Acc *r, int n, int ln, int rn) {
			delete d;
			d = new Seg::Acc[n + 1];
			d[n].l = ln;
			d[n].r = rn;
			for (int i = 0, li = 0, ri = 0; i < n; ++i) {
				if (ri == rn || li < ln && l[li].b < r[ri].b) {
					d[i].c = ((i > 0)? d[i - 1].c + 1: 1);
					d[i].l = li;
					d[i].r = ri;
					d[i].b = l[li++].b;
				}else {
					d[i].c = ((i > 0)? d[i - 1].c: 0);
					d[i].l = li;
					d[i].r = ri;
					d[i].b = r[ri++].b;
				}
			}
		}
};
Tree tree;
const int maxn = 100000;
int dt[maxn];
int main()
{
	int n, m;
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; ++i) {
			scanf("%d", dt + i);
		}
		tree.init(n, dt);
		while (m--) {
			int s, t, k;
			scanf("%d %d %d", &s, &t, &k);
			printf("%d\n", tree.find(s - 1, t, k));
		}
	}
    return 0;
}

Tags: 归并排序, 第K大树, 线段树