SDOI2017相关分析线段树

题目

https://loj.ac/problem/2005

思路

\[\sum_{L}^{R}{(x_i-x)^{2}}
\]

\[\sum_{L}^{R}{(x_i^2-2*x_i*x+x^{2})}
\]

\[\sum_{L}^{R}{x_i^2}-2*x*\sum_{L}^{R}x_i+(r-l+1)x^{2}
\]

\[\sum_{L}^{R}x_{i}^2-2*\frac{1}{r-l+1}(\sum_{L}^{R}x_i)^2+\frac{1}{r-l+1}*(\sum_{L}^{R}x)^2
\]

\[\sum_{L}^{R}x_{i}*x_{i}-\frac{1}{r-l+1}\sum_{L}^{R}x_i*\sum_{L}^{R}x_i
\]

\[\sum_{L}^{R}(x_i-x)(y_i-y)
\]

\[\sum_{L}^{R}(x_i*y_i-x*y_i-y*x_i+x*y)
\]

\[\sum_{L}^{R}x_i*y_i-\sum_{L}^{R}x_i*y-\sum_{L}^{R}y_i*x+(r-l+1)*x*y
\]

\[\sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i-\frac{1}{r-l+1}\sum_{L}^{R}*x_i\sum_{L}^{R}y_i+(r-l+1)*x*y
\]

\[\sum_{L}^{R}x_i*y_i-\frac{2}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i+\frac{1}{(r-l+1)}\sum_{L}^{R}x_i*\sum_{L}^{R}y_i
\]

\[\sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i
\]

\[\frac{\sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i}{\sum_{L}^{R}x_{i}*x_{i}-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}x_i}
\]

其实不用这么麻烦的、、

好了，剩下的去维护吧

好吧，我太菜了

要开long doule

代码

#include <bits/stdc++.h>

#define ll long double

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

const int N=2e5+7;

int read() {

    int x=0,f=1;char s=getchar();

    for (;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for (;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

ll x[N],y[N];

struct node {

	int l,r,siz;

	ll tot[2],pingfang,chengji;

	ll lazy,S,T;

}e[N<<2];

void pushup(int rt) {

	e[rt].tot[0]=e[ls].tot[0]+e[rs].tot[0];

	e[rt].tot[1]=e[ls].tot[1]+e[rs].tot[1];

	e[rt].pingfang=e[ls].pingfang+e[rs].pingfang;

	e[rt].chengji=e[ls].chengji+e[rs].chengji;

}

ll calc(int x) {return (ll)x*(x+1)/2;};

ll calc2(int x) {return (ll)x*(x+1)/2*(2*x+1)/3;};

void pushdown(int rt) {

	if(e[rt].lazy) {

		e[ls].tot[0]=e[ls].tot[1]=calc(e[ls].r)-calc(e[ls].l-1);

		e[ls].pingfang=e[ls].chengji=calc2(e[ls].r)-calc2(e[ls].l-1);

		e[ls].S=e[ls].T=0;

		e[ls].lazy=1;

		e[rs].tot[0]=e[rs].tot[1]=calc(e[rs].r)-calc(e[rs].l-1);

		e[rs].pingfang=e[rs].chengji=calc2(e[rs].r)-calc2(e[rs].l-1);

		e[rs].S=e[rs].T=0;

		e[rs].lazy=1;

		e[rt].lazy=0;

	}

	if(e[rt].S||e[rt].T) {

		e[ls].chengji+=e[ls].tot[0]*e[rt].T+e[ls].tot[1]*e[rt].S+e[rt].S*e[rt].T*e[ls].siz;

		e[ls].pingfang+=e[ls].tot[0]*2*e[rt].S+e[rt].S*e[rt].S*e[ls].siz;

		e[ls].tot[0]+=e[ls].siz*e[rt].S;

		e[ls].tot[1]+=e[ls].siz*e[rt].T;

		e[ls].S+=e[rt].S;

		e[ls].T+=e[rt].T;

		e[rs].chengji+=e[rs].tot[0]*e[rt].T+e[rs].tot[1]*e[rt].S+e[rt].S*e[rt].T*e[rs].siz;

		e[rs].pingfang+=e[rs].tot[0]*2*e[rt].S+e[rt].S*e[rt].S*e[rs].siz;

		e[rs].tot[0]+=e[rs].siz*e[rt].S;

		e[rs].tot[1]+=e[rs].siz*e[rt].T;

		e[rs].S+=e[rt].S;

		e[rs].T+=e[rt].T;

		e[rt].S=e[rt].T=0;

	}

}

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

	e[rt].l=l,e[rt].r=r,e[rt].siz=r-l+1;

	if(l==r) {

		e[rt].tot[0]=x[l];

		e[rt].tot[1]=y[l];

		e[rt].pingfang=x[l]*x[l];

		e[rt].chengji=x[l]*y[l];

		return;

	}

	int mid=(l+r)>>1;

	build(l,mid,ls);

	build(mid+1,r,rs);

	pushup(rt);

}

void modify_1(int L,int R,ll S,ll T,int rt) {

	if(L<=e[rt].l&&e[rt].r<=R) {

		e[rt].chengji+=e[rt].tot[0]*T+e[rt].tot[1]*S+S*T*e[rt].siz;

		e[rt].pingfang+=e[rt].tot[0]*2*S+S*S*e[rt].siz;

		e[rt].tot[0]+=e[rt].siz*S;

		e[rt].tot[1]+=e[rt].siz*T;

		e[rt].S+=S;

		e[rt].T+=T;

		return;

	}

	pushdown(rt);

	int mid=(e[rt].l+e[rt].r)>>1;

	if(L<=mid) modify_1(L,R,S,T,ls);

	if(R>mid) modify_1(L,R,S,T,rs);

	pushup(rt);

}

void modify_2(int L,int R,int rt) {

	if(L<=e[rt].l&&e[rt].r<=R) {

		e[rt].tot[0]=e[rt].tot[1]=calc(e[rt].r)-calc(e[rt].l-1);

		e[rt].pingfang=e[rt].chengji=calc2(e[rt].r)-calc2(e[rt].l-1);

		e[rt].S=e[rt].T=0;

		e[rt].lazy=1;

		return;

	}

	pushdown(rt);

	int mid=(e[rt].l+e[rt].r)>>1;

	if(L<=mid) modify_2(L,R,ls);

	if(R>mid) modify_2(L,R,rs);

	pushup(rt);

}

ll query(int L,int R,int opt,int rt) {

	if(L<=e[rt].l&&e[rt].r<=R) {

		if(opt==0) return e[rt].tot[0];

		if(opt==1) return e[rt].tot[1];

		if(opt==2) return e[rt].pingfang;

		if(opt==3) return e[rt].chengji;

	}

	pushdown(rt);

	int mid=(e[rt].l+e[rt].r)>>1;

	ll ans=0;

	if(L<=mid) ans+=query(L,R,opt,ls);

	if(R>mid) ans+=query(L,R,opt,rs);

	pushup(rt);

	return ans;

}

int main() {

	int 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(1,n,1);

	while(m--) {

		int opt=read(),L=read(),R=read();

		if(opt==1) {

			ll tot_x=query(L,R,0,1);

			ll tot_y=query(L,R,1,1);

			ll tot_x_x=query(L,R,2,1);

			ll tot_x_y=query(L,R,3,1);

			long double a=tot_x_y-tot_x*tot_y/(R-L+1);

			long double b=tot_x_x-tot_x*tot_x/(R-L+1);

			printf("%.10Lf\n",(long double)a/b);

		} else if(opt==2) {

			ll S=read(),T=read();

			modify_1(L,R,(ll)S,(ll)T,1);

		} else {

			ll S=read(),T=read();

			modify_2(L,R,1);

			modify_1(L,R,(ll)S,(ll)T,1);

		}

	}

	return 0;

}

巴特西

SDOI2017相关分析线段树

题目

思路

代码

最新文章

热门文章

巴特西

SDOI2017相关分析 线段树

题目

思路

代码

最新文章

热门文章

SDOI2017相关分析线段树