题解 | #小红的子序列逆序对#

分别计算这个数组里面每一对逆序对的贡献，对于每一对逆序对来说，出现的次数为 ，然后用树状数组加速即可。

#define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;
const int N=3e5+10;
const int M=1e3+10;
int mod=1e9+7;
int a[N];
ll tree[500001];
int ksm(int a,int b,int c){
    a%=c;
    int ans=1;
    while(b){
        if(b&1) ans=(ans*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}
ll lowbit(ll num){
	return num&-num;//返回值为二进制下num从左往右第一个1的位置 
}
void build(ll s,ll num){
	for(ll i=s;i<=200000;i+=lowbit(i)) tree[i]+=num;//当s在i的范围内 第num位数组加上num 
}
ll ask(ll s){
	ll ans=0;
	for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//建树的反操作 
	return ans;
}

void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        int x=ask(100000)-ask(a[i]);
        if(x){
            ans=(ans+x*ksm(2,n-2,mod)%mod)%mod;
        }
        build(a[i],1);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    _=1;
    //cin>>_;
    while(_--){
        solve();
    }
}