P5854 【模板】笛卡尔树

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXn = 1e7;

struct Node {
    LL p;
    LL ls;
    LL rs;
};

Node node[MAXn + 10];
LL n;
LL nowid;
LL stk[MAXn + 10];
LL top;

inline LL read() {
    register char c;
    for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());
    register bool f = c == '-';
    register LL s = f ? 0 : c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {
        s = (s << 3) + (s << 1) + c - '0';
    }
    return f ? -s : s;
}

void insert(LL p) {
    nowid++;
    node[nowid].p = p;
    LL newtop = top;	
    while (newtop && node[stk[newtop]].p > node[nowid].p) 
        newtop--;
    if (newtop) 
        node[stk[newtop]].rs = nowid; 
    if (newtop < top) 
        node[nowid].ls = stk[newtop + 1];
    stk[++newtop] = nowid;
    top = newtop;
}

int main() {
    n = read();
    LL p;
    for (LL i = 0; i < n; i++) {
        p = read();
        insert(p);/*这里 insert 的数字的值(p)没有单调的要求，
							但数字的标号(id)要求单增，若不单增要先排序*/
    }
    for (LL i = 1; i <= n; i++) {
        printf("%lld %lld %lld\n", node[i].p, node[i].ls, node[i].rs);
    }
}