P3707 [SDOI2017]相关分析

线段树裸题？但是真的很麻烦QAQ

题目给的式子是什么不用管，大力拆开，就是\(\frac{\sum x_iy_i-\overline xy_i-\overline yx_i+\overline x\overline y}{\sum x_i^2-2x_i\overline x+\overline x^2}\)

然后发现需要维护\(\sum x,\sum y,\sum xy,\sum x^2\)

剩下的就是维护两个标记，具体自己推吧，懒得写了，看代码，咕咕咕咕

#include<bits/stdc++.h>

#define il inline

#define vd void

#define rg register

typedef long long ll;

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

struct data{double xy,x,y,x2;}s[400010];

il data operator +(const data&a,const data&b){return(data){a.xy+b.xy,a.x+b.x,a.y+b.y,a.x2+b.x2};}

bool lz0[400010],lz1[400010];

double lz0x[400010],lz0y[400010];

double lz1x[400010],lz1y[400010];

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

il double ssum(int x){return 0.50*x*(x+1);}

il double ssqr(int x){return 1.00/6*x*(x+1)*(x*2+1);}

il vd Overwrite(int x,int l,int r,double x0,double y0){

	lz1[x]=1,lz0[x]=0;lz1x[x]=x0,lz1y[x]=y0;

	s[x]=(data){x0*y0*(r-l+1)+(x0+y0)*ssum(r-l+1)+ssqr(r-l+1),x0*(r-l+1)+ssum(r-l+1),y0*(r-l+1)+ssum(r-l+1),x0*x0*(r-l+1)+ssqr(r-l+1)+ssum(r-l+1)*x0*2};

}

il vd Modify(int x,int l,int r,double x1,double y1){

	if(!lz0[x])lz0[x]=1,lz0x[x]=lz0y[x]=0;lz0x[x]+=x1,lz0y[x]+=y1;

	s[x]=s[x]+(data){s[x].x*y1+s[x].y*x1+x1*y1*(r-l+1),(r-l+1)*x1,(r-l+1)*y1,s[x].x*x1*2+x1*x1*(r-l+1)};

}

il vd down(int x,int l,int r){

	if(lz1[x])Overwrite(x<<1,l,mid,lz1x[x],lz1y[x]),Overwrite(x<<1|1,mid+1,r,lz1x[x]+(mid-l+1),lz1y[x]+(mid-l+1)),lz1[x]=0;

	if(lz0[x])Modify(x<<1,l,mid,lz0x[x],lz0y[x]),Modify(x<<1|1,mid+1,r,lz0x[x],lz0y[x]),lz0[x]=0;

}

double X[100010],Y[100010];

il vd build(int x,int l,int r){

	if(l==r){s[x]=(data){X[l]*Y[l],X[l],Y[l],X[l]*X[l]};return;}

	build(x<<1,l,mid),build(x<<1|1,mid+1,r);

	s[x]=s[x<<1]+s[x<<1|1];

}

il vd update_M(int x,int l,int r,const int&L,const int&R,const double&x0,const double&y0){

	if(L<=l&&r<=R)return Modify(x,l,r,x0,y0);

	down(x,l,r);

	if(L<=mid)update_M(x<<1,l,mid,L,R,x0,y0);

	if(mid<R)update_M(x<<1|1,mid+1,r,L,R,x0,y0);

	s[x]=s[x<<1]+s[x<<1|1];

}

il vd update_O(int x,int l,int r,const int&L,const int&R,const double&x0,const double&y0){

	if(L<=l&&r<=R)return Overwrite(x,l,r,x0,y0);

	down(x,l,r);

	if(L<=mid){

		update_O(x<<1,l,mid,L,R,x0,y0);

		if(mid<R)update_O(x<<1|1,mid+1,r,L,R,x0+(mid-std::max(l,L)+1),y0+(mid-std::max(l,L)+1));

	}else update_O(x<<1|1,mid+1,r,L,R,x0,y0);

	s[x]=s[x<<1]+s[x<<1|1];

}

il data query(int x,int l,int r,const int&L,const int&R){

	if(L<=l&&r<=R)return s[x];

	down(x,l,r);

	if(L<=mid)

		if(mid<R)return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);

		else return query(x<<1,l,mid,L,R);

	else return query(x<<1|1,mid+1,r,L,R);

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("3707.in","r",stdin);

	freopen("3707.out","w",stdout);

#endif

	int n=gi(),m=gi();

	for(rg int i=1;i<=n;++i)X[i]=gi();

	for(rg int i=1;i<=n;++i)Y[i]=gi();

	build(1,1,n);

	int o,l,r;double S,T;

	while(m--){

		o=gi();l=gi(),r=gi();

		if(o==1){

			data D=query(1,1,n,l,r);

			rg double px=D.x/(r-l+1),py=D.y/(r-l+1);

			printf("%.10lf\n",(D.xy-px*D.y-py*D.x+px*py*(r-l+1))/(D.x2-2*px*D.x+px*px*(r-l+1)));

		}else{

			S=gi(),T=gi();

			if(o==2)update_M(1,1,n,l,r,S,T);

			else update_O(1,1,n,l,r,S+l-1,T+l-1);

		}

	}

	return 0;

}

巴特西

P3707 [SDOI2017]相关分析

P3707 [SDOI2017]相关分析

最新文章

热门文章