題意：不解釋了。

看了別人的博客才知道要這么用線段樹，用的靈活。

線段樹的節(jié)點(diǎn)s[k].n記錄剩下節(jié)點(diǎn)的數(shù)目。當(dāng)查找到s[k].l=s[k].r即葉子節(jié)點(diǎn)的時(shí)候，就取這個(gè)值，然后將s[k].n=0說(shuō)明這個(gè)點(diǎn)已經(jīng)被拿了。

應(yīng)該說(shuō)來(lái)是 線段樹 + 二分查找。

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; int n,k; const int N=262144; struct node {int l, r;int n; }s[N*4+1];void bulid(int l,int r,int k) {if(l==r){s[k].l=l;s[k].r=r;s[k].n=1;return ;}s[k].l=l;s[k].r=r;s[k].n=0;int mid=(l+r)>>1;bulid(l,mid,k<<1);bulid(mid+1,r,k<<1|1);s[k].n=s[2*k].n+s[2*k+1].n; } int query(int k,int a) {if(s[k].l==s[k].r){s[k].n=0;return s[k].l;}int ans;if(a<=s[k<<1].n) ans=query(k<<1,a);else if(a>s[k<<1].n) ans=query(k<<1|1,a-s[k<<1].n);s[k].n=s[2*k].n+s[2*k+1].n;return ans; } int main() {int t;scanf("%d",&t);for(int w=1;w<=t;w++){scanf("%d%d",&n,&k);bulid(1,n,1);__int64 ans=0;for(int i=1;i<=k;i++){int a;scanf("%d",&a);ans+=query(1,a);}printf("Case %d: ",w);printf("%I64d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的hdu4217 Data Structure? 线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。