【转载】【树状数组区间第K大/小】

时间:2022-09-17 22:29:52

原帖:http://www.cnblogs.com/zgmf_x20a/archive/2008/11/15/1334109.html

回顾树状数组的定义,注意到有如下两条性质:
一,c[ans]=sum of A[ans-lowbit(ans)+1 ... ans];
二,当ans=2^k时,
 c[ans]=sum of A[1 ... ans];

下面说明findK(k)如何运作:
1,设置边界条件ans,ans'<maxn且cnt<=k;
2,初始化cnt=c[ans],其中ans=2^k且k为满足边界条件的最大整数;
3,找到满足边界条件的最大的ans'使得ans'-lowbit(ans')=ans,即ans'满足c[ans']=A[ans+1 .. ans'](根据性质一),只要将c[ans']累加到cnt中(此时cnt=sum of A[1 ... ans'],根据性质二),cnt便可以作为k的逼近值;
4,重复第3步直到cnt已无法再逼近k,此时ans刚好比解小1,返回ans+1。

因此findk(k)的实质就是二分逼近

 /**********************************

 树状数组实现查找K小的元素

                   经典。

 限制:数据范围在1<<20 以内

 ***********************************/

 #include <iostream>

 using namespace std;

 #define maxn 1<<20

 int n,k;

 int c[maxn];

 int lowbit(int x){

     return x&-x;

 }

 void insert(int x,int t){

        while(x<maxn){

           c[x]+=t;

           x+=lowbit(x);    

        }

 }

 int find(int k){

     int cnt=,ans=;

     for(int i=;i>=;i--){

         ans+=(<<i);

         if(ans>=maxn || cnt+c[ans]>=k)ans-=(<<i);

         else cnt+=c[ans];

     }

     return ans+;

 }

 void input(){

        memset(c,,sizeof(c));

        int t;

        scanf("%d%d",&n,&k);

        for(int i=;i<n;i++){    

             scanf("%d",&t);

             insert(t,);

        }

        printf("%d\n",find(k));

 }

 int main(){

     int cases;

     scanf("%d",&cases);

     while(cases--){

         input();

     }

     return ;

 }

【转载】【树状数组区间第K大/小】的更多相关文章

  1. Permutation UVA - 11525(值域树状数组,树状数组区间第k大(离线),log方,log)(值域线段树第k大)

    Permutation UVA - 11525 看康托展开 题目给出的式子(n=s[1]*(k-1)!+s[2]*(k-2)!+...+s[k]*0!)非常像逆康托展开(将n个数的所有排列按字典序排序 ...

  2. HDU 5249 离线树状数组求第k大&plus;离散化

    KPI Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...

  3. poj 2985 The k-th Largest Group 树状数组求第K大

    The k-th Largest Group Time Limit: 2000MS   Memory Limit: 131072K Total Submissions: 8353   Accepted ...

  4. hdu5592&sol;BestCoder Round &num;65 树状数组寻找第K大

    ZYB's Premutation    Memory Limit: 131072/131072 K (Java/Others) 问题描述 ZYBZYB有一个排列PP,但他只记得PP中每个前缀区间的逆 ...

  5. POJ2985 The k-th Largest Group&lbrack;树状数组求第k大值&plus;并查集&vert;&vert;treap&plus;并查集&rsqb;

    The k-th Largest Group Time Limit: 2000MS   Memory Limit: 131072K Total Submissions: 8807   Accepted ...

  6. 树状数组求第K大(From CLJ)

    ; <<log2[n];p;p>>=) if(a[ret+p]<=kth) kth-=a[ret+=p]; return ret;

  7. 【bzoj3110】&lbrack;Zjoi2013&rsqb;K大数查询 整体二分&plus;树状数组区间修改

    题目描述 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c.如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数 ...

  8. 【bzoj5173】&lbrack;Jsoi2014&rsqb;矩形并 扫描线&plus;二维树状数组区间修改区间查询

    题目描述 JYY有N个平面坐标系中的矩形.每一个矩形的底边都平行于X轴,侧边平行于Y轴.第i个矩形的左下角坐标为(Xi,Yi),底边长为Ai,侧边长为Bi.现在JYY打算从这N个矩形中,随机选出两个不 ...

  9. 【bzoj3132】上帝造题的七分钟 二维树状数组区间修改区间查询

    题目描述 “第一分钟,X说,要有矩阵,于是便有了一个里面写满了0的n×m矩阵. 第二分钟,L说,要能修改,于是便有了将左上角为(a,b),右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作. ...

随机推荐

  1. 不知道数据库中表的列类型的前提下&comma;使用JDBC正确的取出数据

    概要: 使用jdbc 如果在不知道表结构的情况下,如何读出表信息? 使用ResultSetMetaData; 然后使用getColumnType 获取column 类型 使用getColumnName ...

  2. 424 - Integer Inquiry

     Integer Inquiry  One of the first users of BIT's new supercomputer was Chip Diller. He extended his ...

  3. mysql函数操作&lpar;5&rpar;

    <?php try{ $dbh = new PDO('mysql:dbname=testdb;host=localhost', 'mysql_user', 'mysql_pwd'); }catc ...

  4. 【转】Android数字证书

    Android数字证书的作用是非常重要的.Android操作系统每一个应用程序的安装都需要经过这一数字证书的签名. Android手机操作系统作为一款比较流行的开源系统在手机领域占据着举足轻重的地位. ...

  5. Apache 与tomcat区别

    Apache与Tomcat有什么关系和区别 经常在用apache和tomcat等这些服务器,可是总感觉还是不清楚他们之间有什么关系,在用tomcat的时候总出现apache,总感到迷惑,到底谁是主谁是 ...

  6. &lbrack;lua&rsqb; 你所不知道的lua nil值在可变参数函数中怎么处理!

    在lua中, 问题1:如果你在可变参数...中传入若干个参数,其中有的参数要带nil,这时怎么解决呢?(比如local function _test(...) end    _test(1, nil, ...

  7. 最新Windows下Redis集群

    实现简单的Windows下Redis集群配置,以下是配置过程中出现的几个问题: [1]逐个启动7001 7002 7003 7004 7005 7006节点时,出现createing server T ...

  8. c&num;根据文件路径启动进程

    //根据文件路径启动进程 private static void StartProcessByFilePath(string path) { Process p = new System.Diagno ...

  9. Android Tools 开发工具库开源项目总结

    在Android开发中,我们不免会遇到使用一些工具库来简化我们的工具代码的编写,以下是本人之前star的开源项目,供大家参考: 一.android_testsuite 项目地址:https://git ...

  10. 使用WPF动态显示CPU使用率

    基于WPF的开源图表控件有很多,大多数都是静态图表,如果需要绘制CPU使用率这样的动态数据就显得力不从心,微软开源的DynamicDataDisplay控件弥补了这个不足,为了做个备忘,我用它来实时绘 ...