本文共 1408 字，大约阅读时间需要 4 分钟。

对于逆序对，可以用树状数组来求，而树状数组就是求出所有的非逆序对，答案当然就是所有情况减去非逆序对了。 举个栗子 1 3 5 2 4 首先输入1，那么在树状数组角标1的位置加入1，3，5同理 这样在加入3的时候，求出前面有一个和它非逆序 5的时候发现前面有两个数和它非逆序 2的时候发现前面有一个数和它非逆序 4的时候发现前面有三个和它非逆序 那么答案就是从5个数中选两个的组合数-非逆序对数 就是10-7=3

树状数组的一些操作：

$lowbit$操作

ll lowbit(ll x){
   	return x&(-x);}

更新操作

void update(ll i, ll x)//更新操作 {
       for (ll pos = i; pos < MAXN; pos += lowbit(pos))        tree[pos] += x;}

求前n项和操作

ll query(ll n)//求前n项和 {
       ll ans = 0;    for (ll pos = n; pos; pos -= lowbit(pos))        ans += tree[pos];    return ans;}

求区间和操作

ll query(ll a, ll b)//查询 {
       return query(b) - query(a - 1);}

本题有一些问题就是：

1.为什么会RE，刚开始做的时候，内心看到满屏的RE是崩溃的。 因为内容的数字可能会大于1e9但是正常的数组没有办法开到如此大，因此需要离散化 2.在离散化过程中如果遇到两数相等会不会出问题 那么就需要在离散化过程中的cmp函数的作用了，如果数值相等，那么这个就不能说是逆序对了，所以需要id小的放到前面去，id大的放到后面去（离散化记录的是相对的位置大小），这样处理的话相等的数值就不会出现误判逆序的问题了。

#include
   
    #include
    
     using namespace std;typedef long long ll;const ll MAXN=6e5;ll tree[MAXN];struct node{
   	ll id;	ll t;}s[2100021];ll a[2102010];ll lowbit(ll x){
   	return x&(-x);} void update(ll i, ll x)//更新操作 {
       for (ll pos = i; pos < MAXN; pos += lowbit(pos))        tree[pos] += x;}ll query(ll n)//求前n项和 {
       ll ans = 0;    for (ll pos = n; pos; pos -= lowbit(pos))        ans += tree[pos];    return ans;}ll query(ll a, ll b)//查询 {
       return query(b) - query(a - 1);}ll cmp(node x,node y){
   	if(x.t==y.t)return x.id
    
   

还是挺考察对树状数组的理解的，好题啊！

转载地址：http://zsjrz.baihongyu.com/