[ABC221E] LEQ 题解

· · 题解

思路

考虑任意一对 (i,j) 满足 a_i\leqslant a_j，明显的，下标在 [i+1,j-1] 中的元素可以随便选，反正最终都会为答案做出贡献。因此，对于这样一对 (i,j)，对答案的贡献为 2^{j-i-1}。

考虑枚举 j，则前面有许多个下标 i 可以满足 a_i\leqslant a_j。不妨令所有满足条件的下标 i 构成的集合为 S，则对于这个 j，答案可以转化：

\begin{aligned} \sum\limits_{i\in S} 2^{j-i-1}&=2^j\times \sum\limits_{i\in S} 2^{-i-1}\\ &=2^j\times\sum\limits_{i\in S} (\frac{1}{2})^{i+1}\\ &=2^j\times\sum\limits_{i\in S} \frac{1}{2^{i+1}} \end{aligned}

在 \bmod M 的情况下，我们需要使用乘法逆元，因此原来的答案继续变为：

\begin{aligned} 2^j\times\sum\limits_{i\in S} \frac{1}{2^{i+1}}=2^j\times\sum\limits_{i\in S} \text{inv}(2^{i+1}) \end{aligned}

注意到右边的和式需要我们对所有满足 a_i\leqslant a_j 的 i 的 \text{inv}(2^{i+1}) 取和。不妨离散化后权值线段树，并且动态加入逆元。注意加入必须是单点加的形式而不是覆盖原位置上的数，因为可能有多个 a_i 相等。

代码

int n;
int a[N],tot;
const int V=3e5;
map <int,int> p;
set <int> s;
int ans;
#define mid (l+r>>1)
struct Segment_Tree{
    int sum[N<<2];
    void pushup(int p){
        sum[p]=sum[p<<1]+sum[p<<1|1];
        sum[p]%=M;
    }
    void insert(int p,int l,int r,int d,int x){
        if(l==r){
            sum[p]+=x%M;
            sum[p]%=M;
            return;
        }
        if(d<=mid){
            insert(p<<1,l,mid,d,x);
        }
        else{
            insert(p<<1|1,mid+1,r,d,x);
        }
        pushup(p);
    }
    int query(int p,int l,int r,int ml,int mr){
        if(ml>mr){
            return 0;
        }
        if(ml<=l&&r<=mr){
            return sum[p];
        }
        int ans=0;
        if(ml<=mid){
            ans+=query(p<<1,l,mid,ml,mr);
        }
        if(mid<mr){
            ans+=query(p<<1|1,mid+1,r,ml,mr);
        }
        return ans%M;
    }
} T;//普通线段树，包括单点加和区间查询
#undef mid
ll qpow(ll b,ll p,ll k){
    if(!p){
        return 1;
    }
    ll d=qpow(b,p>>1,k);
    if(p&1){
        return d*d%k*b%k;
    }
    else{
        return d*d%k;
    }
}
ll inv(ll x){
    return qpow(x,M-2,M);//费马小定理
}
signed main(){
#ifdef Griffin
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    cin>>n;
    fr1(i,1,n){
        cin>>a[i];
        s.insert(a[i]);
    }
    for(auto d:s){
        if(!p.count(d)){
            tot++;
            p[d]=tot;
        }
    }
    fr1(i,1,n){
        a[i]=p[a[i]];
    }//离散化
    fr1(i,1,n){
        ll d=qpow(2,i,M);
        ll g=T.query(1,1,V,1,a[i]);//逆元和
        ans+=d*g%M;//加上此位置贡献的答案
        ans%=M;
        T.insert(1,1,V,a[i],qpow(inv(2),i+1,M));//动态加入
    }
    cout<<ans<<endl;
    return 0;
}

AC 记录