【题目简述】
定义一个长度为 \(n\) 的序列 \(a\) 的方差为：\(s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2\)。
\(\sum\) 为累加求和符号，\(\overline{a}\) 为序列 \(a\) 的平均数。
给定 \(m\) 个形如 \([l,r,b]\) 的组合，表示 \(a_l,a_{l+1},\ldots,a_r\) 为 \(b\)。
给定 \(q\) 个询问，每个询问形如 \([l,r]\)，你要求出区间 \([l,r]\) 的方差 \(s^2 \times (r-l+1)^2\) 的值。
对 \(998244353\) 取模。
【思路】
一道很好的推式子题。。。
前置知识，区间长度乘区间平均值，等于区间和，即：\(n \times \overline{a}=\sum_{i=1}^{n}a_i\)，我们暂时称之为：“拆平均”。
再设 \(n=r-l+1\)，然后给我死命推！
$\ \ \ \ \ s^2 \times n^2 $
\(= \left[\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2\right]\times n^2 （根据定义展开 s^2）\)
\(= \left[\sum_{i=1}^n (a_i-\overline{a})^2\right]\times n （把一个 n 乘进去）\)
\(= \left[\sum_{i=1}^n (a_i^2-2a_i\overline{a}+\overline{a}^2)\right]\times n （完全平方公式展开）\)
\(= \left(\sum_{i=1}^n a_i^2 - \sum_{i=1}^n 2a_i\overline{a} +\sum_{i=1}^n \overline{a}^2\right)\times n （分裂）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - n \times 2 \overline{a}\sum_{i=1}^n a_i + n \times \sum_{i=1}^n \overline{a}^2 （拆括号）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + n \times \sum_{i=1}^n \overline{a}^2 （拆中项平均）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \times n^2 \sum_{i=1}^n \overline{a}^2 （拆 n）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \times \sum_{i=1}^n n^2 \overline{a}^2 （把 n^2 乘进去）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \times \sum_{i=1}^n (n \times \overline{a})^2 （提平方）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \sum_{i=1}^n (\sum_{j=1}^{n}a_j)^2 （拆平均）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \times n (\sum_{j=1}^{n}a_j)^2 （由于末项括号内值与 i 无关，直接化简）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - 2 \left(\sum_{i=1}^n a_i \right)^2 + (\sum_{i=1}^{n}a_i)^2 （常数互相抵消）\)
\(= n \times \left(\sum_{i=1}^n a_i^2 \right) - \left(\sum_{i=1}^n a_i \right)^2 （二、三项合并）\)
至此，我们已经消除了所有的 \(\overline{a}\)，把式子转化为了一个比较好看的形式。
发现式子中的两个求和符号可以用前缀和维护，恭喜你这道题就做完RE了。
发现数据范围 \(1\le l_i\le r_i\le n\le \color{red}10^{18}\)，原地趋势。
于是借鉴分块的思想（？），把每一段的和&平方和维护出来，对于两侧不满足一整段的部分，直接暴力求解。
具体现代码。
【Code】
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,q,l[200005],r[200005],b[200005];
int sum1[200005],sum2[200005]; //区间和&区间平方和
int x,y;
int Baoli1(int l,int r,int b){
return (((r-l+1)%mod)*b)%mod;
}
int Baoli2(int l,int r,int b){
return (((r-l+1)%mod)*((b*b)%mod))%mod;
}
int Calc(int x,int y){
int len=(y-x+1)%mod;
int flagx=lower_bound(r+1,r+1+m,x)-r; //最左端在哪一段
int flagy=lower_bound(r+1,r+1+m,y)-r; //最右端在哪一段
if(flagx==flagy){
return 0; //如果再同一段，说明区间全部相等，直接输出 0
}else{
int s1=(Baoli1(x,r[flagx],b[flagx])+Baoli1(l[flagy],y,b[flagy]))%mod; //暴力求解两端的和
int s2=(Baoli2(x,r[flagx],b[flagx])+Baoli2(l[flagy],y,b[flagy]))%mod; //暴力求解两端的平方和
flagx++,flagy--;
s1=(s1+(sum1[flagy]-sum1[flagx-1]+mod))%mod; //加上中间段的和
s2=(s2+(sum2[flagy]-sum2[flagx-1]+mod))%mod; //加上中间段的平方和
return (((len*s2)%mod+mod)-((s1*s1)%mod))%mod; //公式最后一步
}
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&l[i],&r[i],&b[i]);b[i]%=mod;
int len=(r[i]-l[i]+1)%mod;
sum1[i]=(sum1[i-1]+((len*b[i])%mod))%mod; //长度*数值
sum2[i]=(sum2[i-1]+((len*((b[i]*b[i])%mod))%mod))%mod; //长度*数值的平方
}
for(int i=1;i<=q;i++){
scanf("%lld%lld",&x,&y);
printf("%lld\n",Calc(x,y));
}
return 0;
}