设为首页 加入收藏

TOP

acdreamoj1108（The kth number）
2015-07-24 05:53:02 来源: 作者: 【大 中 小】 浏览:4次
Tags：acdreamoj1108 The kth number

?

题意:n个数的数列，m次查询某个区间出现次数第k多的数出现的次数。n，m<=100000

?

解法：这个因为是离线的所以可以先统一处理，然后再输出。可以维护一个left和right指针，pre，pre[i]表示此时区间内出现次数大于等于i的数的种类。为了减少复杂度，关键是left和right的移动方式，即查询区间如何排序，如果紧靠区间左端点排序，那么右端点每次一定最大回是n，如果按照右端点排序，左端点每次一定最大是n。这里有个很好的处理办法，就是模糊排序，先左端点非严格排序，即除以sqrt(n)再排序，这样复杂度最大是n*sqrt(n)

?

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               //freopen (in.txt , r , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const int INF=1e9+7; int num[Max]; int help[Max]; int r[Max]; int l[Max]; int k[Max]; int pre[Max]; int cnt[Max]; int tool; bool cmp(int i,int j) { if(l[i]/tool==l[j]/tool&&r[i]!=r[j]) return r[i]
              
               =t) l=middle+1; else r=middle-1; } return l-1; } int main() { int t; cin>>t; while(t--) { scanf(%d%d,&n,&m); tool=sqrt(n); for(int i=0; i
               
                
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：First Missing Positive 下一篇：局部静态变量的多线程问题

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: