[ BOJ ] 6758 : Tourney ( PLATINUM 3 ) / C

문제

Don Cherry has been hired to run 24-hour coverage of a series of single-elimination, bracket-style, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between 1 and 1 000 000 000. In every head-to-head match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guaranteed that, at any time, the skill levels of all competitors are distinct, so there are no ties.

There are 2N (1 ≤ N ≤ 20) competitor positions in the tourney tree, numbered 1, 2, . . . , 2N from left to right. In the first round, competitors 1 and 2 face off in a furniture disassembly race, as do competitors 3 and 4, etc. In each subsequent round, the winners of the first two matches from the previous round compete, as do the winners of the following two, etc. After N rounds, a single winner remains. For example, when N = 2, the tourney tree looks like this:

 

where A represents the winner of the match between competitors 1 and 2, B represents the winner of the match between competitors 3 and 4, and C represents the winner of the match between A and B. The winner of this tourney is C.

Because of sponsorship contracts, some competitors will be replaced over time. After any new person comes in, a new tourney is held.

In order to help Don Cherry, you must write a program to compute certain tourney statistics at various points in time, given a sequence of M (1 ≤ M ≤ 1 000 000) commands — see the input format below.

입력

The first line of input contains two integers, N (1 ≤ N ≤ 20) and M (1 ≤ M ≤ 1 000 000), separated by one space.

The next 2N lines, for i from 1 to 2N, each contain one integer Si, indicating the skill level of the initial competitor at position i in the tourney tree.

Each of the following M lines will be a command in one of three formats:

• “R i S” means that the competitor at position i is removed, and replaced with a new one with skill level S. A new tourney is then held.
• “W” means that your program should determine who won the current tourney. Print out the position i (between 1 and 2N) of this competitor.
• “S i” means that your program should print out the number of rounds that the competitor at position i won in the current tourney.

출력

For each “W” or “S i” command in the input, print out the corresponding integer on a line by itself.

풀이 과정

세그먼트 트리를 이용하였으며, 트리를 처음 만들때 이긴 라운드 수를 먼저 계산해 놓고 업데이트 할 때마다 원래 이긴 사람의 이긴 라운드 수를 1 제거하고 새롭게 이긴 사람의 이긴 라운드 수를 1 추가하는 방식으로 구현하였다.

#include <stdio.h>
#include <math.h>
#define SIZE 1100000
typedef long long LL;

LL arr[SIZE];
int win_count[SIZE]= {0,};
typedef struct _Node {
    //LL now_skill;
    LL now_numb;
    int already_wins;
} Node;
Node tree[SIZE * 4];

Node merge_init(Node a, Node b) {
    Node tmp;
    if (arr[a.now_numb] >= arr[b.now_numb]) {
        tmp.now_numb = a.now_numb;
    }
    else {
        tmp.now_numb = b.now_numb;
    }

    tmp.already_wins = 1;
    win_count[tmp.now_numb] += 1;
    return tmp;
}
Node merge(Node o, Node a, Node b) {
    win_count[o.now_numb] -= 1;

    Node tmp;
    if (arr[a.now_numb] >= arr[b.now_numb]) {
        tmp.now_numb = a.now_numb;
    }
    else {
        tmp.now_numb = b.now_numb;
    }

    win_count[tmp.now_numb] += 1;
    return tmp;
}

void init(int start, int end, int idx) {
    if (start == end) {
        tree[idx].now_numb = start;
        return;
    }

    int mid = (start + end) / 2;
    init(start, mid, idx * 2);
    init(mid + 1, end, idx * 2 + 1);
    tree[idx] = merge_init(tree[idx * 2], tree[idx * 2 + 1]);
}

void update(int start, int end, int idx, int what, LL value) {
    if (what < start || end < what) return;
    if (start == end) {
        arr[start] = value;
        return;
    }

    int mid = (start + end) / 2;
    update(start, mid, idx * 2, what, value);
    update(mid + 1, end, idx * 2 + 1, what, value);
    tree[idx] = merge(tree[idx], tree[idx * 2], tree[idx * 2 + 1]);
}

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    int last = (int)pow(2, n) - 1;

    for (int i = 0; i < last + 1; i++) {
        scanf("%lld", &arr[i]);
    }
    init(0, last, 1);
    
    for (int i = 0; i < m; i++) {
        getchar();
        char mode;
        scanf("%c", &mode);

        if (mode == 'R') {
            int a;
            LL b;
            scanf("%d %lld", &a, &b);
            update(0, last, 1, a - 1, b);
        }
        else if (mode == 'W') {
            printf("%d\n", tree[1].now_numb + 1);
        }
        else if (mode == 'S') {
            int a;
            scanf("%d", &a);
            printf("%d\n", win_count[a - 1]);
        }
    }

    return 0;
}