글 읽기 - 세그먼트 응용같은데... 모르겠어요

akane 5년 전 0

각 노드에는 하위 리프노드들의 범위와 개수가 저장돼있구요

한쪽으로 쏠려서 O(n)연산하는 경우를 방지 하려고

insert 할 때마다 한쪽으로 치우침을 확인해서 다른쪽으로 insert 하는 식으로 처리했어요

추가할 때마다 O(lg n), query를 계산할 때마다 O(lg n) 이니 n lg n이고

메모리는 노드당 20byte가 최대 400만개니까 제한 범위 이내라고 생각하는데..

어떻게 풀어야 하나요??

#include<cstdio>

//각 노드는 하위 리프노드들의 범위(min~max), 개수(size)를 저장합니다
struct Node{
	int max = 0, min = 0, size = 0;
	Node * left = NULL, * right = NULL;
} * ROOT;

//remove(root, Max(or Min)) root의 최대 혹은 최소값을 지웁니다
//최대, 최소값이 지워지면 그 다음 최대, 최소값을 갱신하며 갱신한 값을 반환합니다
enum{ Max, Min };
int remove(Node * root, bool b){
	int tmp;
    //하위 리프노드 중 하나를 지울 것이므로 size--
	root->size--;
	
    //원래 size가 2인 경우 하위노드를 모두 지우고 자신이 지워지지 않은 하위노드가 됩니다
	if(root->size == 1){
		delete root->left;
		root->left = NULL;
		delete root->right;
		root->right = NULL;
		if(b) root->min = root->max;
		else root->max = root->min;
		return root->min;
	}
	if(b){
        //지워야하는 쪽이 하나만 있으면 재귀호출하지 않고 바로 지웁니다
		if(root->left->size == 1){
			tmp = root->right->min;
			delete root->left;
			root->left = NULL;
		}
		else tmp = remove(root->left, b);
        //min 값을 갱신하고 갱신된 값을 반환합니다
		return root->min = tmp;
	}
	if(root->right->size == 1){
		tmp = root->left->max;
		delete root->right;
		root->right = NULL;
	}
	else tmp = remove(root->right, b);
	return root->max = tmp;
}

// insert(root, val) root에 val 값을 추가합니다
void insert(Node * root, int val){
    //하위 리프 중 하나가 추가되므로 size++
	root->size++;
    //추가되는 값이 전체범위를 넘으면 갱신해줍니다
	if(root->max < val) root->max = val;
	else if(root->min > val) root->min = val;
	
	if(root->size == 1){
		root->min = root->max = val;
		return;
	}
	else if(root->size == 2){
		root->left = new Node;
		root->right = new Node;
		insert(root->left, root->min);
		insert(root->right, root->max);
	}
	else{
		if(root->left == NULL) root->left = new Node;
		if(root->right == NULL) root->right = new Node;
        //왼쪽에 추가하려는데 이미 왼쪽 개수가 오른쪽보다 많으면,
        //추가했을때 불균형이 생기므로 왼쪽의 가장 큰 값을 미리 오른쪽에 옮겨줍니다
		if(root->right->min > val){
			if(root->left->size > root->right->size){
				insert(root->right, root->left->max);
				remove(root->left, Max);
			}
			insert(root->left, val);
		}
		else{
			if(root->right->size > root->left->size){
				insert(root->left, root->right->min);
				remove(root->right, Min);
			}
			insert(root->right, val);
		}
	}
}
//세그먼트 트리의 query 함수입니다
int query(Node * root, int L, int R){
	if(root == NULL) return 0;
	if(root->max < L || root->min > R) return 0;
	if(root->min >= L && root->max <= R) return root->size;
	return query(root->left, L, R) + query(root->right, L, R);
}
int n, m, x, l, r;
int main(){
	ROOT = new Node;
    
    scanf("%d", &n);
	while(n--){
        scanf("%d", &x);
		insert(ROOT, x);
	}
    
    scanf("%d", &m);
	while(m--){
        scanf("%d", &x);
		if(x == 1){
            scanf("%d", &x);
			insert(ROOT, x);
		}
		else {
            scanf("%d %d", &l, &r);
            // 전체 개수 - 포함하는 개수
			printf("%d\n", r-l-query(ROOT, l, r)+1);
		}
	}
	return 0;
}

yukariko 5년 전 0

구현을 정확하게 이해하지 못했지만

query는 왼쪽, 오른쪽을 다 탐색하기 때문에 최악에 O(n)이 아닌가요?

이 문제는 미리 만들어져있는 세그먼트 트리에서 각 리프노드의 가중치를 0, 1로 두면 sum - 세그먼트 트리를 통해 해결할 수 있습니다.

yukariko 5년 전 0

insert는 치우쳐질때마다 이동을 시키는데, 이동의 시간복잡도도 O(lgN)으로 보입니다.

계속 치우쳐지면 O(lg^2N)이 될것같습니다.

kks227 5년 전 0

기본적인 세그먼트 트리를 가지고도 풀 수 있습니다.

이 문제의 키포인트는 세그먼트 트리를 변형시키는 것이 아니고, 광활한 범위의 값들을 어떻게 처리하는가 입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그먼트 응용같은데... 모르겠어요

akane 5년 전 0

yukariko 5년 전 0

yukariko 5년 전 0

kks227 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말