hdu4217 Data Structure? 线段树

题意：不解释了。

看了别人的博客才知道要这么用线段树，用的灵活。

线段树的节点s[k].n记录剩下节点的数目。当查找到s[k].l=s[k].r即叶子节点的时候，就取这个值，然后将s[k].n=0说明这个点已经被拿了。

应该说来是 线段树 + 二分查找。

#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);} }

总结

以上是生活随笔为你收集整理的hdu4217 Data Structure? 线段树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。