[SDOI2017]相关分析
题目描述
Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。
Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。
现在Frank要分析参数$X$与$Y$之间的关系。他有$n$组观测数据，第ii组观测数据记录了$x_i$和$y_i$。他需要一下几种操作
- 1 $L,R$：
用直线拟合第$L$组到底$R$组观测数据。用$\overline{x}$表示这些观测数据中$x$的平均数，用$\overline{y}$表示这些观测数据中$y$的平均数，即
$\overline{x}={1 \over R-L+1} \sum _{i=L} ^R x_i$
$\overline{y}={1 \over R-L+1} \sum _{i=L} ^R y_i$
如果直线方程是$y=ax+b$，那么$a,b$应当这样计算：
$a={\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y})\over \sum _{i=L} ^R (x_i -\overline{x})^2}$
你需要帮助Frank计算$a$。
- 2 $L,R,S,T$：
Frank发现测量数据第$L$组到底$R$组数据有误差，对每个$i$满足$L \leq i \leq R$，$x_i$需要加上$S$，$y_i$需要加上$T$。
- 3 $L,R,S,T$：
Frank发现第$L$组到第$R$组数据需要修改，对于每个$i$满足$L \leq i \leq R$，$x_i$需要修改为$(S+i)$，$y_i$需要修改为$(T+i)$。
输入输出格式
输入格式：
第一行两个数$n,m$，表示观测数据组数和操作次数。
接下来一行$n$个数，第$i$个数是$x_i$。
接下来一行$n$个数，第$i$个数是$y_i$。
接下来$m$行，表示操作，格式见题目描述。
输出格式：
对于每个1操作，输出一行，表示直线斜率$a$。选手输出与标准输出的绝对误差或相对误差不超过$10^{-5}$即为正确。
输入输出样例
输入样例#1：
3 5
1 2 3
1 2 3
1 1 3
2 2 3 -3 2
1 1 2
3 1 2 2 1
1 1 3
输出样例#1：
1.0000000000
-1.5000000000
-0.6153846154
说明
对于20%的数据 $1 \leq n,m \leq 1000$
另有20%的数据，没有3操作，且2操作中$S=0$
另有30%的数据，没有3操作。
对于100%的数据，$1 \leq n,m \leq 10^5,0 \leq \vert S\vert ,\vert T\vert \leq 10^5,0 \leq \vert x_i\vert ,\vert y_i\vert \leq 10^5$
保证1操作不会出现分母为$0$的情况。
时间限制：1s
空间限制：128MB
题解
我真傻，真的，我以后再也不死劲压行了
遇到这种题求区间某个值首先想到线段树……
仔细看看修改操作和查询操作发现只用维护$\sum x,\sum y,\sum x^2,\sum x\times y$就行了，为了好维护操作$3$可以维护$\sum i,\sum i^2$
然后因为手抖写错了一个标记下推（把第一个标记多清$0$了一次，影响好像只有在大数据中才能体现出来），又因为在一个函数里所以压成了长长的一行，然后调了$3$个小时死活调不出来……
然后偶然把光标往后拖到底……
我再也不压这么长的行了.jpg
用long long存好像会被卡精度？
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL double
using namespace std;
const int MAX=1e5+5;
struct p{
LL x,y,xy,xx,ii,i,tagx,tagy,_tagx,_tagy;
}s[MAX<<2];
int n,m;
int X[MAX],Y[MAX];
p operator+ (p a,p b) {return (p){a.x+b.x,a.y+b.y,a.xy+b.xy,a.xx+b.xx,a.ii+b.ii,a.i+b.i,0,0,-1e6,-1e6};}
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
void pus(int k) {s[k]=s[tl]+s[tr];}
void build(int l=1,int r=n,int k=1)
{
s[k]._tagx=s[k]._tagy=-1e6;
if(l==r) return void(s[k]=(p){X[l],Y[l],1ll*X[l]*Y[l],1ll*X[l]*X[l],1ll*l*l,l,0,0,-1e6,-1e6});
build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
void GET_ADD(int l,int r,int k,LL S,LL T) {s[k].xy+=S*s[k].y+T*s[k].x+(r-l+1)*S*T,s[k].xx+=2*S*s[k].x+(r-l+1)*S*S,s[k].x+=(r-l+1)*S,s[k].y+=(r-l+1)*T,s[k].tagx+=S,s[k].tagy+=T;}
void GET_COV(int l,int r,int k,LL S,LL T) {s[k].xy=(r-l+1)*S*T+s[k].i*(S+T)+s[k].ii,s[k].xx=(r-l+1)*S*S+2*s[k].i*S+s[k].ii,s[k].x=(r-l+1)*S+s[k].i,s[k].y=(r-l+1)*T+s[k].i,s[k]._tagx=S,s[k]._tagy=T,s[k].tagx=s[k].tagy=0;}
void down(int l,int r,int k)
{
if(l==r) return;
LL Fs,Ft;
if(s[k]._tagx!=-1e6) Fs=s[k]._tagx,Ft=s[k]._tagy,s[k]._tagx=s[k]._tagy=-1e6,GET_COV(l,mid,tl,Fs,Ft),GET_COV(mid+1,r,tr,Fs,Ft);
if(s[k].tagx||s[k].tagy) Fs=s[k].tagx,Ft=s[k].tagy,s[k].tagx=s[k].tagy=0,GET_ADD(l,mid,tl,Fs,Ft),GET_ADD(mid+1,r,tr,Fs,Ft);
}
void change(int l,int r,int k,int L,int R,int S,int T)
{
if(r<L||R<l) return;
if(l>=L&&r<=R) return void(GET_ADD(l,r,k,S,T));
down(l,r,k),change(l,mid,tl,L,R,S,T),change(mid+1,r,tr,L,R,S,T),pus(k);
}
void change_(int l,int r,int k,int L,int R,int S,int T)
{
if(r<L||R<l) return;
if(l>=L&&r<=R) return void(GET_COV(l,r,k,S,T));
down(l,r,k),change_(l,mid,tl,L,R,S,T),change_(mid+1,r,tr,L,R,S,T),pus(k);
}
p ask(int l,int r,int k,int L,int R)
{
if(l==L&&r==R) return s[k];
down(l,r,k);
if(R<=mid) return ask(l,mid,tl,L,R);
if(L>mid) return ask(mid+1,r,tr,L,R);
return ask(l,mid,tl,L,mid)+ask(mid+1,r,tr,mid+1,R);
}
double GET_ANS(int l,int r)
{
p x=ask(1,n,1,l,r);
double _x=double(x.x)/double(r-l+1),_y=double(x.y)/double(r-l+1),Up=double(x.xy)-_y*x.x-_x*x.y+double(r-l+1)*_x*_y,Down=double(x.xx)-2*_x*x.x+double(r-l+1)*_x*_x;
return Up/Down;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
X[i]=read();
for(int i=1;i<=n;++i)
Y[i]=read();
build();
for(int i=1,op,l,r,S,T;i<=m;++i)
{
op=read(),l=read(),r=read();
if(op==1) printf("%.10lf\n",GET_ANS(l,r));
else
{
S=read(),T=read();
if(op==2) change(1,n,1,l,r,S,T);
else if(op==3) change_(1,n,1,l,r,S,T);
}
}
return 0;
}
