POJ2104 k-th number 划分树

又是不带修改的区间第k大，这次用的是一个不同的方法，划分树，划分树感觉上是模拟了快速排序的过程，依照pivot不断地往下划分，然后每一层多存一个toleft[i]数组，就可以知道在这一层里从0到i里有多少个被划分到了左子树，知道区间有多少个被分到左子树，就可以一路递归下去，不需要像函数式线段数一样，二分再加query，所以每次询问的复杂度也只是O(nlogn)，空间复杂度的话就是O(nlogn)，具体的介绍很多个链接都有，具体看下面给出的两个链接，它们对我起到非常大的帮助。

http://blog.csdn.net/famousdt/article/details/7064866

http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html

写的时候尤其是递归询问区间的时候很容易出现off-by-one error，我在纸上比划了很久才搞清楚的。有点微弱呀－ －0下面是代码。800多ms，是函数式线段数的时间的一半吧

#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define maxn 100000
using namespace std;

int tree[22][maxn + 50];
int toleft[22][maxn + 50];
int as[maxn + 50];
int n, q;

void build(int l, int r, int dep)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	int same = mid - l + 1;
	for (int i = l; i <= r; i++){
		if (tree[dep][i] < as[mid]){
			same--;
		}
	}
	int ls = l;
	int rs = mid + 1;
	for (int i = l; i <= r; i++){
		if (tree[dep][i] < as[mid]) tree[dep + 1][ls++] = tree[dep][i];
		else if (tree[dep][i] == as[mid] && same) tree[dep + 1][ls++] = tree[dep][i], same--;
		else tree[dep + 1][rs++] = tree[dep][i];
		toleft[dep][i] = toleft[dep][l - 1] + ls - l;
	}
	build(l, mid, dep + 1);
	build(mid + 1, r, dep + 1);
}

int query(int left, int right, int k, int L, int R, int dep)
{
	if (left == right) return tree[dep][left];
	int mid = (L + R) >> 1;
	int x = toleft[dep][left - 1] - toleft[dep][L - 1];
	int y = toleft[dep][right] - toleft[dep][L - 1];
	int rx = left - 1 - L + 1 - x;
	int ry = right - L + 1 - y;
	int cnt = y - x;
	if (cnt >= k) return query(L + x, L + y - 1, k, L, mid, dep + 1);
	// 注意off-by-one error. 
	else return query(mid + 1 + rx,mid + 1 + ry - 1, k - cnt, mid + 1, R, dep + 1);
}

int main()
{
	while (cin >> n >> q)
	{
		for (int i = 1; i <= n; i++){
			scanf("%d", as + i);
			tree[0][i] = as[i];
		}
		sort(as + 1, as + n + 1);
		build(1, n, 0);
		int li, ri, ki;
		for (int i = 0; i < q; i++){
			scanf("%d%d%d", &li, &ri, &ki);
			printf("%d
", query(li, ri, ki, 1, n, 0));
		}
	}
	return 0;
}