●BZOJ 4821 [Sdoi2017]相关分析

时间:2021-04-20 15:33:04

题链:

http://www.lydsy.com/JudgeOnline/problem.php?id=4821

题解:

线段树
是真的恶心,(也许是我的方法麻烦了一些吧)
首先那个式子可以做如下化简:

${a}=\frac {\sum{(}{x}_{i}-\overline{x}{)}{(}{y}_{i}-\overline{y}{)} } {\sum{(}{x}_{i}-\overline{x}{)}{(}{x}_{i}-\overline{x}{)} }$

$\;\;=\frac{{(}\sum{{x}_{i}{y}_{i}}{)}-{n}\overline{x}\overline{y}} {{(}\sum{{x}_{i}{x}_{i}}{)}-{n}\overline{x}\overline{x}}$

然后可以发现,记录区间内的:
x的和(sx),y的和(sy),x*y的和(sxy),x*x的和(sxx),再来两个lazy标记表示区间x,y增量。
以上的东西用线段树维护就可以解决掉第一个和第二个操作。
但是第三个操作怎么办呢?
我们把每个 xi = i + _xi,yi = i + _yi
然后用 _xi,_yi 去建立上述线段树,及维护和上面相同的东西:
_x的和(_sx),_y的和(_sy),_x*_y的和(_sxy),_x*_x的和(_sxx),再来两个lazy标记表示区间x,y增量。
这样就可以同样以区间修改的方式完成第三个操作。 
但是接下来又来了一个问题:
对于一个询问,如何从维护得到的四元组(_sx,_sy,_sxy,_sxx),
得到用于求出答案的四元组(sx,sy,sxy,sxx)
看看如下式子:(用 ' 代替 _)
${x}_{i}\times{y}_{i}$

$={{(}{x'}_{i}+{i}{)}}\times{{(}{y'}_{i}+{i}{)}}$

$={x'_iy'_i}+{2i}{(}{x'_i+y'_i}{)}+{i^2}$

所以

$\begin{align}{sxy}&={sxy'}\\&+{2(\;\;}{{i(}x'_i+y'_i{)}}+{{{(}i+1{)}(}x'_{i+1}+y'_{i+1}{)}}+{{{(}i+2{)}(}x'_{i+2}+y'_{i+2}{)}}+\cdots{)}\\&+{(}i^2+{{(}i+1{)}}^2+{{(}i+2{)}}^2+\cdots{)}\end{align}$
所以只需再维护一些东西用于计算上面式子的中间项和末尾项即可。
即对每个区间 l~r 维护:

_sufxx:${l}\times{(}{x'}_{l}+{x'}_{l}{)} +{(l+1)}\times{(}{x'}_{l+1}+{x'}_{l+1}{)} +\cdots+ {r}\times{(}{x'}_{r}+{x'}_{r}{)}$

_sufxy:${l}\times{(}{x'}_{l}+{y'}_{l}{)} +{(l+1)}\times{(}{x'}_{l+1}+{y'}_{l+1}{)} +\cdots+ {r}\times{(}{x'}_{r}+{y'}_{r}{)}$

再预处理一个数组 ${pi2[i]}=1^2+2^2+3^2+\cdots+i^2$
然后就可以搞出四元组 (sx,sy,sxy,sxx),进而得出答案。

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100500
#define filein(x) freopen(#x".out","r",stdin)
#define fileout(x) freopen(#x".out","w",stdout)
using namespace std;
double pi2[MAXN];
int x[MAXN],y[MAXN];
struct Info{
double _x,_y,_xy,_xx,_sufxy,_sufxx,_s,_t; int len;
void Clear(){
_x=_y=_xy=_xx=_sufxy=_sufxx=_s=_t=0;
}
void Modify(double s,double t,int type){
if(type==2) Clear();
_xx+=_x*s+_x*s+s*s*len;
_xy+=_x*t+_y*s+s*t*len;
_sufxx+=(s+s)*(1.0+(1+len-1))*len/2;
_sufxy+=(s+t)*(1.0+(1+len-1))*len/2;
_x+=s*len; _y+=t*len;
_s+=s; _t+=t;
}
void Update(const Info &ls,const Info &rs){
_x=ls._x+rs._x; _y=ls._y+rs._y;
_xx=ls._xx+rs._xx; _xy=ls._xy+rs._xy;
_sufxx=ls._sufxx+rs._sufxx+(rs._x+rs._x)*ls.len;
_sufxy=ls._sufxy+rs._sufxy+(rs._x+rs._y)*ls.len;
}
double Calc(const int &l){
double X,Y,XX,XY;
X=_x+(1.0*l+(l+len-1))*len/2; X=X/len;
Y=_y+(1.0*l+(l+len-1))*len/2; Y=Y/len;
XX=_xx+(_sufxx+1.0*(l-1)*(_x+_x))+(pi2[l+len-1]-pi2[l-1]);
XY=_xy+(_sufxy+1.0*(l-1)*(_x+_y))+(pi2[l+len-1]-pi2[l-1]);
return (XY-X*Y*len)/(XX-X*X*len);
}
};
struct SGT{
#define ls lson[u]
#define rs rson[u]
#define alen ((r<ar?r:ar)-(l>al?l:al)+1)
int lson[MAXN*2],rson[MAXN*2],lazy[MAXN*2],sz,rt;
Info nd[MAXN*2];
void pushup(Info &ndu,const Info &ndls,const Info &ndrs){
ndu.Update(ndls,ndrs);
}
void pushdown(int u){
nd[ls].Modify(nd[u]._s,nd[u]._t,lazy[u]),
nd[rs].Modify(nd[u]._s,nd[u]._t,lazy[u]);
lazy[ls]=max(lazy[ls],lazy[u]);
lazy[rs]=max(lazy[rs],lazy[u]);
lazy[u]=nd[u]._s=nd[u]._t=0;
}
void build(int &u,int l,int r){
u=++sz; nd[u].len=r-l+1;
if(l==r){
nd[u].Modify(x[l],y[l],2);
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(nd[u],nd[ls],nd[rs]);
}
void Modify(int u,int l,int r,int al,int ar,double s,double t,int type){
if(al<=l&&r<=ar){
lazy[u]=max(lazy[u],type);
nd[u].Modify(s,t,type);
return;
}
int mid=(l+r)>>1;
if(lazy[u]) pushdown(u);
if(al<=mid) Modify(ls,l,mid,al,ar,s,t,type);
if(mid<ar) Modify(rs,mid+1,r,al,ar,s,t,type);
pushup(nd[u],nd[ls],nd[rs]);
}
Info Query(int u,int l,int r,int al,int ar){
if(al<=l&&r<=ar) return nd[u];
int mid=(l+r)>>1; Info ret,lret,rret;
ret.Clear(); lret.Clear(); rret.Clear();
ret.len=alen; lret.len=0; rret.len=0;
if(lazy[u]) pushdown(u);
if(al<=mid) lret=Query(ls,l,mid,al,ar);
if(mid<ar) rret=Query(rs,mid+1,r,al,ar);
pushup(ret,lret,rret);
return ret;
}
#undef ls
#undef rs
#undef alen
}T;
int N,M;
void read(int &X){
static int f; static char ch;
scanf("%d",&X); return;
X=0; f=1; ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-') f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){X=X*10+ch-'0'; ch=getchar();}
X=X*f;
}
int main(){
read(N); read(M);
for(int i=1;i<=N;i++) pi2[i]=pi2[i-1]+1.0*i*i;
for(int i=1;i<=N;i++) read(x[i]),x[i]-=i;
for(int i=1;i<=N;i++) read(y[i]),y[i]-=i;
T.build(T.rt,1,N);
Info ret; int c,l,r,s,t;
for(int i=1;i<=M;i++){
read(c); read(l); read(r);
if(c==1){
ret=T.Query(T.rt,1,N,l,r);
printf("%.10lf\n",ret.Calc(l));
}
else{
read(s); read(t);
T.Modify(T.rt,1,N,l,r,s,t,c-1);
}
}
return 0;
}