I think init of answer array is not needed because it overlaped by another set of questions.

and...

this is my RB Tree. 
but this is very long... that's reason why i didn't post it



#include <cstdio>
#include <cstdlib>
#include <queue>

#include <string>
#include <ctime>
#include <algorithm>
#include <set>

using namespace std;

class Node {
	public:
		Node* left;
		Node* right;
		int red;	// 0 black 1 red
		int key;
		int treesize;
		Node() {
			left = NULL, right = NULL;
			red = 0;
			key = 0;
			treesize = 1;
		}
		Node(int key) {
			left = NULL, right = NULL;
			red = 0;
			this->key = key;
			treesize = 1;
		}
};

class RedBlack {
	public:	
		int treesize;
		Node* base;

		RedBlack() {
			base = new Node();
			treesize = 0;
		}

		~RedBlack() {
			queue<Node*> bfs;
			bfs.push(base);

			while(!bfs.empty()) {
				Node* now = bfs.front();
				bfs.pop();
				if (now) {
					bfs.push(now->left);
					bfs.push(now->right);
					delete now;
					now = NULL;
				}
			}

		}

		int size() {
			return treesize;
		}

		//찾으면 Node* 리턴. 못찾으면 Null 리턴
		//base의 left가 root
		Node* find(int key)
		{
			Node* s = base->left;
			while(s != NULL && s->key != key) {
				if (s->key > key) {
					s = s->left;
				}
				else {
					s = s->right;
				}
			}
			return s;
		}

		int rank(int k)
		{
			if (k < 0 || k > base->left->treesize) return -1;
			Node* s = base->left;
			int nodenum = 1;
			while(1)
			{
				if (s->left) nodenum += s->left->treesize;

				if (nodenum == k) return s->key;
				if (k < nodenum) {
					nodenum -= s->left->treesize;
					s = s->left;
				}
				else {
					nodenum++;
					s = s->right;
				}
			}
			//should not reached
			printf("should not reached!!!!\n");
			(*(int *)0) = 0;
			return -1;
		}

		//pivot의 위치는 변하지 않고, gchild가 회전된 서브트리의 root가 된다.
		//회전된 서브트리의 root의 Pointer가 리턴
		Node* rotate(Node* pivot, int key)
		{
			Node* child, *gchild;
			if (key < pivot->key || pivot == base) child = pivot -> left;
			else child = pivot -> right;

			int save = child->treesize;
			if (key < child->key) {	//L 회전
				gchild = child->left;
				child->treesize -= gchild->treesize;
				if (gchild->right) child->treesize += gchild->right->treesize;

				child->left = gchild->right;
				gchild->right = child;
			}
			else {					//R 회전
				gchild = child->right;
				child->treesize -= gchild->treesize;
				if (gchild->left) child->treesize += gchild->left->treesize;

				child->right = gchild->left;
				gchild->left = child;
			}
			gchild->treesize = save;


			if (key < pivot->key || pivot == base) pivot->left = gchild;
			else pivot->right = gchild;

			return gchild;
		}

		Node* insert(int key)
		{
			Node* t, *parent, *gparent, *ggparent;
			ggparent = gparent = parent = base;
			t = base->left;

			while(t != NULL) {
				if (key == t->key) return NULL;	//이미 같은 키가 존재
				if (t->left != NULL && t-> right != NULL && t->left->red && t->right->red) { //색상변환
					t->red = 1;
					t->left->red = 0, t->right->red = 0;
					if (parent->red) {	//부모가 빨강이면 회전 필요
						gparent->red = 1;
						if ((key < gparent->key) != (key < parent->key)) //LR이나 RL의 첫 회전
							parent = rotate(gparent, key);
						t = rotate(ggparent, key);
						t->red = 0;
					}
					base->left->red = 0;	//root는 항상 검정
				}
				ggparent = gparent;
				gparent = parent;
				parent = t;
				if (key < t->key) t = t->left;
				else t = t->right;
			}

			t = new Node(key);	
			if (key < parent->key || parent == base) parent->left = t;
			else parent->right = t;

			t->red = 1;	//새로 삽입된 노드는 빨강

			//root에서 t의 parent까지 treesize에 1을 더한다
			Node* s = base->left;
			while(s != NULL && s->key != key) {
				s->treesize ++;
				if (s->key > key) {
					s = s->left;
				}
				else {
					s = s->right;
				}
			}

			if (parent->red) {
				gparent->red = 1;
				if ((key < gparent->key) != (key < parent->key)) //LR이나 RL의 첫 회전
					parent = rotate(gparent, key);
				t = rotate(ggparent, key);
				t->red = 0;
			}
			base->left->red = 0;
			

			treesize++;
			return t;
		}


		//삭제 노드와 가장 가까운 빨강 씨앗을 찾아서 빨강 씨앗의 부모의 포인터 리턴
		//이 빨강 씨앗을 아래로 보내면서 삭제한다
		Node* find_seed(int key)
		{
			Node* del, *seed_parent, *parent;
			seed_parent = NULL;
			parent = base;
			del = base->left;

			while(del != NULL) {
				if (key < del->key) {
					//빨강노드나 오른쪽 자식이 빨간 노드 찾기
					if (del->red || (del->right && del->right->red)) seed_parent = parent;
					parent = del;
					del = del->left;
				}
				else {
					//빨강노드나 왼쪽 자식이 빨간 노드 찾기
					if (del->red || (del->left && del->left->red)) seed_parent = parent;
					parent = del;
					del = del->right;
				}
			}
			return seed_parent;
		}


		//원하는 key값의 노드를 red 노드로 만든다.
		//red노드의 leaf노드만 삭제 가능 : 3노드나 4노드이기 때문
		void make_leaf_red(int key)
		{
			Node* seed_parent, *seed, *seed_child;
			seed_parent = find_seed(key);

			if (seed_parent == NULL) {	//빨강 씨앗이 없으면
				seed_parent = base;
				seed = seed_parent->left;
				seed->red = 1;	//루트를 빨강으로 잠시 칠한다
			}
			else {
				//시드 설정
				if (key < seed_parent->key || seed_parent == base) seed = seed_parent->left;
				else seed = seed_parent->right;
			}

			//씨앗이 빨강이 아니면 그 자식을 끌어 올린다.
			if (!seed->red) {
				if (key < seed->key) seed_child = seed->right;
				else seed_child = seed->left;
				seed->red = 1;
				seed_child->red = 0;
				seed_parent = rotate(seed_parent, seed_child->key);
			}

			//외부노드가 아닐 동안
			while(seed->left && seed->right) {
				/*
				   printf("now seed's key value is [%c]\n", seed->key);
				   printf("now seed's left child's key value is [%c]\n", seed->left->key);
				   printf("now seed's right child's key value is [%c]\n", seed->right->key);
				   print(base, 0);
				   */
				seed->red = 0;
				seed->right->red = seed->left->red = 1;

				if (key < seed->key) {
					//if ((seed->right->left || seed->right->right) && 
					//		(seed->right->left->red || seed->right->right->red)) {
					if ((seed->right->left && seed->right->left->red) ||
							(seed->right->right && seed->right->right->red)) {
						if (seed->right->left && seed->right->left->red) {	//RL회전
							seed->right->red = 0;
							rotate(seed, seed->right->left->key);
						}
						else {												//RR회전
							seed->right->right->red = 0;
						}
						rotate(seed_parent, seed->right->key);
					}
					seed_parent = seed;
					seed = seed->left;
				}
				else {
					//if ((seed->left->left || seed->left->right) &&
					//		(seed->left->left->red || seed->left->right->red)) {
					if ((seed->left->left && seed->left->left->red) ||
							(seed->left->right && seed->left->right->red)) {
						if (seed->left->right && seed->left->right->red) {	//LR회전
							seed->left->red = 0;
							rotate(seed, seed->left->right->key);
						}
						else {
							seed->left->left->red = 0;						//LL회전
						}
						rotate(seed_parent, seed->left->key);
					}
					seed_parent = seed;
					seed = seed->right;
				}
			}
		}


		//이 함수를 사용할 떄 반드시 원소가 레드블랙 트리 안에 있는지 체크해 보고 사용할 것!
		//없으면 서브트리의 크기가 뻑남
		//검색하고 시작하도록 해도 되지만 그냥 안했음
		//삭제가 실패하면 NULL 리턴
		Node* erase(int key)
		{
			Node* parent, *del, *center, *pcenter, *son;
			parent = base;
			del = base->left;
			//원소 찾기 : parent를 알아야 하기 때문에 search함수 안씀
			while(del != NULL && key != del->key) {
				del->treesize --;
				parent = del;
				if (key < del->key) del = del->left;
				else del = del->right;
			}
			if (del == NULL) return NULL;
			del->treesize --;

			if (del->right && del->left) {	//내부 노드이면
				pcenter = del;	//삭제할 노드를 대체할 노드를 찾음
				center = del->right;
				while(center->left != NULL) {
					center->treesize--;
					pcenter = center;
					center = center->left; //center는 대체할 키임
				}
				del->key = center->key;	//삭제할 키를 대체할 키로 바꿈
				del = center;			//이제 center를 삭제하도록 조정
				parent = pcenter;
				key = del->key;
			}

			if (del->left || del->right) {	//자식이 하나면 반드시 빨강
				if (del->left) son = del->left;
				else son = del->right;
				son->red = 0;
			}
			else if (del->left == NULL && del->right == NULL) {
				//자식이 없으면 빨강이면 삭제 검정이면 변환 후 삭제
				if (!del->red) make_leaf_red(del->key);
				son = NULL;
			}
			base->left->red = 0;
			if (key < parent->key || parent == base) parent->left = son;
			else parent->right = son;
			delete del;

			treesize--;
			
			return parent;
		}

		void printrecur(Node* node, int depth)
		{
			if (node == NULL) return;
			//for (int i = 0; i < depth; i++) printf("\t");

			printf("%d ", node->key);
			/*
			if (node->red) printf("%c[R](size = %d)\n", (char)(node->key), node->treesize);
			else printf("%c[B](size = %d)\n", (char)(node->key), node->treesize);
			*/

			printrecur(node->left, depth + 1);
			printrecur(node->right, depth + 1);
		}

		void print()
		{
			printf("[");
			printrecur(base->left, 0);
			printf("]\n");
		}
};

int n, m;
int a[100000];
struct query {
	int num;
	int l, r, rank;
};
bool operator < (const query& a, const query& b)
{
	if (a.l == b.l) {
		return (a.r < b.r);
	}
	return (a.l < b.l);
}
query q[50000];
int answer[50000];

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].rank);
		if (q[i].l > q[i].r) {
			int temp = q[i].l; q[i].l = q[i].r; q[i].r = temp;
		}
		q[i].l--, q[i].r--;
		q[i].num = i;
		//printf("%d %d %d\n", q[i].l, q[i].r, q[i].rank);
	}
	sort(q, q + m);

	RedBlack rb;

	for (int i = q[0].l; i <= q[0].r; i++) {
		rb.insert(a[i]);
	}
	answer[q[0].num] = rb.rank(q[0].rank);

	for (int i = 1; i < m; i++) {
		if (q[i - 1].r >= q[i].r) {
			(* (int *)0) = 0;
		}
		if (q[i - 1].r < q[i].l) {
			for (int j = q[i - 1].l; j <= q[i - 1].r; j++) rb.erase(a[j]);
			for (int j = q[i].l; j <= q[i].r; j++) rb.insert(a[j]);
		}
		else {
			for (int j = q[i - 1].l; j < q[i].l; j++) rb.erase(a[j]);
			for (int j = q[i - 1].r + 1; j <= q[i].r; j++) rb.insert(a[j]);
		}
		answer[q[i].num] = rb.rank(q[i].rank);
	}

	for (int i = 0; i < m; i++) {
		printf("%d\n", answer[i]);
	}

	return 0;
}

• ~~-_-|', Long... 13K.(Inside) (11651) C6H6 2006-03-15 14:20:06
  • Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 16:55:46
  • Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 17:32:27
  • Finally, I got accepted (537) insany 2006-03-15 17:33:49