题解 SP3273 【ORDERSET - Order statistic set】

发表于 更新于 阅读次数： Waline：
SP3273 【ORDERSET - Order statistic set】题解。

这题目其实就是个平衡树裸题

那么我们就可以使用平板电视水过去

平板电视代码：

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
#include<cstdio>
#include<ext/pb_ds/assoc_container.hpp>
//pb_ds库内置了红黑树（red-black tree）、伸展树（splay tree）和排序向量树（ordered-vector tree）。
//这些封装好的树都支持插入（insert）、删除（erase）、求kth（find_by_order）、求rank（order_of_key）操作，O(logn)内完成
using namespace std;
using namespace __gnu_pbds;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbt;
//SPOJG++版本稍旧(4.3.2),需要写成null_mapped_type才可以(高级版本可以写null_type)
char in(){
    for(char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch;
}
int main(){
    char c;int x;
    for(int T=read();T--;){
        c=in();x=read();
        if(c=='I')bbt.insert(x);//平衡树：插入
        else if(c=='D')bbt.erase(x);//平衡树：删除
        else if(c=='K'){
            if(x<=bbt.size())
                printf("%d\n",*bbt.find_by_order(x-1));//平衡树，查找
            else puts("invalid");
        }
        else printf("%d\n",bbt.order_of_key(x));//计数
    }
    return 0;
}

然而SPOJ好像并不支持。

没关系，我们手打！

手打平衡树：

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

#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN=200005;
const int INF=0x3f3f3f3f;
struct Treap {
    int tot,root;
    int ch[MAXN][2],key[MAXN],pt[MAXN],size[MAXN];
    Treap() {
        tot=1;
        root=0;
        pt[0]=INF;
        size[0]=0;
    }
    void rotate(int &x,int t) {
        int y=ch[x][t];
        ch[x][t]=ch[y][t^1];
        ch[y][t^1]=x;
        size[y]=size[x];
        size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
        x=y;
    }
    bool insert(int &x,int k) {
        if(!x) {
            x=tot++;
            ch[x][0]=ch[x][1]=0;
            key[x]=k;
            pt[x]=rand();
            size[x]=1;
            return true;
        }
        if(key[x]==k)
            return false;
        int t=key[x]<k;
        if(!insert(ch[x][t],k))
            return false;
        ++size[x];
        if(pt[ch[x][t]]<pt[x])
            rotate(x,t);
        return true;
    }
    bool remove(int &x,int k) {
        if(!x)
            return false;
        if(key[x]!=k) {
            if(!remove(ch[x][key[x]<k],k))
                return false;
            --size[x];
        } else if(!ch[x][0]&&!ch[x][1])
            x=0;
        else if(!ch[x][0])
            x=ch[x][1];
        else if(!ch[x][1])
            x=ch[x][0];
        else {
            rotate(x,pt[ch[x][0]]>pt[ch[x][1]]);
            if(!remove(ch[x][key[x]<k],k))
                return false;
            --size[x];
        }
        return true;
    }
    void insert(int k) {
        insert(root,k);
    }
    void remove(int k) {
        remove(root,k);
    }
    int getKth(int k) {
        int x=root;
        while(size[ch[x][0]]+1!=k)
            if(k<size[ch[x][0]]+1)
                x=ch[x][0];
            else {
                k-=size[ch[x][0]]+1;
                x=ch[x][1];
            }
        return key[x];
    }
    int getRank(int k) {
        int ret=0,x=root;
        while(x)
            if(k<key[x])
                x=ch[x][0];
            else {
                ret+=size[ch[x][0]]+1;
                x=ch[x][1];
            }
        return ret;
    }
} treap;
int main() {
    int n,num;
    char c;
    scanf("%d",&n);
    while(n--) {
        scanf(" %c%d",&c,&num);
        switch(c) {
        case 'I':
            treap.insert(num);
            break;
        case 'D':
            treap.remove(num);
            break;
        case 'K':
            num<=treap.size[treap.root]?printf("%d\n",treap.getKth(num)):puts("invalid");
            break;
        case 'C':
            printf("%d\n",treap.getRank(num-1));
            break;
        }
    }
}