区间第K大(划分树)

63 阅读 0 评论 42 点赞

我是靠谱客的博主阳光大叔，最近开发中收集的这篇文章主要介绍区间第K大(划分树)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1175

注意一个很明显的结论：求区间[p,q]的第K大就等于求区间[p,q]的第q-p+1-k小。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N = 100005;

int sorted[N];
int Tree[20][N];
int toLeft[20][N];

void Build(int k,int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    int i,t;
    t=mid-l+1;
    for(i=l;i<=r;i++)
       if(Tree[k][i]<sorted[mid])
          t--;
    int L=l;
    int R=mid+1;
    for(i=l;i<=r;i++)
    {
       if(i==l)
          toLeft[k][i]=0;
       else
          toLeft[k][i]=toLeft[k][i-1];
       if(Tree[k][i]<sorted[mid])
       {
           toLeft[k][i]++;
           Tree[k+1][L++]=Tree[k][i];
       }
       else if(Tree[k][i]>sorted[mid])
       {
           Tree[k+1][R++]=Tree[k][i];
       }
       else
       {
           if(t!=0)
           {
               t--;
               toLeft[k][i]++;
               Tree[k+1][L++]=Tree[k][i];
           }
           else
               Tree[k+1][R++]=Tree[k][i];
       }
    }
    Build(k+1,l,mid);
    Build(k+1,mid+1,r);
}

int Query(int k,int l,int r,int p,int q,int t)
{
    if(p==q) return Tree[k][p];
    int s,ss;
    int mid=(l+r)>>1;
    if(l==p)
    {
        s=0;
        ss=toLeft[k][q];
    }
    else
    {
        s=toLeft[k][p-1];
        ss=toLeft[k][q]-s;
    }
    int L,R;
    if(t<=ss)
    {
        L=l+s;
        R=l+s+ss-1;
        return Query(k+1,l,mid,L,R,t);
    }
    else
    {
        L=mid-l+1+p-s;
        R=mid-l+1+q-s-ss;
        return Query(k+1,mid+1,r,L,R,t-ss);
    }
}

int main()
{
    int n,m,i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&Tree[0][i]);
            sorted[i]=Tree[0][i];
        }
        std::sort(sorted+1,sorted+n+1);
        Build(0,1,n);
        scanf("%d",&m);
        int p,q,k;
        while(m--)
        {
            scanf("%d%d%d",&p,&q,&k);
            p++;q++;k--;
            printf("%dn",Query(0,1,n,p,q,q-p+1-k));
        }
    }
    return 0;
}