P10511 题解

· · 题解

首先我们来推式子，令 sum=\sum_{i=1}^n a_i,r-l+1=n。

n^2\cdot \frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2 =n\cdot \sum_{i=1}^n (a_i-\overline{a})^2 =n\cdot \sum_{i=1}^n (a_i-\frac{1}{n}\sum_{i=1}^n a_i)^2 =n\cdot \sum_{i=1}^n (a_i-\frac{sum}{n})^2 =n\cdot ({a_1}^2-\frac{2a_1sum}{n}+\frac{sum^2}{n^2}+{a_2}^2-\frac{2a_2sum}{n}+\frac{sum^2}{n^2}\dots+{a_n}^2-\frac{2a_nsum}{n}+\frac{sum^2}{n^2}) =n\cdot ({a_1}^2+{a_2}^2+\dots {a_n}^2-\frac{2a_1sum}{n}-\frac{2a_2sum}{n}\dots-\frac{2a_nsum}{n}+\frac{nsum^2}{n^2} =n\cdot ({a_1}^2+{a_2}^2+\dots {a_n}^2-\frac{2sum^2}{n}+\frac{sum^2}{n}) =n\cdot ({a_1}^2+{a_2}^2+\dots {a_n}^2-\frac{sum^2}{n}) =n\cdot ({a_1}^2+{a_2}^2+\dots {a_n}^2)-sum^2

发现 sum 为区间和，a_1^2+a_2^2+\dots a_n^2 为区间平方和，所以考虑维护这两个东西。

我们先对每个区间求出前缀和和前缀平方和。就能对整个区间处理。但是查询会出现一些散块，也就是没有完全包含这个区间。所以我们先要找到整块，然后处理散块。

对于查询的左端点 x，离他最近的整块的左端点一定不小于他。所以 lower_bound 处理。而对于右端点 y，离他最近的整块的左端点一定不大于他。所以可以 upper_bound，再将找到的坐标 -1。

然后我们算出区间和和区间平方和，答案就呼之欲出了。

注意取模一定要积极，不然会喜提 60。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,m,q;
int x[200005],y[200005],z[200005],sum1[200005],sum2[200005];
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i]>>z[i];
        z[i]%=mod;
        sum1[i]=(sum1[i-1]+z[i]%mod*((y[i]%mod-x[i]%mod+1)%mod))%mod;
        sum2[i]=(sum2[i-1]+z[i]%mod*z[i]%mod*((y[i]%mod-x[i]%mod+1)%mod))%mod;
        //处理前缀和和前缀和平方和
    }
    while(q--)
    {
        int l,r,cnt1=0,cnt2=0,num1,num2,ans;
        cin>>l>>r;
        num1=lower_bound(x+1,x+m+1,l)-x;
        num2=upper_bound(y+1,y+m+1,r)-y-1;
        //找到左右整块的两个编号
        if(num1>num2+1||num1>m)//特判不合法的块
        {
            cout<<0<<"\n";
            continue;
        }
        cnt1=((sum1[num2]-sum1[num1-1])%mod+(x[num1]-l)%mod*z[num1-1]%mod+(r-y[num2])%mod*z[num2+1]%mod)%mod;
        cnt2=((sum2[num2]-sum2[num1-1])%mod+(x[num1]-l)%mod*z[num1-1]%mod*z[num1-1]%mod+(r-y[num2])%mod*z[num2+1]%mod*z[num2+1]%mod)%mod;
        //cnt1表示区间和，cnt2表示区间平方和
        ans=((r-l+1)%mod*cnt2%mod-cnt1%mod*cnt1%mod)%mod;
        //计算答案
        cout<<(ans+mod)%mod<<"\n";
    }
    return 0;
}