首页 > 代码库 > POJ 2182 线段树
POJ 2182 线段树
链接：
http://poj.org/problem?id=2182
题意：
有N头牛，编号1~N，乱序排成一列，现在已知每头牛前面有多少头牛比它的编号小，
求排队后从前往后数，每头牛的编号
题解：
从后往前扫描，遇到数字a，说明它是剩余序列中的第a+1个数，找到改编号并删除。
代码：
31 int a[MAXN];32 int tree[MAXN];33 34 void pushup(int rt) {35 tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];36 }37 void build(int l, int r, int rt) {38 if (l == r) {39 tree[rt] = 1;40 return;41 }42 int m = (l + r) >> 1;43 build(lson);44 build(rson);45 pushup(rt);46 }47 48 int query(int x, int l, int r, int rt) {49 tree[rt]--;50 if (l == r) return l; 51 int m = (l + r) >> 1;52 if (x <= tree[rt << 1]) return query(x, lson);53 else return query(x - tree[rt << 1], rson);54 }55 56 int main() {57 int n;58 cin >> n;59 build(1, n, 1);60 rep(i, 1, n) cin >> a[i];61 per(i, 0, n) a[i] = query(a[i] + 1, 1, n, 1);62 rep(i, 0, n) cout << a[i] << endl;63 return 0;64 }
POJ 2182 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。