P3707 [SDOI2017]相关分析
斯德哥尔摩
2018-05-28 22:19:58
[P3707 [SDOI2017]相关分析](https://www.luogu.org/problemnew/show/P3707)
### 先讲一讲题外话
这题恐怕是继[P4246 [SHOI2008]堵塞的交通](https://www.luogu.org/problemnew/show/P4246)之后，又一道超级毒瘤的线段树题，比那[P2572 [SCOI2010]序列操作](https://www.luogu.org/problemnew/show/P2572)恶心多了。。。
看我提交记录就知道此题有多毒。。。
SHOI那题我还没敢做~~（未见其题，先闻其毒。。。）~~，这题我调了两晚上，SCOI那题我大概一上午不到就1A了。。。
### 步入正题
先分析**操作1**：
为了好解题，我们将$a$拆成两部分：$$a=\frac{s}{t}$$
再把所有要用到的变量设一下：$$s1=\sum_{i=L}^{R}x_i,s2=\sum_{i=L}^{R}y_i,s3=\sum_{i=L}^{R}x_iy_i,s4=\sum_{i=L}^{R}x_i^2,len=R-L+1$$
那么$s=\sum_{i=L}^{R}(x_i-\overline{x})(y_i-\overline{y}),t=\sum_{i=L}^{R}(x_i-\overline{x})^2$
拆开$s$：$$s=\sum_{i=L}^{R}(x_iy_i-\overline{x}y_i-\overline{y}x_i+\overline{x}\overline{y})$$
$$=\sum_{i=L}^{R}x_iy_i-\overline{x}\sum_{i=L}^{R}y_i-\overline{y}\sum_{i=L}^{R}x_i+(R-L+1)\overline{x}\overline{y}$$
又因为：$\overline{x}=\frac{1}{R-L+1}\sum_{i=L}^{R}x_i,\overline{y}=\frac{1}{R-L+1}\sum_{i=L}^{R}y_i$
所以：$$s=s3-\frac{s1s2}{len}-\frac{s1s2}{len}+\frac{s1s2}{len}$$
即：$$s=s3-\frac{s1s2}{len}$$
同理对$t$：$t=\sum_{i=L}^{R}(x_i-\overline{x})^2$
拆开：$$t=\sum_{i=L}^{R}x_i^2-2\overline{x}\sum_{i=L}^{R}x_i+(R-L+1)\overline{x}^2$$
那么：$$t=s4-\frac{s1^2}{len}$$
到此，$a$分析完毕。
那么怎么求$s1,s2,s3,s4$呢？
于是什么乱七八糟的数据结构都出来了——分块，树状数组，线段树，平衡树......
但是这里选用**线段树**。
因为有修改操作。
**操作2**：
这个操作相对比较简单：
$s1,s2$相对好做：$$s1+=S*(R-L+1)$$$$s2+=T*(R-L+1)$$
但是那个$s3,s4$怎么维护？
我们想这样变：$xy->(x+S)(y+T),x^2->(x+S)^2$
那就推式子啊，这个式子总比莫比乌斯反演好推吧。。。
于是：$$(x+S)(y+T)=xy+Sy+Tx+ST$$$$(x+S)^2=x^2+2xS+S^2$$
所以：
$$s3+=S* s2+T* s1+S* T* (R-L+1)$$
$$s4+=S*s1*2+S^2* (R-L+1)$$
这个问题就这样愉快地解决了。。。
**操作3**：
这个操作比较烦。。。有前置要求。。。
前置要求：（小学奥数/高中必修）
$$1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$
$$1+2+3+...+n=\frac{n(n+1)}{2}$$
对于赋值操作，我们可以拆开来：先将$[L,R]$中$x_i.y_i$全部改为$i$，再进行操作2。
定义两个函数：
$$sum(n)=1+2+3+...+n=\frac{n(n+1)}{2}$$
$$mul(n)=1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$
那么：
$$s1=s2=sum(R)-sum(L-1)=\frac{(L+R)(R-L+1)}{2}$$
$$s3=s4=mul(R)-mul(L-1)$$
所以添加一个区间赋值的懒惰标记即可。
记得打懒惰标记时，区间加的标记要清$0$，因为赋值使得前面所有的添加操作都无效了。
### 注意
这题理论上应该开$long\ long$，但是很奇怪的是开了$long\ long$反而过不了，而是开了位数不够大的$double$能过，也不知道出题人造了啥毁天灭地的数据。。。
话说$long\ double$表示不服呢（笑）。。。
所以这题都开$double$吧。。。
### 结语
到此，这个题目总算是分析完了，推式子累死我，调程序累死我，神TM打字打得我更累我也是没话说。。。
~~谁让出题人有一颗毒瘤的心呢。。。~~
省选场上遇到这种题，两种选择：要么交暴力/优化后的暴力，要么调正解代码，但是**不能虚**！**千万不要虚**！**一定不能虚**！一虚便会紧张啊，慌啊啥的，考试最忌紧张！最忌慌！上去就是一个字——**怼**！
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA1(x) a[x].data1
#define DATA2(x) a[x].data2
#define DATA3(x) a[x].data3
#define DATA4(x) a[x].data4
#define SIGN1(x) a[x].c1
#define SIGN2(x) a[x].c2
#define SIGN3(x) a[x].c3
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)
#define MAXN 100010
using namespace std;
int n,m;
double x[MAXN],y[MAXN];
struct Segment_Tree{
double data1,data2,data3,data4,c1,c2,c3;
int l,r;
}a[MAXN<<2];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline double sum(double l,double r){return ((l+r)*(r-l+1)/2.00);}
inline double mul(double l,double r){return (r*(r+1)*(r*2.00+1)/6.00-(l-1)*l*(l*2.00-1)/6.00);}//化简了一下两个式子
inline void pushup(int rt){
DATA1(rt)=DATA1(LSON)+DATA1(RSON);
DATA2(rt)=DATA2(LSON)+DATA2(RSON);
DATA3(rt)=DATA3(LSON)+DATA3(RSON);
DATA4(rt)=DATA4(LSON)+DATA4(RSON);
}
inline void pushdown(int rt){
if(LSIDE(rt)==RSIDE(rt))return;
if(SIGN3(rt)){
SIGN3(LSON)=1;SIGN1(LSON)=SIGN2(LSON)=0;
DATA1(LSON)=DATA2(LSON)=sum(LSIDE(LSON),RSIDE(LSON));
DATA3(LSON)=DATA4(LSON)=mul(LSIDE(LSON),RSIDE(LSON));
SIGN3(RSON)=1;SIGN1(RSON)=SIGN2(RSON)=0;
DATA1(RSON)=DATA2(RSON)=sum(LSIDE(RSON),RSIDE(RSON));
DATA3(RSON)=DATA4(RSON)=mul(LSIDE(RSON),RSIDE(RSON));
SIGN3(rt)=0;
}
if(SIGN1(rt)||SIGN2(rt)){
SIGN1(LSON)+=SIGN1(rt);SIGN2(LSON)+=SIGN2(rt);
DATA3(LSON)+=SIGN1(rt)*DATA2(LSON)+SIGN2(rt)*DATA1(LSON)+SIGN1(rt)*SIGN2(rt)*WIDTH(LSON);
DATA4(LSON)+=SIGN1(rt)*DATA1(LSON)*2+SIGN1(rt)*SIGN1(rt)*WIDTH(LSON);
DATA1(LSON)+=SIGN1(rt)*WIDTH(LSON);DATA2(LSON)+=SIGN2(rt)*WIDTH(LSON);
SIGN1(RSON)+=SIGN1(rt);SIGN2(RSON)+=SIGN2(rt);
DATA3(RSON)+=SIGN1(rt)*DATA2(RSON)+SIGN2(rt)*DATA1(RSON)+SIGN1(rt)*SIGN2(rt)*WIDTH(RSON);
DATA4(RSON)+=SIGN1(rt)*DATA1(RSON)*2+SIGN1(rt)*SIGN1(rt)*WIDTH(RSON);
DATA1(RSON)+=SIGN1(rt)*WIDTH(RSON);DATA2(RSON)+=SIGN2(rt)*WIDTH(RSON);
SIGN1(rt)=SIGN2(rt)=0;
}
}
void buildtree(int l,int r,int rt){
int mid;
LSIDE(rt)=l;
RSIDE(rt)=r;
SIGN1(rt)=SIGN2(rt)=SIGN3(rt)=0;
if(l==r){
DATA1(rt)=x[l];DATA2(rt)=y[l];DATA3(rt)=x[l]*y[l];DATA4(rt)=x[l]*x[l];
return;
}
mid=l+r>>1;
buildtree(l,mid,LSON);
buildtree(mid+1,r,RSON);
pushup(rt);
}
void update_add(int l,int r,double c,double d,int rt){
int mid;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
SIGN1(rt)+=c;SIGN2(rt)+=d;
DATA3(rt)+=c*DATA2(rt)+d*DATA1(rt)+c*d*WIDTH(rt);DATA4(rt)+=c*DATA1(rt)*2+c*c*WIDTH(rt);
DATA1(rt)+=c*WIDTH(rt);DATA2(rt)+=d*WIDTH(rt);
return;
}
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)update_add(l,r,c,d,LSON);
if(mid<r)update_add(l,r,c,d,RSON);
pushup(rt);
}
void update_all(int l,int r,int rt){
int mid;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
SIGN3(rt)=1;SIGN1(rt)=SIGN2(rt)=0;
DATA1(rt)=DATA2(rt)=sum(LSIDE(rt),RSIDE(rt));
DATA3(rt)=DATA4(rt)=mul(LSIDE(rt),RSIDE(rt));
return;
}
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)update_all(l,r,LSON);
if(mid<r)update_all(l,r,RSON);
pushup(rt);
}
double query_one(int l,int r,int rt){
int mid;
double ans=0.00;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA1(rt);
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans+=query_one(l,r,LSON);
if(mid<r)ans+=query_one(l,r,RSON);
return ans;
}
double query_two(int l,int r,int rt){
int mid;
double ans=0.00;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA2(rt);
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans+=query_two(l,r,LSON);
if(mid<r)ans+=query_two(l,r,RSON);
return ans;
}
double query_three(int l,int r,int rt){
int mid;
double ans=0.00;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA3(rt);
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans+=query_three(l,r,LSON);
if(mid<r)ans+=query_three(l,r,RSON);
return ans;
}
double query_four(int l,int r,int rt){
int mid;
double ans=0.00;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA4(rt);
pushdown(rt);
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans+=query_four(l,r,LSON);
if(mid<r)ans+=query_four(l,r,RSON);
return ans;
}
void work(){
int f,l,r;
double s,t;
while(m--){
f=read();l=read();r=read();
if(f==1){
double s1=query_one(l,r,1),s2=query_two(l,r,1),len=r-l+1;
double s3=query_three(l,r,1),s4=query_four(l,r,1);
s=s3-s1*s2/len;t=s4-s1*s1/len;
printf("%.10lf\n",s/t);
}
if(f==2){
scanf("%lf%lf",&s,&t);
update_add(l,r,s,t,1);
}
if(f==3){
scanf("%lf%lf",&s,&t);
update_all(l,r,1);
update_add(l,r,s,t,1);
}
}
}
void init(){
n=read();m=read();
for(int i=1;i<=n;i++)scanf("%lf",&x[i]);
for(int i=1;i<=n;i++)scanf("%lf",&y[i]);
buildtree(1,n,1);
}
int main(){
init();
work();
return 0;
}
```