【BZOJ4821】[SDOI2017] 相关分析(线段树)

点此看题面

大致题意: 给定\(x,y\)两个数组,每次给定\(L,R\),要求支持三种操作:设\(\overline{x}\)为\(x_{L\sim R}\)的平均数,\(\overline{y}\)为\(y_{L\sim R}\)的平均数,求\(\frac{\sum_{i=L}^R(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=L}^R(x_i-\overline{x})^2}\);把区间内所有\(x_i\)加上\(S\),所有\(y_i\)加上\(T\);把区间内所有\(x_i\)修改为\(S+i\),所有\(y_i\)修改为\(T+i\)。

前言

写了一天的计算几何(其实也就\(3\)题。。。),身心俱疲。。。

于是找道比较水的线段树题来水一水。。。

维护

这种东西看看都很难维护,显然要先拆式子:

\[\sum_{i=L}^R(x_i-\overline{x})(y_i-\overline{y}) \]

\[\sum_{i=L}^Rx_iy_i-\overline{x}\sum_{i=L}^Ry_i-\overline{y}\sum_{i=L}^Rx_i+(R-L+1)\overline{x}\overline{y} \]

而\(\overline{x}=\frac{\sum_{i=L}^Rx_i}{R-L+1},\overline{y}=\frac{\sum_{i=L}^Ry_i}{R-L+1}\),代入得到:

\[\sum_{i=L}^Rx_iy_i-\frac{\sum_{i=L}^Rx_i\sum_{i=L}^Ry_i}{R-L+1}-\frac{\sum_{i=L}^Rx_i\sum_{i=L}^Ry_i}{R-L+1}+\frac{\sum_{i=L}^Rx_i\sum_{i=L}^Ry_i}{R-L+1} \]

也就是:

\[\sum_{i=L}^Rx_iy_i-\frac{\sum_{i=L}^Rx_i\sum_{i=L}^Ry_i}{R-L+1} \]

同理,\(\sum_{i=L}^R(x_i-\overline{x})^2\)就等于:(只要把上面式子的\(y\)都换成\(x\)就好了)

\[\sum_{i=L}^Rx_i^2-\frac{(\sum_{i=L}^Rx_i)^2}{R-L+1} \]

然后我们看一看这两个式子,就会发现我们只需要维护\(x_i,y_i,x_i^2,x_iy_i\)各自的和就可以了。

区间加法

第一种修改很简单啊。显然有:(\(l\)为区间长度)

\[\sum(x+S)^2=\sum x^2+2S\sum x+l\cdot S^2 \]

\[\sum(x+T)(y+T)=\sum xy+T\cdot\sum x+S\cdot\sum y+l\cdot S\cdot T \]

因此,\(\sum x^2\)加上\(2S\cdot\sum x_i+l\cdot S^2\),\(\sum xy\)加上\(T\cdot\sum x+S\cdot\sum y+l\cdot S\cdot T\)。

至于\(\sum x,\sum y\),只要分别加上\(l\cdot S\)和\(l\cdot T\)就行了(注意要放后面加)。

区间赋值

第二种修改实际上也很简单,方便起见,我们令\(S,T\)表示当前区间修改为\(S+1,S+2,...,S+l\)和\(T+1,T+2,...,T+l\)(只要在处理右区间时分别给操作中给出的\(S,T\)加上左区间的大小即可)。

则可以得到:

\[\sum x=\sum_{i=1}^l(S+i)=l\cdot S+\frac{l(l+1)}2 \]

\[\sum y=\sum_{i=1}^l(T+i)=l\cdot T+\frac{l(l+1)}2 \]

\[\sum x^2=\sum_{i=1}^l(S+i)^2=l\cdot S^2+S\cdot l(l+1)+\frac{l(l+1)(2l+1)}6 \]

\[\sum xy=\sum_{i=1}^l(S+i)(T+i)=l\cdot S\cdot T+(S+T)\cdot \frac{l(l+1)}2+\frac{l(l+1)(2l+1)}6 \]

于是这道题就做完了,具体实现可以详见代码。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define DB double
#define CD Con DB& 
using namespace std;
int n,x[N+5],y[N+5];
class SegmentTree//线段树
{
	private:
		#define PT CI l=1,CI r=n,CI rt=1
		#define LT l,mid,rt<<1
		#define RT mid+1,r,rt<<1|1
		#define PU(x) (O[x]=O[x<<1]+O[x<<1|1])
		#define PD(x)\
		(\
			O[x].Uf&&(O[x<<1].Upt(O[x].Ux,O[x].Uy),\
				O[x<<1|1].Upt(O[x].Ux+mid-l+1,O[x].Uy+mid-l+1),O[x].Uf=0),\
			(O[x].Ax||O[x].Ay)&&(O[x<<1].Add(O[x].Ax,O[x].Ay),\
				O[x<<1|1].Add(O[x].Ax,O[x].Ay),O[x].Ax=O[x].Ay=0)\
		)//下传标记,注意赋值标记传到右区间要加上左区间大小
		struct node
		{
			#define CN Con node& 
			int l,Uf,Ux,Uy;DB sx,sy,xx,xy,Ax,Ay;
			I friend node operator + (CN x,CN y)//合并两个区间信息
			{
				node t;t.l=x.l+y.l,t.sx=x.sx+y.sx,t.sy=x.sy+y.sy,t.xx=x.xx+y.xx,
				t.xy=x.xy+y.xy,t.Uf=t.Ax=t.Ay=0;return t;
			}
			I void Add(CD s,CD t)//区间加法
			{
				Ax+=s,Ay+=t,xx+=2*s*sx+l*s*s,xy+=t*sx+s*sy+l*s*t,sx+=l*s,sy+=l*t;
			}
			I void Upt(CI s,CI t)//区间赋值
			{
				Ax=Ay=0,Uf=1,Ux=s,Uy=t,sx=1.0*l*s+1.0*l*(l+1)/2,sy=1.0*l*t+1.0*l*(l+1)/2,
				xx=1.0*l*s*s+1.0*s*l*(l+1)+1.0*l*(l+1)*(2*l+1)/6,
				xy=1.0*l*s*t+1.0*(s+t)*l*(l+1)/2+1.0*l*(l+1)*(2*l+1)/6;
			}
		}O[N<<2];
	public:
		I void Build(PT)//建树
		{
			if(l==r)
			{
				O[rt].l=1,O[rt].sx=x[l],O[rt].sy=y[l],O[rt].xx=1.0*x[l]*x[l],
				O[rt].xy=1.0*x[l]*y[l];return;
			}
			int mid=l+r>>1;Build(LT),Build(RT),PU(rt);
		}
		I void U1(CI x,CI y,CI s,CI t,PT)//第一种修改
		{
			if(x<=l&&r<=y) return O[rt].Add(s,t);int mid=l+r>>1;PD(rt);
			x<=mid&&(U1(x,y,s,t,LT),0),y>mid&&(U1(x,y,s,t,RT),0),PU(rt);
		}
		I void U2(CI x,CI y,CI s,CI t,PT)//第二种修改
		{
			if(x<=l&&r<=y) return O[rt].Upt(s,t);int mid=l+r>>1;PD(rt);
			x<=mid&&(U2(x,y,s,t,LT),0),y>mid&&(U2(x,y,s+mid-l+1,t+mid-l+1,RT),0),PU(rt);
		}
		I node Qry(CI x,CI y,PT)//询问
		{
			if(x==l&&r==y) return O[rt];int mid=l+r>>1;PD(rt);
			if(y<=mid) return Qry(x,y,LT);if(x>mid) return Qry(x,y,RT);
			return Qry(x,mid,LT)+Qry(mid+1,y,RT);
		}
		I double Q(CI x,CI y)
		{
			node t=Qry(x,y);double f=t.xy-t.sx*t.sy/(y-x+1);
			double g=t.xx-t.sx*t.sx/(y-x+1);return f/g;//计算答案
		}
}S;
int main()
{
	RI Qt,i;scanf("%d%d",&n,&Qt);
	for(i=1;i<=n;++i) scanf("%d",x+i);for(i=1;i<=n;++i) scanf("%d",y+i);S.Build();
	RI op,l,r,s,t;W(Qt--) switch(scanf("%d%d%d",&op,&l,&r),op)
	{
		case 1:printf("%.10lf\n",S.Q(l,r));break;
		case 2:scanf("%d%d",&s,&t),S.U1(l,r,s,t);break;
		case 3:scanf("%d%d",&s,&t),S.U2(l,r,s,t);break;
	}return 0;
}
上一篇:要做的题


下一篇:树点涂色[SDOI2017]