当前位置:编程学习 > C/C++ >>

Hdu 4006 The kth great number (数据结构_SBT)

题目大意: 给定n个操作,操作分两种,插入和查询第k大的数。n<=1000000

解题思路:因为本题没有删除操作,所以变得特别简单,只需要维护一个大小为k的小顶堆即可。
   但是如果有删除操作,就变地复杂了,所以用SBT写了这道题,怒写2遍,明天晚上黄金十点半再写三遍,测模版的没什么好说的。

测试数据:
8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

C艹代码:
[cpp] 
#include <stdio.h> 
#include <string.h> 
#define MAX 1000010 
 
 
int n,m; 
struct SBT { 
 
    int left,right,size,key; 
    void Init() { 
 
        left = right = 0; 
        size = 1; 
    } 
}a[MAX]; 
int tot,root; 
 
 
void left_rotate(int &t) { 
 
    int k = a[t].right; 
    a[t].right = a[k].left; 
    a[k].left = t; 
    a[k].size = a[t].size; 
    a[t].size = a[a[t].left].size + a[a[t].right].size + 1; 
    t = k; 

void right_rotate(int &t) { 
 
    int k = a[t].left; 
    a[t].left = a[k].right; 
    a[k].right = t; 
    a[k].size = a[t].size; 
    a[t].size = a[a[t].left].size + a[a[t].right].size + 1; 
    t = k; 

void maintain(int &t,int flag) { 
 
    if (flag == 0) { 
 
        if (a[a[a[t].left].left].size > a[a[t].right].size)  
            right_rotate(t); 
        else if (a[a[a[t].left].right].size > a[a[t].right].size) 
            left_rotate(a[t].left),right_rotate(t); 
        else return; 
    } 
    else { 
 
        if (a[a[a[t].right].right].size > a[a[t].left].size) 
            left_rotate(t); 
        else if (a[a[a[t].right].left].size > a[a[t].left].size) 
            right_rotate(a[t].right),left_rotate(t); 
        else return; 
    } 
    maintain(a[t].left,0); 
    maintain(a[t].right,1); 
    maintain(t,0); 
    maintain(t,1); 

void insert(int &t,int v) { 
 
    if (t == 0) 
        t = ++tot,a[t].Init(),a[t].key = v; 
    else { 
 
        a[t].size++; 
        if (v < a[t].key) 
            insert(a[t].left,v); 
        else insert(a[t].right,v); 
        maintain(t,v>=a[t].key); 
    } 

int del(int &t,int v) { 
 
    if (!t) return 0; 
    a[t].size--; 
 
    if (v == a[t].key || v < a[t].key && !a[t].left 
        || v > a[t].key && !a[t].right) { 
 
        if (a[t].left && a[t].right) { 
 
            int p = del(a[t].left,v+1); 
            a[t].key = a[p].key; 
            return p; 
        } 
        else { 
 
            int p = t; 
            t = a[t].left + a[t].right; 
            return p; 
        } 
    } 
    else return del(v<a[t].key?a[t].left:a[t].right,v); 

int find(int t,int k) { 
 
    if (k <= a[a[t].left].size) 
        return find(a[t].left,k); 
    if (k > a[a[t].left].size + 1) 
        return find(a[t].right,k-a[a[t].left].size-1); 
    return a[t].key; 

 
 
int main() 

    int i,j,k; 
 
 
    while (scanf("%d%d",&n,&m) != EOF) { 
 
        tot = root = 0; 
        char ope[10]; 
        while (n--) { 
 
            scanf("%s",ope); 
            if (ope[0] == 'I') { 
 
                scanf("%d",&k); 
                insert(root,k); 
            } 
            else printf("%d\n",find(root,a[root].size+1-m)); 
        } 
    } 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,