poj 2182

线段树代码：

(1.普通二叉树，0ms)

#include<stdio.h>
struct {
    int l,r,len;
}tree[8005<<2];
int pre[8005],ans[8005];
void buildtree(int left,int right,int u) {
    tree[u].l=left;
    tree[u].r=right;
    tree[u].len=right-left+1;
    if(left==right)    return;
    buildtree(left,left+right>>1,u<<1);
    buildtree((left+right>>1)+1,right,(u<<1)+1);
}
int query(int u,int num) {
    --tree[u].len;
    if(tree[u].l==tree[u].r)    return tree[u].l;
    if(tree[u<<1].len<num)    return query((u<<1)+1,num-tree[u<<1].len);
    else return query(u<<1,num);
}
int main() {
    int n;
    scanf("%d",&n);
    pre[1]=0;
    for(int i=2;i<=n;++i)    scanf("%d",&pre[i]);
    buildtree(1,n,1);
    for(int i=n;i>=1;--i)    ans[i]=query(1,pre[i]+1);
    for(int i=1;i<=n;++i)    printf("%d\n",ans[i]);
    return 0;
}

(2.满二叉树，94ms,推荐---下标检索比指针快)

#include<stdio.h>
#include<math.h>
int pre[8005],ans[8005],tree[8005<<2];
void buildtree(int n,int left) {
    for(int i=left;i<left+n;++i) tree[i]=1;
    while(left!=1) {
        for(int i=left/2;i<left;++i)
            tree[i]=tree[i<<1]+tree[(i<<1)+1];
        left=left/2;
    }
}
int query(int u,int num,int left) {
    --tree[u];
    if(u>=left)    return u;
    if(tree[u<<1]<num)    return query((u<<1)+1,num-tree[u<<1],left);
    else return query(u<<1,num,left);
}
int main() {
    int left,n;
    scanf("%d",&n);
    pre[1]=0;
    left=1<<(int(log(n)/log(2))+1);
    for(int i=2;i<=n;++i)    scanf("%d",&pre[i]);
    buildtree(n,left);
    for(int i=n;i>=1;--i)
        ans[i]=query(1,pre[i]+1,left)-left+1;
    for(int i=1;i<=n;++i)    printf("%d\n",ans[i]);
    return 0;
}

树状数组代码：

(79ms)

#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int tree[10000],pre[10000],ans[10000];
int n;
#define lowbit(x)    ((x)&-(x))
void add(int x,int d) {
    while(x<=n) {
        tree[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x) {
    int sum=0;
    while(x) {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int findpos(int x) {
    int l=1,r=n;
    while(l<r) {
        int mid=(l+r)>>1;
        if(sum(mid)<x)    l=mid+1;
        else    r=mid;
    }
    return l;
}
int main() {
    scanf("%d",&n);
    pre[1]=0;
    for(int i=2;i<=n;++i)    scanf("%d",&pre[i]);
    for(int i=1;i<=n;++i)    tree[i]=lowbit(i);
    for(int i=n;i>0;--i) {
        int x=findpos(pre[i]+1);
        add(x,-1);
        ans[i]=x;
    }
    for(int i=1;i<=n;++i)    printf("%d\n",ans[i]);
    return 0;
}

poj 3468

线段树代码：

#include<stdio.h>
#define ll long long
using namespace std;
ll sum[100001<<2],add[100001<<2];
inline void push_up(int rt) {
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int m) {
    if(add[rt]) {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=(m-(m>>1))*add[rt];
        sum[rt<<1|1]+=(m>>1)*add[rt];
        add[rt]=0;
    }
}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void build(int l,int r,int rt) {
    add[rt]=0;
    if(l==r) {
        scanf("%lld",&sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int a,int b,ll c,int l,int r,int rt){
    if(a<=l&&b>=r) {
        sum[rt]+=(r-l+1)*c;
        add[rt]+=c;
        return;
    }
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    if(a<=mid)    update(a,b,c,lson);
    if(b>mid)    update(a,b,c,rson);
    push_up(rt);
}
ll query(int a,int b,int l,int r,int rt) {
    if(a<=l&&b>=r)    return sum[rt];
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid)    ans+=query(a,b,lson);
    if(b>mid)    ans+=query(a,b,rson);
    return ans;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--) {
        char ch;
        int a,b;    ll c;
        scanf(" %c",&ch);
        if(ch=='C') {
            scanf("%d%d%lld",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        else {
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a,b,1,n,1));
        }
    }
}