POJ 1442 블랙 박스 (데이터 구조)

제목 유형  데이터 구조
제목
최대 30000 개의 수 를 제시 하고 최대 30000 번 을 물 어 봅 니 다. 앞의 x 개 수 를 고려 할 때 y 가 작은 수 는 얼마 입 니까? 그 중에서 y 는 1 -> 30000 에서 해당 하 는 x 입력 으로 제 시 됩 니 다.
문제 풀이 방법
선분 트 리, treap, splay 등 데이터 구조 로 만 들 수 있 습 니 다.
참조 코드 - 궁금 한 점 이 있 으 시 면 아래 에 댓 글 을 남 겨 주시 면 바로 답 해 드 리 겠 습 니 다.
treap

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>

using namespace std;

const int maxn = 30000 + 10;
int a[maxn], b[maxn];

struct Node {
	Node * ch[2];
	int r;
	int v;
	int s;
	Node(int v) : v(v) { ch[0] = ch[1] = NULL; r = rand(); s = 1; }
	int cmp(int x) const {
		if(x == v) return -1;
		return x < v ? 0 : 1;
	}
	void maintain() {
		s = 1;
		if(ch[0] != NULL) s += ch[0]->s;
		if(ch[1] != NULL) s += ch[1]->s;
	}
};

struct Treap {
	Node * rt;
	Treap() { rt = NULL; }
	
	void rotate(Node* & o, int d) {
		Node * k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; 
		o->maintain(); k->maintain();
		o = k;
	}

	void insert(Node* & o, int x) {
		if(o == NULL) o = new Node(x);
		else {
			int d = (x > o->v ? 1 : 0); //         
			insert(o->ch[d], x);
			if(o->ch[d]->r > o->r) rotate(o, d ^ 1);
		}
		o->maintain();
	}

	void remove(Node* & o, int x) {
		int d = o->cmp(x);
		if(d == -1) {
			Node * u = o;
			if(o->ch[0] != NULL && o->ch[1] != NULL) {
				int d2 = (o->ch[0] > o->ch[1] ? 1 : 0);
				rotate(o, d2); remove(o->ch[d2], x);
			}
			else {
				if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
				delete u;
			}
		}
		else remove(o->ch[d], x);
		if(o != NULL) o->maintain();
	}

	int kth(Node* & o, int k) { //  k 
		Node * t = o;
		while(1) {
			int s = t->ch[0] == NULL ? 0 : t->ch[0]->s;
			if(k <= s) t = t->ch[0];
			else if(k == s + 1) return t->v;
			else { k -= s + 1; t = t->ch[1]; }
		}
	}

	void removetree(Node* & x) {
		if(x == NULL) return ;
		if(x->ch[0] != NULL) removetree(x->ch[0]);
		if(x->ch[1] != NULL) removetree(x->ch[1]);
		delete x;
		x = NULL;
	}
};

int main() {
	freopen("in", "r", stdin);
  srand(time(0));

	int n, m;
	while(scanf("%d%d", &m, &n) != EOF) {
		for( int i=0; i<m; i++ ) scanf("%d", &a[i]);
		for( int i=0; i<n; i++ ) scanf("%d", &b[i]);
		Treap trp;
		int i = 0;
		int j = 0;
		int tj = 0;
		for( int i=0; i<n; i++ ) {
			while(tj < b[i]) {
				trp.insert(trp.rt, a[tj]);
				tj++;
			}
			printf("%d
", trp.kth(trp.rt, i+1));
		}
		trp.removetree(trp.rt);
	}
	return 0;
}

splay

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 30000 + 10;
int a[maxn], b[maxn];

struct Node {
	Node * ch[2];
	int v;
	int s;
	Node(int v) : v(v) { ch[0] = ch[1] = NULL; s = 1; }
	int cmp(int x) const {
		if(x == v) return -1;
		return x < v ? 0 : 1;
	}
	void maintain() {
		s = 1;
		if(ch[0] != NULL) s += ch[0]->s;
		if(ch[1] != NULL) s += ch[1]->s;
	}
};

struct Splay {
	Node * rt;
	Splay() { rt = NULL; }
	void rotate(Node* & o, int d) {
		Node * k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; 
		o->maintain(); k->maintain();
		o = k;
	}

	void splay(Node* & o, int x) {
		int d = o->cmp(x);
		if(d != -1) {
			Node * p = o->ch[d];
			int d2 = p->cmp(x);
			if(d2 != -1) {
				splay(p->ch[d2], x);
				if(d == d2) rotate(o, d^1); else rotate(o->ch[d], d);
			}
			rotate(o, d^1);
		}
	}

	void insert(Node* & o, int x) {
		if(o == NULL) o = new Node(x);
		else {
			int d = x > o->v ? 1 : 0; //          
			insert(o->ch[d], x);
			o->maintain();
		}
	}

	int findMax(Node* & o) {
		Node * t = o;
		while(t->ch[1] != NULL) t = t->ch[1];
		splay(o, t->v);
		return o->v;
	}

	void remove(int x) {
		splay(rt, x);

		Node * t = rt;
		if(rt->ch[0] == NULL) {
			rt = rt->ch[1];
			delete t;
		}
		else {
			findMax(rt->ch[0]);
			rt->ch[0]->ch[1] = rt->ch[1];
			rt = rt->ch[0];
			rt->maintain();
			delete t;
		}
	}

	int kth(Node* & o, int k) { //  k 
		Node * t = o;
		while(1) {
			int s = t->ch[0] == NULL ? 0 : t->ch[0]->s;
			if(k <= s) t = t->ch[0];
			else if(k == s + 1) return t->v;
			else { k -= s + 1; t = t->ch[1]; }
		}
	}

	void removetree(Node* & o) {
		if(o == NULL) return ;
		if(o->ch[0] != NULL) removetree(o->ch[0]);
		if(o->ch[1] != NULL) removetree(o->ch[1]);
		delete o;
		o = NULL;
	}
};

int main() {
	int n, m;
	scanf("%d%d", &m, &n);
	for( int i=0; i<m; i++ ) scanf("%d", &a[i]);
	for( int i=0; i<n; i++ ) scanf("%d", &b[i]);
	Splay spy;
	int i = 0;
	int tj = 0;
	for( int i=0; i<n; i++ ) {
		while(tj < b[i]) {
			spy.insert(spy.rt, a[tj]);
			spy.splay(spy.rt, a[tj]);
			tj++;
		}
		int ans = spy.kth(spy.rt, i+1);
		spy.splay(spy.rt, ans);
		printf("%d
", ans);
	}
	return 0;
}