loj2005 「SDOI2017」相关分析

鬼畜线段树……Orz Capella
#include <iostream>

#include <cstdio>

using namespace std;

int n, m, uu, vv, opt;

double xx[100005], yy[100005], ss, tt, faq[4];

struct SGT{

	double val[400005][4], stag[400005], ttag[400005];

	/*

	 * val[0]: x_i^2

	 * val[1]: x_i

	 * val[2]: y_i

	 * val[3]: x_i*y_i

	 */

	bool ismo[400005];

	void pushUp(int o, int lson, int rson){

		for(int i=0; i<4; i++)

			val[o][i] = val[lson][i] + val[rson][i];

	}

	double calc(int x){

		return (double)x*(x+1)*(2*x+1)/6.0;

	}

	void pushModify(int o, int l, int r){

		val[o][0] = val[o][3] = calc(r) - calc(l-1);

		val[o][1] = val[o][2] = (double)(l+r) * (r-l+1) / 2.0;

		ismo[o] = true;

		stag[o] = ttag[o] = 0.0;

	}

	void pushAdd(int o, int l, int r, double s, double t){

		int siz=r-l+1;

		val[o][0] += 2.0*s*val[o][1] + s*s*siz;

		val[o][3] += s*val[o][2] + t*val[o][1] + s*t*siz;

		val[o][1] += s * siz;

		val[o][2] += t * siz;

		stag[o] += s;

		ttag[o] += t;

	}

	void pushDown(int o, int l, int r, int lson, int rson, int mid){

		if(ismo[o]){

			if(l<=mid)	pushModify(lson, l, mid);

			if(mid<r)	pushModify(rson, mid+1, r);

		}

		if(l<=mid)	pushAdd(lson, l, mid, stag[o], ttag[o]);

		if(mid<r)	pushAdd(rson, mid+1, r, stag[o], ttag[o]);

		stag[o] = ttag[o] = ismo[o] = 0;

	}

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

		if(l==r){

			val[o][0] = xx[l] * xx[l];

			val[o][1] = xx[l]; val[o][2] = yy[l];

			val[o][3] = xx[l] * yy[l];

		}

		else{

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

			int lson=o<<1;

			int rson=lson|1;

			if(l<=mid)	build(lson, l, mid);

			if(mid<r)	build(rson, mid+1, r);

			pushUp(o, lson, rson);

		}

	}

	void update(int o, int l, int r, int x, int y, double s, double t){

		// printf("faQ\n");

		if(l>=x && r<=y)	pushAdd(o, l, r, s, t);

		else{

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

			int lson=o<<1;

			int rson=lson|1;

			pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	update(lson, l, mid, x, y, s, t);

			if(mid<y)	update(rson, mid+1, r, x, y, s, t);

			pushUp(o, lson, rson);

		}

	}

	void modify(int o, int l, int r, int x, int y, double s, double t){

		if(l>=x && r<=y){

			pushModify(o, l, r);

			pushAdd(o, l, r, s, t);

		}

		else{

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

			int lson=o<<1;

			int rson=lson|1;

			pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	modify(lson, l, mid, x, y, s, t);

			if(mid<y)	modify(rson, mid+1, r, x, y, s, t);

			pushUp(o, lson, rson);

		}

	}

	void query(int o, int l, int r, int x, int y){

		if(l>=x && r<=y){

			for(int i=0; i<4; i++)

				faq[i] += val[o][i];

		}

		else{

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

			int lson=o<<1;

			int rson=lson|1;

			pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	query(lson, l, mid, x, y);

			if(mid<y)	query(rson, mid+1, r, x, y);

		}

	}

}sgt;

double queryRange(int l, int r){

	for(int i=0; i<4; i++)	faq[i] = 0.0;

	sgt.query(1, 1, n, l, r);

	return (faq[3]-faq[1]*faq[2]/(r-l+1)) / (faq[0]-faq[1]*faq[1]/(r-l+1));

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++)

		scanf("%lf", &xx[i]);

	for(int i=1; i<=n; i++)

		scanf("%lf", &yy[i]);

	sgt.build(1, 1, n);

	while(m--){

		scanf("%d", &opt);

		if(opt==1){

			scanf("%d %d", &uu, &vv);

			printf("%.10f\n", queryRange(uu, vv));

		}

		else if(opt==2){

			scanf("%d %d %lf %lf", &uu, &vv, &ss, &tt);

			sgt.update(1, 1, n, uu, vv, ss, tt);

		}

		else{

			scanf("%d %d %lf %lf", &uu, &vv, &ss, &tt);

			sgt.modify(1, 1, n, uu, vv, ss, tt);

		}

	}

	return 0;

}
巴特西

loj2005 「SDOI2017」相关分析

最新文章

热门文章
