• 如何統(tǒng)計(jì)第i個(gè)數(shù)與1～第i - 1個(gè)數(shù)構(gòu)成多少個(gè)逆序?qū)δ?#xff1f;
• 考慮根據(jù)值來建樹狀數(shù)組，初始樹狀數(shù)組為全0，先按序列從左到右將數(shù)據(jù)的值對(duì)應(yīng)的位置的數(shù)加一，代表又有一個(gè)數(shù)出現(xiàn)。因此，在循環(huán)到第i項(xiàng)時(shí)，前i-1項(xiàng)已經(jīng)加入到樹狀數(shù)組內(nèi)了，樹狀數(shù)組內(nèi)比ai大的都會(huì)與ai構(gòu)成逆序?qū)?#xff0c;產(chǎn)生的逆序?qū)?shù)量是i-sum(ai)
• 根據(jù)ai來建樹狀數(shù)組空間不夠誒？
• 確實(shí)不夠，但我們需要的只是元素之間的相對(duì)大小，這啟發(fā)我們對(duì)數(shù)據(jù)離散化，先將數(shù)據(jù)排序，再用1～n分別對(duì)應(yīng)n個(gè)數(shù)表示它們的相對(duì)大小，對(duì)新的序列建樹狀數(shù)組空間就夠了(n≤5×10^5 )
• 相等的元素是否會(huì)導(dǎo)致求解錯(cuò)誤？每一個(gè)數(shù)（不管是否相等）對(duì)應(yīng)的新數(shù)都不同誒？
• 不處理的話會(huì)出錯(cuò)的，問題的關(guān)鍵在于是否有與ai相等的元素在ai前被加入且其相對(duì)大小標(biāo)記更大。出現(xiàn)這種情況就會(huì)誤將兩個(gè)相等的數(shù)判為逆序?qū)ΑＴ趺唇鉀Q呢，只要所有與ai相等的元素中，先出現(xiàn)的標(biāo)記也更小就好了(我們只統(tǒng)計(jì)相對(duì)更大的)。具體只需要在排序時(shí)將ai作為第一關(guān)鍵字，下標(biāo)(第幾個(gè)出現(xiàn))作為第二關(guān)鍵字從小到大排序即可。

#include <iostream> #include <algorithm>using namespace std;typedef long long ll;const int N = 5e5 + 10;int Rank[N], tr[N]; int n;struct node {int num, val; }a[N];bool cmp(node a, node b) {if (a.val == b.val)return a.num < b.num;return a.val < b.val; }int lowbit(int x) {return x & (-x); }void add(int x, int c) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; }ll sum(int x) {ll res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res; }int main() {scanf("%d", &n);for (int i = 1; i <= n; i ++ )scanf("%d", &a[i].val), a[i].num = i;sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n ; i ++ )Rank[a[i].num] = i;ll ans = 0;for (int i = 1; i <= n; i ++ ){add(Rank[i], 1);ans += i - sum(Rank[i]);}printf("%lld\n", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的树状数组 求 逆序对的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。