P2804 神秘数字

平均值限制转成前缀和顺序

问题

P2804 神秘数字
给定正整数序列，统计平均数严格大于给定 $M$ 的连续子数组数目，并对 $92084931$ 取模。

数据规模：$n\le2\times10^5$，$M\le3\times10^3$，每个数不超过 $5\times10^3$。

思路

序列上平均值的限制，可以先把分母消掉。对一个长度为正的区间 $[l,r]$，平均数严格大于 $M$，等价于区间和严格大于 $M(r-l+1)$。

因此把每个数都减去 $M$ 后，一个区间合法，当且仅当变换后的区间和严格大于 $0$。

设 sum[i] 是变换后数组前 $i$ 项之和，并令 sum[0] = 0。这样任意区间 $[j+1,i]$ 的和都可以统一写成 sum[i] - sum[j]，这样 sum[0] 就很自然的处理了边界的情况。

固定右端点 $i$ 时，需要统计所有满足 $j<i$ 且 sum[j] < sum[i] 的 $j$。于是原问题被转化为：按下标从左到右扫描，统计此前出现过多少个严格小于当前值的前缀和。

这就是一个 “顺序对” 模型，可以用归并排序，或者树状数组来统计了。

复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

AC 代码

▶

P2804

struct Disc {
/* ================================================== */
vector<ll> v;
void clear( ) { v.clear( ); }
void add( ll x ) { v.push_back( x ); }
void init( ) {
    sort( v.begin( ), v.end( ) );
    v.erase( unique( v.begin( ), v.end( ) ), v.end( ) );
}
int size( ) { return v.size( ); }
int get_idx( ll x ) { return lower_bound( v.begin( ), v.end( ), x ) - v.begin( ) + 1; }
ll get_val( int idx ) { return v[idx - 1]; }
/* ================================================== */
} disc;

struct BIT {
/* ================================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 1, 0 );
}
void build( int N, ll val[] ) {
    init( N );
    for( int i = 1; i <= N; ++ i ) add( i, val[i] );
}
void add( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) tr[i] += val;
} // 单点修改 a[idx] += val
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res += tr[i];
    return res;
} // 查询前缀和 [1, idx]
ll ask( int l, int r ) { 
    return ask( r ) - ask( l - 1 ); 
} // 查询区间和 [l, r]
/* ================================================== */
} bit;

ll a[maxn];
ll sum[maxn];

void solve( ) {
    int n = read( ), M = read( );
    
    disc.add( 0 );
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( ) - M;
        sum[i] = sum[i-1] + a[i];
        disc.add( sum[i] );
    }

    disc.init( );
    int m = disc.size( );

    bit.init( m );
    ll ans = 0;
    // bit.add( disc.get_idx( 0 ), 1 );
    for( int i = 0; i <= n; ++ i ) {
        int x = disc.get_idx( sum[i] );
        ans = ( ans + bit.ask( 1, x - 1 ) ) % mod;
        bit.add( x, 1 );
    }
    cout << ans << '\n';
}