题解：P11037 【MX-X3-T4】「RiOI-4」上课

Wf_yjqd · 2024-09-09 19:21:21 · 题解

怎么评蓝的？怎么评蓝的？怎么评蓝的？

平均数 \bar x=\frac{\sum\limits_{i=1}^n x_i}{n}。

方差简单的变形，\frac{\sum\limits_{i=1}^n(x_i-\bar x)^2}{n}=\frac{\sum\limits_{i=1}^n x_i^2}{n}-(\bar x)^2。

显然对于每个询问，平均数是固定的，所以题目相当于最小化平方和。

假设一开始所有 a_i 都取到 l_i，只需要以此为基础将一些 a_i 的值增加。

若将 x-1 增加到 x，平方和增加 x^2-(x-1)^2=x\times2-1。

所以显然每次将最小值增加 1 最优。

将询问离线，记录可以增加到每个数的数的个数，双指针维护即可。

复杂度 \operatorname{O}(n\log n)，瓶颈在于排序。

建议评黄。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+26,mx=1e6,mod=998244353;
struct Query{
    ll x,id,ans;
    friend bool operator<(Query xy,Query zb){
        return xy.x<zb.x;
    }
}qq[maxn];
ll n,q,invn,l[maxn],r[maxn],cnt[maxn],ans,ansx;
inline ll Pow(ll x,ll y){
    if(!y)
        return 1;
    if(y&1)
        return Pow(x,y^1)*x%mod;
    return Pow(x*x%mod,y>>1);
}
int main(){
    scanf("%lld%lld",&n,&q);
    invn=Pow(n,mod-2);
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld",&l[i],&r[i]);
        ans+=l[i]*l[i];
        ansx+=l[i];
        cnt[l[i]+1]++;
        cnt[r[i]+1]--;
    }
    for(ll i=0;i<=mx;i++)
        cnt[i]+=cnt[i-1];
    for(ll i=1;i<=q;i++){
        scanf("%lld",&qq[i].x);
        qq[i].id=i;
    }
    sort(qq+1,qq+q+1);
    for(ll i=1,j=0;i<=q;i++){
        while(ansx<qq[i].x){
            if(qq[i].x-ansx<cnt[j]){
                cnt[j]-=(qq[i].x-ansx);
                (ans+=(qq[i].x-ansx)*(j*2-1)%mod)%=mod;
                ansx=qq[i].x;
                break;
            }
            ansx+=cnt[j];
            (ans+=cnt[j]*(j*2-1)%mod)%=mod;
            j++;
        }
        qq[i].ans=ans;
        qq[i].x%=mod;
    }
    sort(qq+1,qq+q+1,[](Query xy,Query zb){
        return xy.id<zb.id;
    });
    for(ll i=1;i<=q;i++)
        printf("%lld\n",(qq[i].ans*invn%mod-qq[i].x*qq[i].x%mod*invn%mod*invn%mod+mod)%mod);
    return 0;
}