逆序对——树状数组
逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 a i > a j a_i>a_j ai>aj 且 i < j i<j i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
输入格式
第一行，一个数 n n n，表示序列中有 n n n个数。
第二行 n n n 个数，表示给定的序列。序列中每个数字不超过 1 0 9 10^9 109。
输出格式
输出序列中逆序对的数目。
样例 #1
样例输入 #1
6
5 4 2 6 3 1
样例输出 #1
11
提示
对于 25 % 25\% 25% 的数据， n ≤ 2500 n \leq 2500 n≤2500
对于 50 % 50\% 50% 的数据， n ≤ 4 × 1 0 4 n \leq 4 \times 10^4 n≤4×104。
对于所有数据， n ≤ 5 × 1 0 5 n \leq 5 \times 10^5 n≤5×105
思路：
问题解答
Q1: 如何统计第 i i i 个数会与第 i + 1 i+1 i+1 ~ n n n 个数构成多少个逆序对呢?
Ans1: 可以通过建立一个树状数组来解决这个问题。初始时，树状数组的所有元素都为 0 0 0。然后，按照序列从右到左将数据的值对应的位置的数加一，表示该值已经出现。在处理第 i i i 项时，后 n − i n-i n−i 项已经加入到树状数组中。树状数组中比 a i a_i ai 小的元素都会与 a i a_i ai 构成逆序对，因为它们出现的更早。因此，产生的逆序对数量为 q u e r y ( a i ) query(a_i) query(ai)，其中 q u e r y ( a i ) query(a_i) query(ai) 表示在树状数组内询问 1 1 1 ~ a i a_i ai 项的前缀和。
Q2: 根据 a i a_i ai 来建树状数组空间不够啊？
Ans2: 确实，直接根据 a i a_i ai 的值来建立树状数组可能会导致空间不足。但是，我们只需要数据之间的相对大小，而不需要具体的数值大小。因此，可以通过离散化来解决这个问题。具体来说，先将数据排序，然后用 1 1 1 ~ n n n 分别对应 n n n 个数表示它们的相对大小。这样，对新的序列建立树状数组就足够了，因为 n ≤ 5 × 1 0 5 n \leq 5 \times 10^5 n≤5×105。
Q3: 相等的元素是否会导致求解错误？每一个数（不管是否相等）对应的新数都不同诶？
Ans3: 如果不处理相等的元素，确实会导致错误。问题的关键在于是否有与 a i a_i ai 相等的元素在 a i a_i ai 之前被加入且其相对大小标记更大。为了解决这个问题，可以在排序时将 a i a_i ai 作为第一关键字，下标（第几个出现）作为第二关键字从小到大排序。这样，所有与 a i a_i ai 相等的元素中，先出现的标记也更小，从而避免了误判逆序对的情况。
总结
通过建立树状数组并结合离散化处理，可以高效地统计序列中每个元素与其之前的元素构成的逆序对数量。离散化确保了空间复杂度在可接受范围内，而排序时考虑元素出现顺序则避免了相等元素导致的错误。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+100,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m;
struct node
{int id;int s;
}a[N],b[N];
bool cmp(node a,node b)
{if(a.s!=b.s) return a.s<b.s;else return a.id<b.id;
}
int c[N];
int ranks[N];
int lowbit(int x)
{return x&(-x);
}
int query(int x)
{int s=0;for(;x>0;x-=lowbit(x)){s+=c[x];}return s;
}
void modify(int id,int x)
{for(;id<=n;id+=lowbit(id)){c[id]+=x;}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i].s,a[i].id=i;sort(a+1,a+1+n,cmp);int ans=0;for(int i=1;i<=n;i++) ranks[a[i].id]=i;for(int i=n;i>=1;i--){int idx=ranks[i];ans+=query(idx-1);modify(idx,1);}cout<<ans<<endl;}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);T=1;//cin>>T;while(T--){solve();}return 0;
}