首页 > 代码库 > POJ 2104 求序列里第K大 主席树裸体题

POJ 2104 求序列里第K大 主席树裸体题

2024-07-14 18:35:54   220人阅读

给定一个n的序列，有m个询问 每次询问求l-r 里面第k大的数字是什么

只有询问，没有修改

可以用归并树和划分树（我都没学过。。囧）

我是专门冲着弄主席树来的

对主席树的建树方式有点了解了，不过这题为什么是在主席树里面这么操作的 还是有点不懂，今天照着模板敲了一遍就打多校了

再研究吧

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=100010;const int maxm=maxn*30;int n,m,tot,s;int A[maxn],t[maxn],T[maxn];int c[maxm],lson[maxm],rson[maxm];int build(int l,int r){    int rt=++tot;    c[rt]=0;    if (l>=r) return rt;    int mid=(l+r)>>1;    lson[rt]=build(l,mid);    rson[rt]=build(mid+1,r);    return rt;}int update(int rt,int pos,int val){   int newrt=++tot,tmp=newrt;   c[newrt]=c[rt]+val;   int l=1,r=s;   while (l<r)   {       int mid=(l+r)>>1;       if (pos<=mid){           r=mid;           lson[newrt]=++tot;rson[newrt]=rson[rt];           newrt=lson[newrt];rt=lson[rt];       }       else{           l=mid+1;           rson[newrt]=++tot;lson[newrt]=lson[rt];           newrt=rson[newrt];rt=rson[rt];       }       c[newrt]=c[rt]+val;   }   return tmp;}int query(int lrt,int rrt,int k){    int l=1,r=s;    while (l<r)    {        int mid=(l+r)>>1;        if (c[lson[lrt]]-c[lson[rrt]]>=k){            r=mid;            lrt=lson[lrt];            rrt=lson[rrt];        }        else        {            l=mid+1;            k-=c[lson[lrt]]-c[lson[rrt]];            lrt=rson[lrt];            rrt=rson[rrt];        }    }    return l;}int main(){    while (scanf("%d%d",&n,&m)!=EOF)    {        tot=0;        for (int i=1;i<=n;i++) scanf("%d",&A[i]),t[i]=A[i];        sort(t+1,t+1+n);        s=unique(t+1,t+1+n)-(t+1);        T[n+1]=build(1,m);        for (int i=n;i>=1;i--){            int pos=lower_bound(t+1,t+n+1,A[i])-t;            T[i]=update(T[i+1],pos,1);        }        while (m--)        {            int l,r,k;            scanf("%d%d%d",&l,&r,&k);            int ans=query(T[l],T[r+1],k);            printf("%d\n",t[ans]);        }    }    return 0;}

　　


联系
我们