数据结构(三)#

1
struct TRE
2
{
3
    int ls, rs, sum;
4
} tre[N*40];
5
int root[N*40], cnt;
6

7
int build(int l, int r)
8
{
9
    int k = ++cnt;
10
    tre[k] = {0};
11
    if (l < r)
12
    {
13
        int mid = (l + r) >> 1;
14
        tre[k].l = build(l, mid);
15
        tre[k].r = build(mid + 1, r);
16
    }
17
    return k;
18
}
19

20
int change(int lst, int l, int r, int op)
21
{
22
    int k = ++cnt;
23
    tre[k] = tre[lst];
24
    tre[k].sum++;
25
    if (l < r)
26
    {
27
        int mid = (l + r) >> 1;
28
        if (mid >= op) tre[k].ls = change(tre[lst].ls, l, mid, op);
29
        else tre[k].rs = change(tre[lst].rs, mid + 1, r, op);
30
    }
31
    return k;
32
}
33

34
int query(int a1, int a2, int l, int r, int k)
35
{
36
    if (l == r) return l;
37
    int xx = tre[tre[a2].ls].sum - tre[tre[a1].ls].sum;
38

39
    int mid = (l + r) >> 1;
40
    if (xx >= k) return query(tre[a1].ls, tre[a2].ls, l, mid, k);
41
    else return query(tre[a1].rs, tre[a2].rs, mid + 1, r, k - xx);
42
}
43

44

45

46
//打印      版本   范围
47
void nszka(int k,int l,int r)
48
{
49
    auto []=tre[k];
50
//输出
51
    if(l==r)
52
    {
53
        //操作
54
        return ;
55
    }
56
    int mid=(l+r)>>1;
57
    nszka(tre[k].ls,l,mid);
58
    nszka(tre[k].rs,mid+1,r);
59
}