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++;elsebreak;}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; }

 

总结

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

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