글 읽기 - 세그먼트 트리 알고리즘 점검.

amatuer789 5년 전 1

TC를 통해서, 오류가 있다는 것은 확인했습니다만, 어느 부분이 틀린지 잘모르겠습니다.

세그트리 알고리즘에 틀린 부분 있는지 확인 부탁드립니다.

(알고리즘에서 지적해 주셔도 감사하겠습니다.)

n+m 크기의 leaf를 가지는 seg 트리를 선언
선택한 disk를 n+i로 Index설정하여, search(현 Index+1, max Index) 를 반복합니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 524300
using namespace std;
int t, n, m, num, node_idx;
int tree[MAX], I[100001];
int search(int a, int b){
    int ret = 0;
    while(a<=b){
        if(a&1) ret += tree[a++];
        if(~b&1) ret += tree[b--];
        a >>= 1, b >>= 1;
    }
    return ret;
}
void update(int idx, int diff){
    while(idx>0){
        tree[idx] += diff;
        idx >>= 1;
    }
}
int main(){
    int i, j;
    scanf("%d", &t);
    while(t--){
        memset(&tree, 0, sizeof(tree));
        memset(&I, 0, sizeof(I));
        scanf("%d%d", &n, &m);
        node_idx = 1<<((int)ceil(log2(n<<1)));
        node_idx--;
        for(i = 1; i <= n; i++){
            I[i] = n-i+1;    
            update(node_idx+i, 1);
        }
        for(i = 0; i < m; i++){
            scanf("%d", &num);
            printf("%d ", search(node_idx+I[num]+1, node_idx+n+i));
            update(node_idx+I[num],-1);
            I[num] = n+i+1;
            update(node_idx+I[num], 1);
        }
        printf("\n");
    }
}

amatuer789 5년 전 0

(참고)트리 크기 초기화 실수.

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

문제

문제

출처

ICPC

세그먼트 트리 알고리즘 점검.

amatuer789 5년 전 1

amatuer789 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말