Description：

给出两个序列 $x[i]$ 和 $y[i]$ ，支持：

$1$ 、给定 $L,R$ ，查询： $$ \frac{\begin{align}\sum_{i=L}^R(x[i]-\overline x)(y[i]-\overline y)\end{align}}{\begin{align}\sum_{i=L}^R(x[i]-\overline x)^2\end{align}} $$ $2$ 、给定 $L,R,S,T$ ， $\forall i\in[L,R]\ \ x[i]=x[i]+S,y[i]=y[i]+T$

$2$ 、给定 $L,R,S,T$ ， $\forall i\in[L,R]\ \ x[i]=S+i,y[i]=T+i$

$1\leqslant n\leqslant 10^5$

Solution：

首先化一下上面的式子，发现其实是： $$ \frac {\begin{align}\sum_{i=L}^Rx[i]y[i]-\frac{\begin{align}\sum_{i=L}^Rx[i]\sum_{i=L}^Ry[i]\end{align}}{R-L+1}\end{align}} {\begin{align}\sum_{i=L}^Rx[i]^2-\frac{\begin{align}\sum_{i=L}^Rx[i]\sum_{i=L}^Rx[i]\end{align}}{R-L+1}\end{align}} $$ 所以线段树需要维护的东西是： $\sum x[i]y[i],\sum x[i],\sum y[i],\sum x[i]^2$ 。

区间加的话，二次项拆开就行，一次项直接加。

区间修改不太好做，因为二次项是一个等差数列对应相乘再求和，但是可以先提出来一个 $S'=S+l-1,T'=T+l-1$ 的操作，然后剩下的就是 $\begin{align}SUM=\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6\end{align}$ ，然后再做一个区间加就行了。 $\sum x[i]^2$ 也类似。

注意标记的顺序，如果是修改标记，那子树也是修改标记，如果是加标记，那么子树标记不变。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef double ll;

ll x[MAXN],y[MAXN];

struct node

{

	int lc,rc;

	ll x,y,xy,x2;

	ll xtag,ytag;

	int type;

	node(){type = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void merge(node &rt,node lc,node rc)

{

	rt.x = lc.x + rc.x;

	rt.y = lc.y + rc.y;

	rt.xy = lc.xy + rc.xy;

	rt.x2 = lc.x2 + rc.x2;

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].x = x[l];t[rt].y = y[l];

		t[rt].xy = x[l] * y[l];t[rt].x2 = x[l] * x[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

void addtag(int rt,ll xtag,ll ytag,int l,int r)

{

	ll len = r - l + 1;

	t[rt].xy += ytag * t[rt].x + xtag * t[rt].y + len * xtag * ytag;

	t[rt].x2 += 2 * xtag * t[rt].x + len * xtag * xtag;

	t[rt].x += xtag * len;t[rt].y += ytag * len;

	if(t[rt].type == 0)t[rt].type = 1;

	t[rt].xtag += xtag;t[rt].ytag += ytag;

	return;

}

void settag(int rt,ll xtag,ll ytag,int l,int r)

{

	ll len = r - l + 1;

	ll xv = xtag + l - 1,yv = ytag + l - 1;

	t[rt].xy = len * (len + 1) * (2 * len + 1) / 6;

	t[rt].x2 = len * (len + 1) * (2 * len + 1) / 6;

	t[rt].x = (1 + len) * len / 2;

	t[rt].y = (1 + len) * len / 2;

	addtag(rt,xv,yv,l,r);

	t[rt].type = 2;

	t[rt].xtag = xtag;t[rt].ytag = ytag;

	return;

}

void pushdown(int rt,int l,int r)

{

	if(t[rt].type == 0)return;

	int ll = l,lr = mid,rl = mid + 1,rr = r;

	if(t[rt].type == 2)

	{

		settag(t[rt].lc,t[rt].xtag,t[rt].ytag,ll,lr);

		settag(t[rt].rc,t[rt].xtag,t[rt].ytag,rl,rr);

	}

	if(t[rt].type == 1)

	{

		addtag(t[rt].lc,t[rt].xtag,t[rt].ytag,ll,lr);

		addtag(t[rt].rc,t[rt].xtag,t[rt].ytag,rl,rr);

	}

	t[rt].type = 0;t[rt].xtag = t[rt].ytag = 0;

	return;

}

void add(int rt,int L,int R,ll x,ll y,int l,int r)

{

	if(L <= l && r <= R)

	{

		addtag(rt,x,y,l,r);

		return;

	}

	pushdown(rt,l,r);

	if(L <= mid)add(t[rt].lc,L,R,x,y,l,mid);

	if(R > mid)add(t[rt].rc,L,R,x,y,mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

void set(int rt,int L,int R,ll x,ll y,int l,int r)

{

	if(L <= l && r <= R)

	{

		settag(rt,x,y,l,r);

		return;

	}

	pushdown(rt,l,r);

	if(L <= mid)set(t[rt].lc,L,R,x,y,l,mid);

	if(R > mid)set(t[rt].rc,L,R,x,y,mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

node query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt];

	pushdown(rt,l,r);

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	node res;

	merge(res,query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%lf",&x[i]);

	for(int i = 1;i <= n;++i)scanf("%lf",&y[i]);

	build(root,1,n);

	int opt,l,r;

	ll x,y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&opt,&l,&r);

		if(opt == 1)

		{

			node res = query(root,l,r,1,n);

			double ans = (res.xy - res.x * res.y / (r - l + 1)) / (res.x2 - res.x * res.x / (r - l + 1));

			printf("%.10lf\n",ans);

		}

		if(opt == 2)

		{

			scanf("%lf%lf",&x,&y);

			add(root,l,r,x,y,1,n);

		}

		if(opt == 3)

		{

			scanf("%lf%lf",&x,&y);

			set(root,l,r,x,y,1,n);

		}

	}

	return 0;

}