【poj2104/hdu2665】区间k大值

2015.02.16 21:47 Mon | 4次阅读 | 旧日oi | 固定链接 | 源码

题意

给定一个n个数的序列(n<=100000),询问m(m<=100000)次区间(i,j)中第k小的元素

题解

用树套树怎么也水不过……果断学习了主席树,发现也并不难啊,跟上一道线段树套线段树挺像的,可能是还没涉及到修改,挺好用
主席树的讲解网上不少,我就不写了

我的程序

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define maxn 100005
using namespace std;
int n,m,t,x,y,z,cnt;
int rank[maxn],root[maxn*20];
struct node{
    int x;
    int idx;
}a[maxn];
struct functional_segment_tree{
    int l,r,sum;
}fst[maxn*20];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}
void insert(int num,int &rt,int l,int r)
{
    fst[++cnt]=fst[rt];rt=cnt;
    fst[rt].sum++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(num<=mid) insert(num,fst[rt].l,l,mid);
    else insert(num,fst[rt].r,mid+1,r);
}
int query(int L,int R,int c,int l,int r)
{
    if(l==r) return l;
    int t=fst[fst[R].l].sum-fst[fst[L].l].sum;
    int mid=(l+r)>>1;
    if(c<=t) return query(fst[L].l,fst[R].l,c,l,mid);
    else return query(fst[L].r,fst[R].r,c-t,mid+1,r);
}
int main()
{
    cin>>t;
    while(t--)
    {
        cnt=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].idx=i;
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)
        rank[a[i].idx]=i;
        for(int i=1;i<=n;i++)
        root[i]=root[i-1],insert(rank[i],root[i],1,n);  
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            printf("%d\n",a[query(root[x-1],root[y],z,1,n)].x);
        }
    }
}```