[SDOI2017] 相关分析题解

经验分享区
1

我们教练说这题只有绿
放题
我们要计算这个玩意：
a=\frac {\displaystyle\sum_{i=L}^{R}(x_i-\overline{x})(y_i-\overline{y}) }{\displaystyle\sum_{i=L}^{R}(x_i-\overline{x})^2}
打这个公式比较烦，而且应该比较容易化简，我就给一个最终式子了。
a=\frac {\displaystyle\sum_{i=L}^{R}x_iy_i-\frac{\displaystyle\sum_{i=L}^{R}x_i\displaystyle\sum_{i=L}^{R}y_i}{R-L+1} }{\displaystyle\sum_{i=L}^{R}x_i^2-\frac{(\displaystyle\sum_{i=L}^{R}x_i)^2}{R-L+1}}
然后我们用线段树维护一下 x,y,xy,x^2 就行了。
操作 2 没啥好说的。
操作 3 就是先做一次区间推平让 x_i=y_i=i ，然后在操作 2 。
下面看看 pushdown
首先存覆盖标记如果有的话区间推平。
然后看如何下传。
懒标记下传没啥好说的， x,y 的下传也简单。
xy 和 xx 的下传就是把 (x_i+s)(y_i+t)和(x_i+s)^2 化简你就知道了，这里请自己化简。
下面就很简单了 build update modify query 这三个函数和板子没啥两样，这里给出另外几个函数。

void cover(int l,int r,int now)
{
	tree[now].s=tree[now].t=0;
	tree[now].flag=1;
	tree[now].x=tree[now].y=(l+r)*(r-l+1)/2;
	tree[now].xy=tree[now].xx=r*(r+1)*(2*r+1)/6-(l-1)*l*(2*l-1)/6;
}
void lazy(int l,int r,int now,long double s,long double t)
{
	tree[now].s+=s;
	tree[now].t+=t;
	tree[now].xy+=t*tree[now].x+s*tree[now].y+s*t*(r-l+1);
	tree[now].xx+=2*s*tree[now].x+s*s*(r-l+1);
	tree[now].x+=s*(r-l+1);
	tree[now].y+=t*(r-l+1);
}
void push_up(int now)
{
	tree[now].x=tree[now*2].x+tree[now*2+1].x;
	tree[now].y=tree[now*2].y+tree[now*2+1].y;
	tree[now].xy=tree[now*2].xy+tree[now*2+1].xy;
	tree[now].xx=tree[now*2].xx+tree[now*2+1].xx;
}
void push_down(int l,int r,int now)
{
	if(tree[now].flag)
	{
		int mid=(l+r)/2;
		cover(l,mid,now*2);
		cover(mid+1,r,now*2+1);
		tree[now].flag=0;
	}
	int mid=(l+r)/2;
	lazy(l,mid,now*2,tree[now].s,tree[now].t);
	lazy(mid+1,r,now*2+1,tree[now].s,tree[now].t);
	tree[now].s=tree[now].t=0;
}

还有这题会爆 long long 建议直接用 double 或 long double，还有 long long 也要开哦。

题外话

我们本周模考三题分别是： 小凸玩密室， 兔子与樱花， 相关分析。
这是我第一次场切紫（T1，T3不是赛时做出的），够我吹半年了。
我们教练却说这三题让他评只有蓝绿绿。

1 个赞