设为首页 加入收藏

TOP

POJ 2299-Ultra-QuickSort-线段树的两种建树方式(二)
2019-08-14 00:08:54 】 浏览:101
Tags:POJ 2299-Ultra-QuickSort- 线段 建树 方式
e<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=5e5+20; int b[N],cnt; //存原排列 struct node{ int x,id; }a[N]; struct tnode{ int l,r,sum; }tr[N<<2]; void pushup(int m) { tr[m].sum=tr[m<<1].sum+tr[m<<1|1].sum; return; } void build(int m,int l,int r) { tr[m].l=l; tr[m].r=r; if(l==r) { tr[m].sum=0; return; } int mid=(l+r)>>1; build(m<<1,l,mid); build(m<<1|1,mid+1,r); pushup(m); return; } void update(int m,int x) { if(tr[m].l==x&&tr[m].r==x) { tr[m].sum=1; return; } int mid=(tr[m].l+tr[m].r)>>1; if(x<=mid) update(m<<1,x); else update(m<<1|1,x); pushup(m); return; } int query(int m,int l,int r) { if(tr[m].l==l&&tr[m].r==r) return tr[m].sum; int mid=(tr[m].l+tr[m].r)>>1; if(r<=mid) return query(m<<1,l,r); if(l>mid) return query(m<<1|1,l,r); return query(m<<1,l,mid)+query(m<<1|1,mid+1,r); } bool cmp1(node p,node q) { return p.x<q.x; } bool cmp2(node p,node q) { return p.id<q.id; } int getid(int x) { return lower_bound(b,b+cnt,x)-b+1; } int main() { int n; while(1) { scanf("%d",&n); if(!n) break; //输入 a[0].x=-1; for(int i=1;i<=n;i++) { scanf("%d",&a[i].x); a[i].id=i; } //先离散化 sort(a+1,a+n+1,cmp1); cnt=0; for(int i=1;i<=n;i++) if(a[i].x!=a[i-1].x) b[cnt++]=a[i].x; //根据离散后的cnt建树 build(1,1,cnt); //别忘了把a数组sort回来 sort(a+1,a+n+1,cmp2); //边更新边查询 ll ans=0; for(int i=1;i<=n;i++) { int t=getid(a[i].x); ans+=query(1,t,n); update(1,t); } //输出 printf("%lld\n",ans); } return 0; }
首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇hdu--1232 继续通畅工程 下一篇湫湫系列故事——设计风景线 HDU ..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目