区间方差
link
线段树大水题（确信）
这道题没有区间修改，所以我们不用写懒标记 所以出题人听我说谢谢你，想写懒标记的去这道题
方差公式为：
\[d=\frac{\sum\limits_{i=1}^{n}(a_i-\overline{a})^2}{n}
\]
修改 \(a_i\) 不会对 \(n\) 产生影响，所以我们暂时不用考虑 \(n\) ，考虑上半部分。
把上半部分展开，可得：
\[\sum\limits_{i=1}^n {a_i}^2 -2n\overline{a}\sum\limits_{i=1}^n a_{i}+n{\overline{a}}^2
\]
第一项求出区间平方和即可，第二项和第三项求出区间和即可。
\(\overline{a}\) 的求法：
\[\overline{a}=\frac{1}{n}\sum\limits_{i=1}^n a_i
\]
求出区间和后即可直接求出 \(\overline{a}\)
除法可以通过乘法逆元来处理。
所以我们需要维护两个标记，区间和，区间平方和。
代码：
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
typedef __uint128_t ULLL;
static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
inline void pc(const char &ch){
if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
*pw++=ch;
}
#define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
struct FastMod{
FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
ULL reduce(ULL a){
ULL q=(ULL)((ULLL(m)*a)>>64);
ULL r=a-q*b;
return r>=b?r-b:r;
}
ULL b,m;
}HPOP(10);
struct QIO{
char ch;
int st[40];
template<class T>inline T read(T &x){
x=0,ch=gc;
while(!isdigit(ch))ch=gc;
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
return x;
}
template<class T>inline void write(T a){
do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
while(st[0])pc(st[st[0]--]^48);
pc('\n');
}
}qrw;
}
using namespace FastIo;
#define ls(rt) rt<<1
#define rs(rt) rt<<1|1
#define mid (l+r>>1)
#define lson l,mid,ls(rt)
#define rson mid+1,r,rs(rt)
const int mod=1e9+7,NUMBER1=1e5;
template<class T>inline T square(const T &a){return a*a;}
inline LL quick_mod(LL a){
LL ans(1),b=mod-2;
while(b){
if(b&1)ans=ans*a%mod;
a=square(a)%mod,b>>=1;
}
return ans;
}
struct SEG{
LL sum,squ;
SEG(LL sum=0,LL squ=0):sum(sum),squ(squ){}
SEG operator+(const SEG &A)const{
SEG ret;
ret.squ=((LL)squ+A.squ)%mod,ret.sum=((LL)sum+A.sum)%mod;
return ret;
}
}tr[(NUMBER1<<2)+5];
struct Segment{
inline void push_up(const int &rt){
tr[rt].sum=((LL)tr[ls(rt)].sum+tr[rs(rt)].sum)%mod;
tr[rt].squ=((LL)tr[ls(rt)].squ+tr[rs(rt)].squ)%mod;
}
void build(int l,int r,int rt){
if(l==r)return tr[rt].squ=square(qrw.read(tr[rt].sum))%mod,void(0);
build(lson);build(rson);push_up(rt);
}
void update(int l,int r,int rt,int p,LL k){
if(l==r)return tr[rt].sum=k%mod,tr[rt].squ=square(k)%mod,void(0);
if(p<=mid)update(lson,p,k);
else update(rson,p,k);
push_up(rt);
}
SEG query(int l,int r,int rt,int x,int y){
if(x<=l&&r<=y)return tr[rt];
SEG res;
if(x<=mid)res=res+query(lson,x,y);
if(mid<y)res=res+query(rson,x,y);
return res;
}
}seg;
signed main(){
int n,m;
SEG k;
qrw.read(n);
qrw.read(m);
seg.build(1,n,1);
for(LL c,x,y,average,ans;m;--m){
qrw.read(c);
qrw.read(x);
qrw.read(y);
if(c==1)seg.update(1,n,1,x,y);
else{
k=seg.query(1,n,1,x,y);
c=quick_mod(y-x+1);
average=c*k.sum%mod;
ans=k.squ*c%mod-square((LL)average)%mod;
qrw.write((ans%mod+mod)%mod);
}
}
fsh;
exit(0);
return 0;
}
后记：
一定要记得开 long long 。一开始我认为开 int ，相加取模时强制转为 long long 即可，结果调了我几个小时。如果你有仔细看我代码，你会发现我基本上都是后面才开了 long long 的，之前用 int 强制转为 long long 的影子还存在着（懒得删了）。