自动搬运

查看原文

来自洛谷，原作者为

	Wf_yjqd 哀酱永远的神/tyt /se /qq!!!

搬运于2025-08-24 23:03:41，当前版本为作者最后更新于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;
}