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

7 43 1 -4 2 8 -1000 21 2 6 6 

3312

话说一看到区间k大就想到了平衡树 可惜本蒟蒻不会treap等等树 害的我都想去学了。。。

然后就写模拟了

名其曰”滑动数组“ 。。。

二分插入位置 后面的都向后挪1个位置 插入这个数

查询直接输出第k个就是第k小

然后可以过30

同学有写每次插入到末尾然后sort的 可以得40/50

还有写multiset的 好像可以40/50

大神直接上平衡树秒杀了蒟蒻们。。。

另一位大神两个堆秒杀了蒟蒻们。。。

本蒟蒻感觉两个堆还是有参考意义的

还可以用双堆求中位数

先说一下求中位数吧   一串数s1,s2.....sn  首先中位数mid是s1

一个小根堆  一个大根堆

从s2向后 若s>mid 放到小根堆中

否则放入大根堆

若两堆内元素相差大于2时 将m放入元素少的堆中 从元素多的堆中取一个 为新的中位数

若最后两堆元素相同 中位数为mid

否则为mid和 堆中元素多的那个堆的堆顶

然后再说一下这个题

看到双堆求中位数后 我想到了用mid维护第k小

一个大根堆ql 一个小根堆qr

首先mid=s1

从s2向后

若s比mid小 放入ql中 否则放入qr中

若ql中元素个数>k-1     mid入qr   mid=ql的堆顶 ql弹出堆顶

查询时  若ql中元素不足k-1个 mid入ql  mid=qr的堆顶 qr弹出堆顶

即严格让ql中数小于mid 个数=k-1 此时mid为第k小的数

不会手打heap 只能priority_queue...

还要注意优先队列的greater和less

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;priority_queue
       
        
         ,less
         
           >ql;priority_queue
          
           
            ,greater
            
              >qr;int l,r,mid;int m,n,a,b,c;int ask;int s[200022];int main(){ freopen("blackbox.in","r",stdin); freopen("blackbox.out","w",stdout); scanf("%d%d",&m,&n); for(a=1;a<=m;a++)scanf("%d",&s[a]); mid=s[1]; b=2; for(a=1;a<=n;a++) { scanf("%d",&ask); for(b;b<=ask;b++) { if(s[b]>mid) { qr.push(s[b]); } else { qr.push(mid); ql.push(s[b]); mid=ql.top(); ql.pop(); } } while(l
            
           
          
         
        
       
      
     
    
   

当时又憨脸了

首先可以用线段树支持一下几个操作

1.给出x，使f[x]+1

2.求

i<=x-1                       i<=x

    Σ         f[i]<k   且     Σ     f[i]>=k          时的x

   i=1                          i=1

这个题就是这样

离散化后200000个点 用一个线段树支持上面的操作 然后就可以了。。。

太神奇了。。。

离散化是自己yy的 不知道对不对。。。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=200022;int sumv[lim<<2],m,n,a,b,c,ask;struct self{int x,y;}s[lim];     //s[x]=y;int transfor[lim],hash[lim],pm;         //hash[离散后数值]=离散前下标   transfor[离散前下标]=离散后数值 int cmp(self a1,self a2){if(a1.y==a2.y)return a1.x
       
        >1;    if(i<=mid)add(o<<1,l,mid,i);    else add(o<<1|1,mid+1,r,i);    pushup(o);}int query(int o,int l,int r,int i){    if(l==r)return l;    int mid=(l+r)>>1;    int ret=0;    if(i>sumv[o<<1])    ret=query(o<<1|1,mid+1,r,i-sumv[o<<1]);    else ret=query(o<<1,l,mid,i);    return ret;}int main(){    freopen("blackbox.in","r",stdin);    freopen("blackbox.out","w",stdout);    scanf("%d%d",&m,&n);    for(a=1;a<=m;a++)    {        scanf("%d",&s[a].y);        s[a].x=a;    }        sort(s+1,s+m+1,cmp);        for(a=1;a<=m;a++)    {        if(s[a].y!=s[a-1].y)pm++;        hash[pm]=a;        transfor[s[a].x]=pm;    }    b=1;    for(a=1;a<=n;a++)    {        scanf("%d",&ask);        for(b;b<=ask;b++)add(1,1,pm,transfor[b]);        cout<
        
         <<'\n'; } return 0;}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/12977875 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！