博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
[主席树]K-th Number
阅读量：4563 次
发布时间：2019-06-08

本文共 2059 字，大约阅读时间需要 6 分钟。

正确解法：

分块（超时）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 using namespace std;12 typedef long long ll;13 const int inf=0x7fffffff;14 const int N=100000+100;15 const int M=5000+10;16 const double PI=acos(-1.0);17 int B=1000;18 int n,m,a[N],num[N];19 int I,J,K;20 vector
                
                  buck[N/1000];21 int main()22 {23 scanf("%d %d",&n,&m);24 for(int i=0;i
                 
                  >1;40 int x=num[md];41 int tl=I-1,tr=J,c=0;42 while(tl=K) ub=md-1;51 else lb=md+1;52 }53 printf("%d\n",num[lb]);54 }55 56 57 return 0;58 }
View Code

主席树：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 using namespace std;12 typedef long long ll;13 const int inf=0x7fffffff;14 const int N=100000+100;15 const int M=5000+10;16 const double PI=acos(-1.0);17 int n,m,a[N],num[N];18 int I,J,K;19 vector
                
                 buck[(1<<18)-1];20 void build(int rt,int l,int r)21 {22 if(l==r)23 {24 buck[rt].push_back(a[l]);25 return ;26 }27 int m= l+r >>1;28 build(rt<<1,l,m);29 build(rt<<1|1,m+1,r);30 buck[rt].resize(r-l+1);31 merge(buck[rt<<1].begin(),buck[rt<<1].end(),buck[rt<<1|1].begin(),buck[rt<<1|1].end(),buck[rt].begin());32 }33 int query(int L,int R,int x,int rt,int l,int r)34 {35 if(R
                 
                  
                   >1;40 ans+=query(L,R,x,rt<<1,l,m);41 ans+=query(L,R,x,rt<<1|1,m+1,r);42 return ans;43 }44 int main()45 {46 scanf("%d %d",&n,&m);47 for(int i=1;i<=n;i++)48 {49 scanf("%d",&a[i]);50 num[i]=a[i];51 }52 sort(num+1,num+1+n);53 build(1,1,n);54 while(m--)55 {56 scanf("%d %d %d",&I,&J,&K);57 //J++;58 int lb=1,ub=n;59 while(lb<=ub)60 {61 int md=lb+ub >>1;62 int c=query(I,J,num[md],1,1,n);63 if(c>=K) ub=md-1;64 else lb=md+1;65 }66 printf("%d\n",num[lb]);67 }68 69 return 0;70 }
View Code

 

转载于:https://www.cnblogs.com/Kaike/p/10808572.html

你可能感兴趣的文章
RTP协议分析
查看>>
怎么洗掉衣服上的水粉颜料、丙烯颜料、水彩颜料、油画颜料
查看>>
linux常用命令总结
查看>>
数值计算中的上溢和下溢
查看>>
Jenkins+SVN+Maven+shell 自动化部署实践
查看>>
看见一个程序员敲键盘的速度不快
查看>>
如何轻松培养孩子流利说英语
查看>>
Matlab 重命名
查看>>
js call
查看>>
1.7 单例模式
查看>>
.net三步配置错误页面，让你的站点远离不和谐的页面
查看>>
编程学习要讲究效率和经验
查看>>
关于hibernate中多对多关系
查看>>
InstallShield12豪华版破解版下载|InstallShield下载|软件打包工具
查看>>
魔兽RPG仿魔兽世界：基尔加丹的末日V1.0
查看>>
V8引擎实现标准ECMA-262（三）
查看>>
前端面试题集锦（一）
查看>>
php下载文件的代码示例
查看>>
js鼠标及对象坐标控制属性详细解析
查看>>
Java封装servlet发送请求（二）
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-10-17 19:24:13   当前IP: 18.188.81.3   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我