pku2104.cpp

PKU2104的源代码

////POJ2104 K-th Number
///segment tree 找数据

#include <cstdio>
#include <algorithm>
using namespace std;

bool flag;

const int MAX_Elem = 100001;
struct Node{
	int left, right;
	int dep;
	Node *lcd, *rcd;
	void Build(int, int, int);
	void Calculate();
}SegTree[2*MAX_Elem+5], *root=&SegTree[0];

int Element[18][MAX_Elem];
int up, num;
int st, ed, dst;
int pre_num;

void Node::Build(int l, int r, int depth)
{
	left = l; right = r;dep = depth;
	if(l==r){
		scanf("%d",&Element[dep][l]);
	}
	int mid = (l + r) >> 1;
	if(r-l>=1){
		lcd = &SegTree[++up];
		lcd->Build(l, mid, depth+1);
		rcd = &SegTree[++up];
		rcd->Build(mid+1, r,depth+1);
	}else if(r==l){
		lcd = rcd = NULL;
		return;
	}
	/////////////////////////归并排序/////////////////////////////
	int i = left, j = mid + 1, k = left;
	while(i<=mid && j<=right){
		if(Element[dep+1][i]<Element[dep+1][j]){
			Element[dep][k++] = Element[dep+1][i++];
		}else{
			Element[dep][k++] = Element[dep+1][j++];
		}
	}
	while(i<=mid)Element[dep][k++] = Element[dep+1][i++];
	while(j<=right)Element[dep][k++] = Element[dep+1][j++];
	//////////////////////////////////////////////////////////////
}

void Node::Calculate()
{
	if(st>right||ed<left) return;
	if(left==right){
		if(Element[dep][left]<num) pre_num++;
		if(Element[dep][left]==num)flag = true;
	}else if(left>=st && right<=ed){
		int low = left, high = right, mid=(low + high) >> 1;
		for(;low<=high;){
			if(num==Element[dep][mid]){
				flag = true;
				break;
			}else if(num > Element[dep][mid]){
				low = mid + 1;
				mid = (low + high) >> 1;
			}else{
				high = mid - 1;
				mid = (low + high) >> 1;
			}
		}
	
		if(num>Element[dep][mid]){
			pre_num += mid - left + 1;
		}else if(low<=high){
			pre_num += mid - left;
		}
	}else{
		if(st<=lcd->right){
			lcd->Calculate();
		}
		if(ed>=rcd->left){
			rcd->Calculate();
		}
	}
}

int main()
{
	int n, m;
	int i, j, k;
	scanf("%d %d",&n, &m);
	up = 0;
	root->Build(0, n-1, 0);

	for(i=0;i<m;i++){
		scanf("%d%d%d",&st,&ed,&dst);
		st--; ed--; dst--;
		int d, low, high, mid;
		low = 0; high = n -1; mid = (low + high) >> 1;
		for(;low<=high;){
			flag = false;
			pre_num = 0;
			num = Element[0][mid];
			root->Calculate();
			if(pre_num==dst){
				if(flag){
					printf("%d\n",Element[0][mid]);
					break;
				}else{
					low = mid + 1;
					mid = (low + high) >> 1;
				}
			}else if(pre_num<dst){
				low = mid + 1;
				mid = (low + high) >> 1;
			}else{
				high = mid - 1;
				mid = (low + high) >> 1;
			}
		}
	}
	return 0;
}