HDU-5249 KPI(STL or 权值线段树)

青旅半醒 2021-11-01 06:38 292阅读 0赞

安利博客：[https://blog.csdn.net/qq\_35776579/article/details/55004134][https_blog.csdn.net_qq_35776579_article_details_55004134]  
[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。  
Input  
有大约100组数据。

每组数据第一行有一个n(1≤n≤10000)，代表服务记录数。

接下来有n行，每一行有3种形式  
“in x”: 代表重要值为x(0≤x≤109)的请求被推进管道。  
“out”: 代表服务拉取了管道头部的请求。  
“query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有m条请求, 我想知道，升序排序后第floor(m/2)+1th  
条请求的重要值.  
为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有"out"和"query"操作。  
Output  
对于每组数据，先输出一行  
Case \#i:  
然后每一次"query”，输出当前管道内重要值的中间值。  
Sample Input  
6  
in 874  
query  
out  
in 24622  
in 12194  
query

Sample Output  
Case \#1:  
874  
24622  
分析：  
扫描线是真的恶心。 所以，晚上只能来做做线段树了。

目的：找到区间第k大值（把找中位数理解为找第k大）。  
单点增加，删除操作。

区间第k大，我们可以在每个结点中增加一个属性num表示这颗子树里面有多少个数。  
if（左子树的个数>=k） 则第k大一定在左子树里面，  
else 则第k大一定在右子树里面（同时k要减去左子树里面数的个数）。

数据范围必离散，离散必二分。每次都这样~~~~

容器可看：[https://blog.csdn.net/henuyh/article/details/86720373][https_blog.csdn.net_henuyh_article_details_86720373]

#include"stdio.h"
    #include"string.h"
    #include"queue"
    #include"algorithm"
    using namespace std;
    
    typedef struct Node
    {
        int l,r;
        int num;
        int val;
    }Node;
    
    int n;
    int oper[10010],b[10010],top;
    Node node[510010];
    
    void push_up(int id)
    {
        node[id].num = node[id << 1].num + node[id << 1 | 1].num;
    }
    void Build_Tree(int id,int l,int r)
    {
        node[id].l = l; node[id].r = r;
        node[id].num = 0;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        Build_Tree(id << 1,l,mid);
        Build_Tree(id << 1 | 1,mid + 1,r);
        push_up(id);
    }
    
    void Update(int id,int x,int val)
    {
        int L = node[id].l;
        int R = node[id].r;
        if(L == R)
        {
            node[id].num += val;
            return ;
        }
        int mid = (L + R) >> 1;
        if(x <= mid) Update(id << 1,x,val);
        else Update(id << 1 | 1,x,val);
        push_up(id);
    }
    
    int Query(int id,int x)
    {
        int l = node[id].l; int r = node[id].r;
        if(l == r) return l;
        int mid = (l + r) >> 1;
        if(node[id << 1].num >= x)
           return Query(id << 1,x);
        else
           return Query(id << 1 | 1,x - node[id << 1].num);
    }
    
    int main()
    {
        int cnt = 1;
        while(~scanf("%d",&n))
        {
            printf("Case #%d:\n",cnt ++);
            char str[10]; top = 0;
            for(int i = 1; i <= n; i ++)
            {
                scanf("%s",str);
                if(str[0] == 'i')  {scanf("%d",&oper[i]); b[++ top] = oper[i];}
                else if(str[0] == 'o') oper[i] = -1;
                else oper[i] = -2;
            }
            sort(b + 1,b + 1 + top);
            top = unique(b + 1,b + 1 + top) - b - 1;
            Build_Tree(1,1,top);
            queue<int> Q;
            for(int i = 1; i <= n; i ++)
            {
                if(oper[i] >= 0)
                {
                    int x = lower_bound(b + 1,b + top + 1,oper[i]) - b;
                    Update(1,x,1);
                    Q.push(oper[i]);
                }
                if(oper[i] == -1)
                    {
                      int x = lower_bound(b + 1,b + top + 1,Q.front()) - b;
                      Q.pop();
                      Update(1,x,-1);
                    }
                if(oper[i] == -2)
                {
                    int m = Q.size() / 2 + 1;
                    int x = Query(1,m);
                    printf("%d\n",b[x]);
                }
            }
        }
    }
    
    /*
    
    */

[https_blog.csdn.net_qq_35776579_article_details_55004134]: https://blog.csdn.net/qq_35776579/article/details/55004134
[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[https_blog.csdn.net_henuyh_article_details_86720373]: https://blog.csdn.net/henuyh/article/details/86720373