P4 跳格⼦ - Hopscotch

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;
long long N, MAXA, a[500005], bit[500005], ans;

// 快速冪 x^n
long long quick_pow(long long x, long long n)
{
    x %= MOD;
    long long res = 1;
    while(n)
    {
        if(n & 1)
            res = (res*x) % MOD;
        x = (x*x) % MOD;
        n >>= 1;
    }
    return res;
}

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

void bit_add(int x, long long val)
{
    for(int i = x; i <= N; i += lowbit(i))
        bit[i] += val;
}

long long bit_query(int x)
{
    long long ans = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        ans += bit[i];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    for(int i = 0; i < N; ++i)	cin >> a[i], MAXA = max(MAXA, a[i]);
    ans = (quick_pow(2, N) - 1 + MOD)%MOD;
    
    for(int i = 0; i < N; ++i)
    {
    	long long cnt = bit_query(MAXA) - (bit_query(a[i]+2) - bit_query(a[i]-3));
		if(cnt) ans = (ans - quick_pow(2, cnt*N - cnt*i - cnt) + MOD)%MOD;
		bit_add(a[i], 1);
	}	
    		
    cout << ans << "\n";
}