這是我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 閱讀(797)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構