poj2182（线段树求序列第k小）

题目链接：https://vjudge.net/problem/POJ-2182

题意：有n头牛，从1..n编号，乱序排成一列，给出第2..n个牛其前面有多少比它编号小的个数，记为a[i]，求该序列的完整编号ans[i]。

思路：最近几天开始学线段树，加油！！我们从序列最后一个开始，则可以确定ans[n]=a[n]+1，然后把编号a[n]+1删除，继续判断倒数第二个...而这一求序列中第k小的数可通过线段树来完成。线段树结点包含l（区间左端点），r（区间右端点），len（区间剩余的编号个数）。每次查询时维护len属性，若k<=左子树的len，则遍历左子树，否则遍历右子树。

AC代码：

#include<cstdio>
using namespace std;
const int maxn=8005;

struct node{
    int l,r,len;
}tr[4*maxn];

int n,a[maxn],ans[maxn];

void build(int v,int l,int r){
    tr[v].l=l,tr[v].r=r,tr[v].len=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(2*v,l,mid);
    build(2*v+1,mid+1,r);
}

int query(int v,int k){
    --tr[v].len;
    if(tr[v].l==tr[v].r) return tr[v].r;
    if(k<=tr[2*v].len) query(2*v,k);
    else query(2*v+1,k-tr[2*v].len);
}

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=n;i>=1;--i)
        ans[i]=query(1,a[i]+1);
    for(int i=1;i<=n;++i)
        printf("%d
",ans[i]);
    return 0;
}

poj2182（线段树求序列第k小）

相关推荐