algorithms/2201_RMQ.cpp at master · roles/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
 * 笛卡尔树，用RMQ的方法去解，在POJ上RE
 *
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

#define MAXVAL 30000

struct node {
    int a, k;
    int idx;
    int p, lc, rc;
};

static node T[50001];
static int a2pos[MAXVAL*2+1];
static int rmq[50001][17];

int cmp_node_by_k(const void *pa, const void *pb){
    node* a = (node*)pa;
    node* b = (node*)pb;

    if(a->k < b->k){
        return -1;
    }else{
        return 1;
    }
}

int cmp_node_by_idx(const void *pa, const void *pb){
    node* a = (node*)pa;
    node* b = (node*)pb;

    if(a->idx < b->idx){
        return -1;
    }else{
        return 1;
    }
}

int query_rmq(int b, int e){
    int lg = (int)(log(1.0 * (e-b+1)) / log(2.0));
    return min(rmq[b][lg], rmq[e-(1<<lg)+1][lg]);
}

int build_tree(int b, int e, int root){
    if(b == e){
        T[b].p = root;
        T[b].lc = 0;
        T[b].rc = 0;
        return b;
    }
    int min_val = query_rmq(b, e);
    int min_idx = a2pos[min_val];
    T[min_idx].p = root;

    int lc_idx, rc_idx;
    if(b != min_idx){
        lc_idx = build_tree(b, min_idx-1, T[min_idx].idx);
        T[min_idx].lc = T[lc_idx].idx;
    }else{
        T[min_idx].lc = 0;
    }

    if(e != min_idx){
        rc_idx = build_tree(min_idx+1, e, T[min_idx].idx);
        T[min_idx].rc = T[rc_idx].idx;
    }else{
        T[min_idx].rc = 0;
    }

    return min_idx;
}

int main(){
    int N;

    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        scanf("%d%d", &T[i].k, &T[i].a);
        T[i].idx = i+1;
        T[i].p = T[i].lc = T[i].rc = 0;
    }

    qsort(T, N, sizeof(node), cmp_node_by_k);

    for(int i = 0; i < N; i++){
        rmq[i][0] = T[i].a;
        a2pos[T[i].a] = i;
    }

    int lg = (int)(log(N * 1.0) / log(2.0));

    for(int j = 1; j <= lg; j++){
        for(int i = 0; i <= N - (1<<j); i++){
            rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }

    build_tree(0, N-1, 0);

    qsort(T, N, sizeof(node), cmp_node_by_idx);

    cout << "YES" << endl;
    for(int i = 0; i < N; i++)
        cout << T[i].p << " " << T[i].lc << " " << T[i].rc << endl;

    return 0;
}