POJ-2104-K-th Number(函数式线段树)

Description

Input

Output

Sample Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

5
6
3

Hint

Source

思路：离散化，插入，查询。详见代码。

#include <cstdio>
#include <algorithm>
using namespace std;

struct S{
int val,id,pos;
}node[100005];

bool cmpval(struct S a,struct S b)
{
    return a.val<b.val;
}

bool cmpid(struct S a,struct S b)
{
    return a.id<b.id;
}

int T[100005],ls[4000000],rs[4000000],vv[100005],cnum[4000000],nodenum,cnt,n,m;

void insert(int s,int e,int pos,int pre,int &x)
{
    x=++nodenum;

    ls[x]=ls[pre];
    rs[x]=rs[pre];

    cnum[x]=cnum[pre]+1;

    if(s!=e)
    {
        int mid=(s+e)>>1;

        if(pos<=mid) insert(s,mid,pos,ls[pre],ls[x]);
        else insert(mid+1,e,pos,rs[pre],rs[x]);
    }

}

int query(int a,int b,int s,int e,int k)
{
    if(s==e) return vv[s];
    else
    {
        int mid=(s+e)>>1;

        if(cnum[ls[b]]-cnum[ls[a]]>=k) return query(ls[a],ls[b],s,mid,k);//跟第b棵树的左子树和第a棵树的左子树的差比较
        else return query(rs[a],rs[b],mid+1,e,k-cnum[ls[b]]+cnum[ls[a]]);
    }
}

int main()
{
    int i,a,b,k;

    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&node[i].val);
            node[i].id=i;

            vv[i]=node[i].val;
        }

        sort(vv+1,vv+n+1);
        cnt=unique(vv+1,vv+n+1)-vv-1;//去重

        sort(node+1,node+n+1,cmpval);

        int p=1;

        for(i=1;i<=n;i++)//离散化
        {
            if(node[i].val!=vv[p]) p++;

            node[i].pos=p;
        }

        sort(node+1,node+n+1,cmpid);

        T[0]=ls[0]=rs[0]=cnum[0]=nodenum=0;

        for(i=1;i<=n;i++) insert(1,cnt,node[i].pos,T[i-1],T[i]);

        while(m--)
        {
            scanf("%d%d%d",&a,&b,&k);

            printf("%d\n",query(T[a-1],T[b],1,cnt,k));
        }
    }
}

POJ-2104-K-th Number(函数式线段树),布布扣,bubuko.com

POJ-2104-K-th Number(函数式线段树)

原文：http://blog.csdn.net/faithdmc/article/details/38225389