yuzh的博客

❤ ECUST ❤

0%

P5076 【深基16.例7】普通二叉树（简化版）

发表于 更新于 Valine：

题目

题目

不多赘述，直接看代码吧

代码

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

int n,m;

struct Node 
{
    int l,r,sum;//l,r为左右节点的号码，sum为该节点作为子树的数量
    int val,cnt;//值，出现次数
}ltt[maxn];

int lst=0,root; //lst最后一个节点的位置，控制ltt，root为根（ltt的位置，开始时不存在）

//预定义宏，懒人专用。
//ltt中的x随着ls中的x变化而变化
#define ls(x) ltt[x].l
#define rs(x) ltt[x].r

void up(Node &f,Node ls,Node rs)//insert后的操作（提升操作）
{
    f.sum=f.cnt+ls.sum+rs.sum;//重复次数加上左右节点的数值
}

void insert(int &p,int x)
{
    //动态开点（点为0，直接开点）
    if(!p)//节点编号为0
    {
        p=++lst;//root=+lst
        ltt[p].val=x; ltt[p].cnt=1; ltt[p].sum=1;
        return;
    }
    if(ltt[p].val==x)//重复情况，数值加一
    {
        ltt[p].cnt++; ltt[p].sum++;
        return;
    }
    if(ltt[p].val<x)//要插入的点比这个点的数值要大
    {
        insert(rs(p),x);//向右跑
    }
    else//相反后同上
    {
        insert(ls(p),x);
    }
    up(ltt[p],ltt[ls(p)],ltt[rs(p)]);//IMPORTANT提升操作
}

int findth(int p,int x)//查看某一个点(x)的排名
{
    if(!p) return 1;//p不存在（空节点），排名为一
    int cc=ltt[ls(p)].sum;//查找p节点的左子树的数量
    if(ltt[p].val==x)//节点中的值和x点相同
    {
        return cc+1;//比p小的所有数的数量+1
    }
    if(ltt[p].val>x)//节点中的值比x点大（向左子树跑）
    {
        return findth(ls(p),x);
    }
    else//节点中的值比x点小（向右子树跑）
    {
        return findth(rs(p),x)+cc+ltt[p].cnt;
    }
}

int findkth(int p,int k)//查找k点的排名（第k大的数字）
{
    if(!p) return p;
    int cc=ltt[ls(p)].sum;
    if(cc>=k) return findkth(ls(p),k);
    else if(cc<k && cc+ltt[p].cnt>=k) return p;
    else return findkth(rs(p),k-cc-ltt[p].cnt);
}

int pre(int p,int x,int ans)//前驱
{
    if(!p) return ans;
    if(ltt[p].val>=x)
    {
        return pre(ls(p),x,ans);
    }
    else
    {
        return pre(rs(p),x,max(ans,ltt[p].val));
    }
}

int nxt(int p,int x,int ans)//后继
{
    if(!p) return ans;
    if(ltt[p].val<=x)
    {
        return nxt(rs(p),x,ans);
    }
    else
    {
        return nxt(ls(p),x,min(ans,ltt[p].val));
    }
}

int main()
{
    //插入无限小和无限大
    insert(root,-0x7fffffff);
    insert(root,0x7fffffff);
    cin>>n;
    for(int i=1,a,b;i<=n;i++)
    {
        cin>>a>>b;
        if(a==1)
        {
            cout<<findth(root,b)-1<<endl;
        }
        else if(a==2)
        {
            cout<<ltt[findkth(root,b+1)].val<<endl;
        }
        else if(a==3)
        {
            int ans=pre(root,b,-0x7fffffff);
            cout<<ans<<endl;
        }
        else if(a==4)
        {
            int ans=nxt(root,b,0x7fffffff);
            cout<<ans<<endl;
        }
        else if(a==5)
        {
            insert(root,b);//从根节点开始插入b
        }
    }
    return 0;
}

如上，本题较为复杂。但是要是仔细看看的话，其实难度也不大，就是要码的字实在是太多了QAQ