这是我AC的第一道关于线段树的题目。
题目大意：给你从1到n这n个数字，求出一个序列，要求满足：第i个数前面有a[i]个数小于它。
这题我使用线段树解决，以下是编写的一些函数：
getnum(begin,end)：返回值为区间[begin,end]中剩余的数的个数；
find(k,node)：在线段树找到第k个大的数；
del(k,node)：在线段树中删除k。
基于二分的算法，应该不需要多说。
后来看了别人的代码知道了我把算法设计得复杂了……getnum()完全可以不要，维护一个len[i]数组即可；del()也可以不用，查找的时候连带着更新即可。
这些都给我以下的代码增加了些许遗憾……怎么说呢，第一个线段树……继续努力了！
以下是我的代码：
#include<stdio.h>
const long maxn=8007;
typedef struct
{
long a,b,num;
long left,right;
}node;
long n,a[maxn],ans[maxn];
node tree[maxn*7];long tot;
bool used[maxn];
void build(long begin,long end)
{
long now,mid=(begin+end)>>1;
tot++;now=tot;
tree[now].a=begin;tree[now].b=end;
tree[now].num=end-begin+1;
if(begin<end)
{
tree[now].left=tot+1;build(begin,mid);
tree[now].right=tot+1;build(mid+1,end);
}
}
long getnum(long begin,long end,long node)
{
long t=(tree[node].a+tree[node].b)>>1;
if(begin>end) return 0;
if(begin==tree[node].a&&end==tree[node].b)
return tree[node].num;
if(t>=end) return getnum(begin,end,tree[node].left);
if(t<=begin) return getnum(begin,end,tree[node].right);
return getnum(begin,t,tree[node].left)+getnum(t+1,end,tree[node].right);
}
long find(long k,long node)
{
long t=(tree[node].a+tree[node].b)>>1,count;
if(tree[node].a==tree[node].b) return tree[node].a;
count=getnum(tree[node].a,t,1);
if(count>=k)
return find(k,tree[node].left);
else return find(k-count,tree[node].right);
}
void del(long k,long node)
{
long t=(tree[node].a+tree[node].b)>>1;
tree[node].num--;
if(tree[node].a<tree[node].b)
{
if(t>=k) del(k,tree[node].left);
else del(k,tree[node].right);
}
}
int main()
{
scanf("%ld",&n);
a[1]=0;
for(long i=2;i<=n;i++) scanf("%ld",&a[i]);
// Input
tot=0;
build(1,n);
// Build A Segment-Tree
for(long i=1;i<=n;i++) used[i]=false;
// Clear
for(long i=n;i>=1;i--)
{
ans[i]=find(a[i]+1,1);
del(ans[i],1);
}
// Work
for(long i=1;i<=n;i++) printf("%ld\n",ans[i]);
// Output
return 0;
}
posted on 2010-02-17 20:51
lee1r 阅读(788)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构