Baekjoon Online Judge 13538

https://www.acmicpc.net/problem/13538

이 문제는 Persistent Segment Tree를 이용하면 효율적으로 해결할 수 있다.

수의 범위가 1~500000이므로 2^19(524288)개의 리프 노드를 만들고, 각 노드는 해당하는 구간에 포함되는 원소의 개수를 들고 있는다.

즉, k번째 Segment Tree의 [l, r) 노드는 1~k번째 원소 중 l 이상 r 미만인 수의 개수이다.

이렇게 트리를 만들면 각 쿼리는 다음과 같은 방법으로 처리할 수 있다.

0. 0번 트리를 만든다. 수열이 비어있으므로 모든 노드는 0을 값으로 갖는다.

1. 새로운 트리를 만든다. 이 트리는 현재까지의 수열에 x를 추가한 트리이고, 이를 N번 트리로 명명한다.

2. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 x와 xor한 값이 더 큰 방향에 원소가 있으면 해당 방향으로, 없다면 반대 방향으로 움직이는 것을 19번 반복하면 y를 구할 수 있다.

3. N -= k

4. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 x+1을 찾아가면서, 오른쪽 자식으로 갈 때 R번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 더해주고 L-1번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 빼 주는 것을 19번 반복하면 x보다 작거나 같은 원소의 개수를 구할 수 있다.

5. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 R번 트리에서 왼쪽 자식에 포함되는 원소의 개수에서 L-1번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 뺀 것이 k 이상이라면 왼쪽 자식으로 이동하고, 아니라면 그 값을 k에서 뺀 뒤 오른쪽 자식으로 이동한다. 이를 19번 반복해서 도착한 노드의 번호가 k번째로 작은 수이다.

전체 시간복잡도는 O(M log x)가 된다.

#include <cstdio>

struct node {
	node *l, *r;
	int x;
} T[11050000], *a[500005];
int Tn, n;

void Add(node *p, node *q, int x, int y) {
	p->x = q->x + 1;
	if (y < 0) return;
	if (x >> y & 1) {
		p->r = T + ++Tn;
		p->l = q->l;
		Add(p->r, q->r, x, y - 1);
	}
	else {
		p->l = T + ++Tn;
		p->r = q->r;
		Add(p->l, q->l, x, y - 1);
	}
}

int Xor(node *p, node *q, int x, int y) {
	if (y < 0) return 0;
	if (x >> y & 1 ? p->l->x == q->l->x : p->r->x != q->r->x) return 1 << y | Xor(p->r, q->r, x, y - 1);
	return Xor(p->l, q->l, x, y - 1);
}

int Sum(node *p, int x, int y) {
	if (y < 0) return 0;
	if (x >> y & 1) return p->l->x + Sum(p->r, x, y - 1);
	return Sum(p->l, x, y - 1);
}

int Kth(node *p, node *q, int x, int y) {
	if (y < 0) return 0;
	if (p->l->x - q->l->x < x) return 1 << y | Kth(p->r, q->r, x - p->l->x + q->l->x, y - 1);
	return Kth(p->l, q->l, x, y - 1);
}

int main() {
	int i, j, k, m;
	scanf("%d", &m);
	for (i = 1; i < 1 << 19; i++) {
		T[i].l = T + (i << 1);
		T[i].r = T + (i << 1 | 1);
	}
	a[n = 0] = T + 1;
	Tn = 1 << 20;
	while (m--) {
		scanf("%d", &i);
		switch (i) {
		case 1:
			scanf("%d", &i);
			a[++n] = T + ++Tn;
			Add(a[n], a[n - 1], i, 18);
			break;
		case 2:
			scanf("%d%d%d", &i, &j, &k);
			printf("%d\n", Xor(a[j], a[i - 1], k, 18));
			break;
		case 3:
			scanf("%d", &i);
			n -= i;
			break;
		case 4:
			scanf("%d%d%d", &i, &j, &k);
			printf("%d\n", Sum(a[j], k + 1, 18) - Sum(a[i - 1], k + 1, 18));
			break;
		case 5:
			scanf("%d%d%d", &i, &j, &k);
			printf("%d\n", Kth(a[j], a[i - 1], k, 18));
			break;
		}
	}
}