制定网站响应时间,移动版网站模板,多功能wordpress图片主题,青岛移动网站开发树状数组离散化求逆序对
用一个数组 w [ ] w[] w[]来记录遍历到当前数时#xff0c;每个数出现的次数 由于只关心每个数前边有多少个数比他大#xff0c;遍历到 i i i时#xff0c;求大于 a [ i ] a[i] a[i]的数有多少个#xff0c;就是对 [ a [ i ] , n ] [a[i], n] [a[i…树状数组离散化求逆序对
用一个数组 w [ ] w[] w[]来记录遍历到当前数时每个数出现的次数 由于只关心每个数前边有多少个数比他大遍历到 i i i时求大于 a [ i ] a[i] a[i]的数有多少个就是对 [ a [ i ] , n ] [a[i], n] [a[i],n]求和。 之后将 a [ i ] a[i] a[i]的出现次数 w [ a [ i ] ] 1 w[a[i]]1 w[a[i]]1再求后边的答案。
如果暴力来做是 O ( n 2 ) O(n^2) O(n2)的不知道这个对不对不过不重要
for (int i 1; i n; i) {int cnt 0;for (int j a[i]; j n; j) {cnt w[j];}ans cnt;w[a[i]];
}发现即要做单点修改 w [ a [ i ] ] 1 w[a[i]] 1 w[a[i]]1又要做区间查询 ∑ j a [ i ] n w [ j ] \sum\limits_{ja[i]}^{n} w[j] ja[i]∑nw[j]于是用树状数组维护 w [ ] w[] w[]来降低复杂度。
回顾树状数组的两个操作区间查询 单点修改 q u e r y ( i ) 表示查询区间 [ 1 , i ] 的和 query(i)表示查询区间[1, i]的和 query(i)表示查询区间[1,i]的和 a d d ( i , k ) 表示将含有 a [ i ] 的点都 k add(i, k)表示将含有a[i]的点都k add(i,k)表示将含有a[i]的点都k
实际上这里说的树状数组是权值树状数组就是记录每个数出现的次数的树状数组
一个前提只关心相对大小数本身有多大我并不关心所以可以离散化否则数据太大的话 w [ ] w[] w[]放不下那么大的下标会爆掉
写法1
按照每个数的大小降序排序如果大小相等则按照位置降序排序考虑为什么这么做
假设在排序后的数组中第 i i i个数的原位置为 p [ i ] p[i] p[i]树状数组维护的是每个原位置的数是否出现。 比如
原数组3 2 1 5 4
下标 1 2 3 4 5排序后5 4 3 2 1
原位置4 5 1 2 3遍历到第2个数4时记录情况为[0, 0, 0, 1, 0]即原位置为4的数已经出现了。
我们知道4的原位置为5此时对区间[1, 5]求和就是原位置5对应的逆序对数量。
把原位置5记录进去。遍历到第3个数3时记录情况为[0, 0, 0, 1, 1]原位置4 5的数已经出现了
知道3的原位置为1此时对区间[1, 1]求和就是原位置1对应逆序对的数量。
把原位置1记录进去。遍历到第4个数2时记录情况为[1, 0, 0, 1, 1]原位置1 4 5的数已经出现了
知道2的原位置为2此时对区间[1, 2]求和就是原位置2对应逆序对的数量。
把原位置2记录进去。遍历到第5个数1时记录情况为[1, 1, 0, 1, 1]原位置1 2 4 5的数已经出现了
知道1的原位置为3此时对区间[1, 3]求和就是原位置3对应逆序对的数量。
把原位置3记录进去。看懂这一丁点就行下边是一顿胡扯可以不看了 注意以下所有情况都在排好序的数组中进行
现在来考虑两个情况
1. 当前数是唯一的不考虑相同数位置降序排序的情况 记第 i 个数为 a [ i ] , 排序前位置为 p [ i ] 记第i个数为a[i], 排序前位置为p[i] 记第i个数为a[i],排序前位置为p[i] 要查询这个位置对应的逆序对数量 因为我们已经按照降序进行了排序就变为查询 位置在 p [ i ] p[i] p[i]之前且大于 a [ i ] a[i] a[i]的数的个数 对应到排序后的数组中就是 前 i − 1 i - 1 i−1个数中原位置在 p [ i ] p[i] p[i]之前的数。 因为排序已经确保了前 i − 1 i - 1 i−1个数都是比 a [ i ] a[i] a[i]大的数现在只需要在前 i − 1 i - 1 i−1个数中找到位置在 p [ i ] p[i] p[i]前的数就可以了
比他大的数在排序前只有两种情况在他前边/在他后边 只有 (排序前在他前边) 的数才会构成逆序对在他后边的数不会构成逆序对
再次强调因为是降序排序故已经确保了 (遍历到第 i i i个数时已经记录出现的数) 都是大于 a [ i ] a[i] a[i]的。
那么对于第 i i i个数比 a [ i ] a[i] a[i]大 且 在 p [ i ] p[i] p[i]之前出现 的数的个数实际上就是已经记录出现了的数的个数即 [ 1 , p [ i ] ] [1, p[i]] [1,p[i]]的和。求区间 [ 1 , p [ i ] ] [1, p[i]] [1,p[i]]的和就是 q u e r y ( p [ i ] ) query(p[i]) query(p[i])。 最后将这个位置的数记为出现 a d d ( p [ i ] , 1 ) add(p[i], 1) add(p[i],1)
2. 如果数不唯一
数不唯一的话按照位置降序排序
考虑一下假设已经按照位置进行了降序排序 当前数为 a [ i ] a[i] a[i]位置 p [ i ] p[i] p[i] 排序后数组中在当前数之前的相同数 a [ j ] a[j] a[j]对应位置 p [ j ] p[j] p[j]一定在 p [ i ] p[i] p[i]后边 那么 [ 1 , p [ i ] ] [1, p[i]] [1,p[i]]求和时是这样的一个区间 1 2 3 4 ... p[i] ... p[j] ... 就不会把相同的数也算到逆序对中这样就避免了重复计算。
总结一下核心降序排序后每个位置 i i i要查询的区间和 [ 1 , p [ i ] ] [1,p[i]] [1,p[i]]是出现在原数组位置 p [ i ] p[i] p[i]之前且大于当前数的元素个数
#includeiostream
#includecstdio
#includealgorithm
#includecstring#define debug(x) std::cerr #x x
#define DEBUG(x) std::cerr #x x std::endltypedef long long ll;
using namespace std;const int N_MAX 500000 10;int n;
int tr[N_MAX];
struct Node {int v, p;bool operator (const Node other) const {if (v ! other.v) return v other.v;return p other.p;}
}a[N_MAX];int lowbit(int x) {return x -x;
}void inc(int x, int v) {for (int i x; i n; i lowbit(i)) tr[i] v;
}ll calc(int x) {ll sum 0ll;for (int i x; i 1; i - lowbit(i)) sum tr[i];return sum;
}int main() {cin n;for (int i 1; i n; i) cin a[i].v, a[i].p i;sort(a 1, a n 1);ll ans 0ll;for (int i 1; i n; i) {ans calc(a[i].p);inc(a[i].p, 1);}printf(%lld\n, ans);return 0;
}
