poj_2182 线段树/树状数组

题目大意

n个数排成一排（不知道大小，只是占了一个位置），从a[1]到a[n]进行遍历，对于每个a[i]，给出从a[1]到a[i-1]中小于a[i]数的个数。要求出 a[1]到a[n]中这n个数的相对顺序。

题目分析

对于每个数 a[i], 给出了从 a[1] — a[i-1]中小于a[i]的个数 less[i]. 
    从n到1逆序查看， less[n] 表示前n-1个数中小于a[n]的个数，则可以确定a[n]的位置为 less[n] + 1 
类似的对于 i，为了确定a[i]在所有n个数中的序号，将这个任务分为两部分： 
（1）在 a[1] — a[i-1]中有多少个数小于a[i]， 题目给出了为 less[i] 
（2）在a[i+1]—a[n]中有多少个数小于 a[i]， 设为t

则 a[i] 在所有n个数中的序号（按照从小到大排序）为 k = less[i] + t + 1

但是，t并不好直接求出，则观察k的性质。对于a[i]在所有n个数中的位置k，1—k-1中包括 less[i]个在 a[1] — a[i-1]中的元素，同时包括t个在a[i+1]—a[n]中的元素，在a[i+1]—a[n]中的元素已经确定了他们在整个n个数中的位置（我们是从后往前进行计算的）,则 1—-k-1中就可以确定那t个元素的位置。

为了确定k的位置，则设置一个数组b[1]–b[n],初始全部为0，从n到1统计，若a[i]的位置确定下来为p，则 b[p] = 1.则对于任意的k，b[1]—b[k]中1的个数表示 1—-k中被占用的位置，0 的位置表示未被占用的位置。

对于 a[i]，找到某个k，使得其b[1]–b[k-1]中0的个数正好为 less[i]个，则k的位置就是 a[i]在整个n个数中的按照大小排序的位置

实现(c++)

1. 线段树

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>#define MAX_COW_NUM 80010
#define MAX_NODE_NUM 4*MAX_COW_NUMint gLess[MAX_COW_NUM];
int gPos[MAX_COW_NUM];
struct Node{
int beg;
int end;
int sum_zero;
int Mid(){
return (beg + end) >> 1;
}
};
Node gNodes[MAX_NODE_NUM];
void BuildTree(int beg, int end, int index){
gNodes[index].beg = beg;
gNodes[index].end = end;
if (beg == end){
gNodes[index].sum_zero = 1;
return;
}
int left = 2 * index + 1;
int right = 2 * index + 2;
int mid = (beg + end) >> 1;
BuildTree(beg, mid, left);
BuildTree(mid + 1, end, right);
gNodes[index].sum_zero = gNodes[left].sum_zero + gNodes[right].sum_zero;
}
//对于每个数 a[i], 给出了从 a[1] -- a[i-1]中小于a[i]的个数 less[i].
//从n到1逆序查看， less[n] 表示前n-1个数中小于a[n]的个数，则可以确定a[n]的位置为 less[n] + 1
//类似的对于 i，为了确定a[i]在所有n个数中的序号，将这个任务分为两部分：
//（1）在 a[1] -- a[i-1]中有多少个数小于a[i]， 题目给出了为 less[i]
//（2）在a[i+1]---a[n]中有多少个数小于 a[i]， 设为t//则 a[i] 在所有n个数中的序号（按照从小到大排序）为 k = less[i] + t + 1//t 并不好直接求出，则观察k的性质。对于a[i]在所有n个数中的位置k，1---k-1中包括 less[i]个在 a[1] -- a[i-1]中的元素，
//同时包括 t个在a[i+1]---a[n]中的元素，在a[i+1]---a[n]中的元素已经确定了他们在整个n个数中的位置（我们是从后往前进行计算的）,
//则 1----k-1中就可以确定那t个元素的位置。//为了确定k的位置，则设置一个数组 b[1]--b[n],初始全部为0，从n到1统计，若a[i]的位置确定下来为p，则 b[p] = 1.
//则对于任意的k，b[1]---b[k]中1的个数表示 1----k中被占用的位置，0 的位置表示未被占用的位置。//对于 a[i]，找到某个k，使得其b[1]--b[k-1]中0的个数正好为 less[i]个，则k的位置就是 a[i]在整个n个数中的按照大小排序的位置//利用线段树，找到 b[1]---b[pos]中 0的个数为k个的pos的位置
void FindKth(int k, int index, int& pos){
if (gNodes[index].sum_zero < k){
return;
}
if (gNodes[index].beg == gNodes[index].end){
gNodes[index].sum_zero = 0;
pos = gNodes[index].beg;
return;
}
int left = 2 * index + 1, right = 2 * index + 2;
gNodes[index].sum_zero--;
if (gNodes[left].sum_zero >= k){
FindKth(k, left, pos);
}
else{
FindKth(k - gNodes[left].sum_zero, right, pos);
}
}int main(){
int n;
scanf("%d", &n);
BuildTree(0, n - 1, 0);
for (int i = 2; i <= n; i++){
scanf("%d", &gLess[i]);
}
int pos = 0;
gLess[1] = 0;
for (int i = n; i >= 1; i--){
FindKth(gLess[i] + 1, 0, pos);
gPos[i] = pos + 1;
}
for (int i = 1; i <= n; i++){
printf("%d\n", gPos[i]);
}
return 0;
}

 2. 树状数组

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define MAX_COW_NUM 80010
int gLowBit[MAX_COW_NUM];
int gC[MAX_COW_NUM];
int gLess[MAX_COW_NUM];
int gPos[MAX_COW_NUM];
bool gUsed[MAX_COW_NUM];
void InitLowBit(int n){
for (int i = 1; i <= n; i++){
gLowBit[i] = i&(-i);
}
}
void InitSequence(int n){
for (int i = 1; i <= n; i++){
gC[i] = gLowBit[i];
}
}//树状数组的更新
void Update(int p, int n, int add){
while (p <= n){
gC[p] += add;
p += gLowBit[p];
}
}//树状数组的查询
int Query(int p){
int result = 0;
while (p > 0){
result += gC[p];
p -= gLowBit[p];
}
return result;
}//二分法，查找满足要求的 位置
int Search(int k, int n){
int beg = 1, end = n + 1;
while (beg < end){
int mid = (beg + end) >> 1;
int sum_zero = Query(mid);
if (sum_zero == k){
while (mid + 1 < end){//用于判断该位置是否被占用
if (gUsed[mid + 1])
mid++;
else
break;
}
return mid + 1;
}
else if (sum_zero < k){
beg = mid + 1;
}
else{
end = mid;
}
}
return 1;
}int main(){
int n;
scanf("%d", &n);
gLess[1] = 0;
InitLowBit(n);
InitSequence(n);
memset(gUsed, false, sizeof(gUsed));for (int i = 2; i <= n; i++){
scanf("%d", &gLess[i]);
}
for (int i = n; i >= 1; i--){
int pos = Search(gLess[i], n);
gPos[i] = pos;
gUsed[pos] = true;
Update(pos, n, -1);
}
for (int i = 1; i <= n; i++){
printf("%d\n", gPos[i]);
}
return 0;
}