Chenfan Blog

Do cool things that matter.

0%

HDU 4006 The kth great number 优先队列、平衡树模板题（SBT）

Posted on Edited on In

The kth great number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)

Problem Description

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.

Input

There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an “ I” followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a “Q”, then you need to output the kth great number.

Output

The output consists of one integer representing the largest number of islands that all lie on one line.

Sample Input

3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

Sample Output

1
2
3

Hint

Xiao Ming won’t ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=<k<=n<=1000000).

题意

给出一系列操作：

1.记录一个数；2.求第k小的数

分析

解法一、优先队列

题目每次询问的只是其中的一个数，这种情况下用一个堆来维护所有数的集合即可。

而且本题的k是一个固定值，因此只需要一个小根堆即可；若k不是一个固定值，则需要一个小根堆配合大根堆共同完成。

堆可以用STL中的优先队列来代替。

创建一个小根堆并向其加入数据，若堆中的数量大于k则弹出堆顶元素，始终保持整个堆中只有k个元素。遇到询问时，读取堆顶元素。

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
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU4006
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

struct cmp
{
    bool operator()(int x,int y)
    {
        return x>y;
    }
};

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("std.txt","w",stdout);

    int n,k;

    while(scanf("%d%d",&n,&k)==2)
    {
        priority_queue<int,vector<int>,cmp>q;
        char c;
        for (int i=1;i<=n;i++)
        {
            c=getchar();
            while(c!='I'&&c!='Q')
            {
                c=getchar();
            }
            if (c=='I')
            {
                int now;
                scanf("%d",&now);
                q.push(now);
                if (q.size()>k) q.pop();
            } else
            {
                printf("%d\n",q.top());
            }
        }
    }

    return 0;
}

解法二、平衡树

本题可作为平衡树模板题，虽然因为有点大材小用内存占用比较大，而且时间上并没有太大优势。

动态维护一棵平衡树，求k大值。

以下采用Size Balanced Tree完成：

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
138
139
140
141
142
143
144
145
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU4006_SBT
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 1000010

typedef struct sbtnod
{
    int key,left,right,size;
} sbtnode;
int sbttail,sbt;

sbtnode tree[MAXN];

void rrotate(int& t)
{
    int k=tree[t].left;
    if (!k) return ;
    tree[t].left=tree[k].right;
    tree[k].right=t;
    tree[k].size=tree[t].size;
    tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+1;
    t=k;
}

void lrotate(int& t)
{
    int k=tree[t].right;
    if (!k) return ;
    tree[t].right=tree[k].left;
    tree[k].left=t;
    tree[k].size=tree[t].size;
    tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+1;
    t=k;
}

void maintain(int& t,bool flag)
{
    if (!t) return ;
    if (!flag)
        if (tree[tree[tree[t].left].left].size>tree[tree[t].right].size) rrotate(t);
        else if (tree[tree[tree[t].left].right].size>tree[tree[t].right].size) 
        {
            lrotate(tree[t].left);
            rrotate(t);
        } else return ;
    else
        if (tree[tree[tree[t].right].right].size>tree[tree[t].left].size) lrotate(t);
        else if (tree[tree[tree[t].right].left].size>tree[tree[t].left].size)
        {
            rrotate(tree[t].right);
            lrotate(t);
        } else return ;
    
    maintain(tree[t].left,false);
    maintain(tree[t].right,true);
    maintain(t,false);
    maintain(t,true);
}

void insert(int& t,int v)
{
    if (!t)
    {
        sbttail++;
        tree[sbttail].key=v;
        tree[sbttail].size=1;
        t=sbttail;
    } else 
    {
        tree[t].size++;
        if (v<tree[t].key) insert(tree[t].left,v);
        else insert(tree[t].right,v);
        maintain(t,v>=tree[t].key);
    }
}

int del(int& t,int v)
{
    int ret;
    tree[t].size--;
    if (v==tree[t].key||(v<tree[t].key&&tree[t].left==0)||(v>tree[t].key&&tree[t].right==0))
    {
        ret=tree[t].key;
        if (tree[t].left==0||tree[t].right==0) t=tree[t].left+tree[t].right;//
        else tree[t].key=del(tree[t].left,tree[t].key+1);
    } else 
    {
        if (v<tree[t].key) ret=del(tree[t].left,v);
        else ret=del(tree[t].right,v);
    }
    return ret;
}

int select(int t,int k)
{
    if (k==tree[tree[t].left].size+1) return t;
    if (k<=tree[tree[t].left].size) return select(tree[t].left,k);
    else return select(tree[t].right,k-1-tree[tree[t].left].size);
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("st.txt","w",stdout);

    int n,k;
    while(scanf("%d%d",&n,&k)==2)
    {
        memset(tree,0,sizeof(tree));
        sbttail=0;
        sbt=0;

        char c;
        for (int i=1;i<=n;i++)
        {
            c=getchar();
            while(c!='I'&&c!='Q')
            {
                c=getchar();
            }
            int now;
            if (c=='I')
            {
                scanf("%d",&now);
                insert(sbt,now);
            } else 
            {
                now=select(sbt,sbttail-k+1);
                printf("%d\n",tree[now].key);
            }
        }
    }

    return 0;
}
Related Posts