POJ - 2104 (K - th Number 구분 트 리)

[제목 설명] n 개의 숫자 가 한 열 로 배열 되 어 있 고 m 개의 질문 이 있 습 니 다. 형식 은 left right k 입 니 다. 구간 [left, right] 에서 k 번 째 로 큰 데 이 터 는 얼마 입 니까?건축 도: 나 무 를 만 드 는 과정 이 비교적 간단 합 니 다. 구간 [l, r] 에 대해 먼저 원 배열 의 순 서 를 통 해 이 구간 의 중위 수 a [mid] 를 찾 습 니 다. a [mid] 보다 작은 수 는 왼쪽 나무 [l, mid - 1] 에 그 어 넣 고 오른쪽 나무 [mid, r] 보다 큽 니 다.이 동시에 i 번 째 수 a [i] 에 대해 서 는 [l, i] 구간 에 얼마나 많은 수가 왼쪽 나무 에 그 어 졌 는 지 기록 합 니 다.마지막 으로 왼쪽 나무 구간 [l, mid - 1] 과 오른쪽 나무 구간 [mid, r] 을 재 귀적 으로 계속 만 들 면 됩 니 다.나 무 를 만 들 때 같은 하위 트 리 로 나 뉘 는 요소 에 대해 요소 간 의 상대 적 인 위 치 는 바 꿀 수 없 음 을 주의해 야 합 니 다.
찾 는 과정 에서 주요 문 제 는 찾 을 구간 을 확인 하 는 것 이다.깊이 는 dep 이 고 큰 구간 [L, R] 에서 동네 [l, r] 의 k 요 소 를 찾 습 니 다.우리 의 생각 은 먼저 [l, r] 중의 k 요소 가 [L, R] 의 어느 서브 트 리 에 있 는 지 판단 한 다음 에 해당 하 는 동네 와 k 를 찾 아 재 귀적 으로 찾 아 동네 간 의 l = = r 까지 하 는 것 이다.이전 기록 을 통 해 알 수 있 듯 이 구간 [L, l - 1] 에 (toleft [dep] [l - 1] - toleft [dep] [L - 1]) 이 왼쪽 나무 에 들 어가 x 로 기록 되 어 있다.
동 리 구간 [L, r] 에는 (toleft [dep] [r] - toleft [dep] [L - 1]) 개의 수가 왼쪽 나무 에 들 어가 Y 로 기록 되 어 있다.그래서 우 리 는 구간 단지 간 [l, r] 에 (y - x) 개의 수가 왼쪽 나무 에 들 어 가 는 것 을 알 고 있다.그러면 (y - x) > = k 라면 왼쪽 트 리 에서 계속 찾 으 세 요. 그렇지 않 으 면 오른쪽 트 리 에서 계속 찾 으 세 요.
  이 어 찾 는 동네 문 제 를 해결 했다.  다음 에 찾 으 려 는 것 이 왼쪽 나무 라면 동네 간 은 [L + ([L, l - 1] 구간 에서 왼쪽 나무 에 들 어 가 는 개수), L + ([L, r] 구간 에서 왼쪽 나무 에 들 어 가 는 개수) - 1] 이 어야 합 니 다.즉 구간 [L + x, L + y - 1].    분명히 여기 k 는 변 하지 않 아 도 된다.  다음 에 찾 으 려 는 것 이 오른쪽 나무 라면 동네 간 은 [mid + ([L, l - 1] 구간 에서 오른쪽 나무 에 들 어 가 는 개수), mid + ([L, r] 구간 에서 오른쪽 나무 에 들 어 가 는 개수) - 1] 이 어야 합 니 다.    즉 구간 [mid + (l - L - x), mid + (r - L - y)].    분명히 여기 서 k 는 구간 에서 왼쪽 나무 에 들 어간 개 수 를 빼 야 한다. 즉, k 는 k - (y - x) 로 변 한다.

/*==========================================================*\
|    
\*==========================================================*/
#define MAX_SIZE 100005
int sorted[MAX_SIZE];//        
int toleft[25][MAX_SIZE];
int tree[25][MAX_SIZE];
void build_tree(int left, int right, int deep) 
{
	int i;
	if (left == right) return ;
	int mid = (left + right) >> 1;
	int same = mid - left + 1; //        
	for (i = left; i <= right; ++i) {//                   
		if (tree[deep][i] < sorted[mid]) {
			--same;
		}
	}
	int ls = left;
	int rs = mid + 1;
	for (i = left; i <= right; ++i) {
		int flag = 0;
		if ((tree[deep][i] < sorted[mid]) || (tree[deep][i] == sorted[mid] && same > 0)) {
			flag = 1;
			tree[deep + 1][ls++] = tree[deep][i];
			if (tree[deep][i] == sorted[mid])
				same--;
		} else {
			tree[deep + 1][rs++] = tree[deep][i];
		}
		toleft[deep][i] = toleft[deep][i - 1]+flag;
	}
	build_tree(left, mid, deep + 1);
	build_tree(mid + 1, right, deep + 1);
}
int query(int left, int right, int k, int L, int R, int deep)
{
	if (left == right)
		return tree[deep][left];
    int mid = (L + R) >> 1;
	int x = toleft[deep][left - 1] - toleft[deep][L - 1];//  left              
	int y = toleft[deep][right] - toleft[deep][L - 1];// right          
	int ry = right - L - y;// right              
	int cnt = y - x;//[left,right]            
	int rx = left - L - x;//left             
	if (cnt >= k) {
		//printf("sss %d %d %d
", xx++, x, y);
		return query(L + x, L + y - 1, k, L, mid, deep + 1);
	}
	else {
		//printf("qqq %d %d %d
", xx++, x, y);
		return query(mid + rx + 1, mid + 1 + ry, k - cnt, mid + 1, R, deep + 1);
	}
}
int main()
{
	int m, n;
	int a, b, k;
	int i;
	while (scanf("%d%d", &m, &n) == 2) {
		for (i = 1; i <= m; ++i) {
			scanf("%d", &sorted[i]);
			tree[0][i] = sorted[i];
		}
		sort(sorted + 1, sorted + 1 + m);
		build_tree(1, m, 0);
		for (i = 0; i < n; ++i) {
			scanf("%d%d%d", &a, &b, &k);
			printf("%d
", query(a, b, k, 1, m, 0));
		}
	}
	return 0;
}