求调,悬关,大概知道不会有人帮我调屎山
查看原帖
求调,悬关,大概知道不会有人帮我调屎山
557781
ruojiyz楼主2023/11/11 15:08
#include <bits/stdc++.h>
using namespace std; 

#define ls p << 1
#define rs p << 1 | 1
#define db double
const int N = 1e5 + 5;

int n, q, a[N], b[N], op, ql, qr; db c, d, fz, fm;
//x x的和 x2 x^2的和 y y的和 y2 y^2的和 xy (x+y)^2的和
struct tree{ db x, x2, y, y2, xy, S1, T1, S2, T2, len; } t[N << 2];

inline void pushup(int p)
{
	t[p].x = t[ls].x + t[rs].x;
	t[p].x2 = t[ls].x2 + t[rs].x2;
	t[p].y = t[ls].y + t[rs].y;
	t[p].y2 = t[ls].y2 + t[rs].y2;
	t[p].xy = t[ls].xy + t[rs].xy;
}

inline void pushdown(int l, int r, int p)
{
	int m = (l + r) >> 1;
	if(t[p].S2 != N && t[p].T2 != N)
	{
		t[ls].x = t[ls].len * t[p].S2 + (l + m) * t[ls].len / 2;
		t[ls].x2 = t[ls].len * t[p].S2 * t[p].S2 + t[p].S2 * (l + m) * t[ls].len + (m * (m + 1) * (2 * m + 1) - (l - 1) * l * (2 * l - 1)) / 6;
		t[ls].y = t[ls].len * t[p].T2 + (l + m) * t[ls].len / 2;
		t[ls].y2 = t[ls].len * t[p].T2 * t[p].T2 + t[p].T2 * (l + m) * t[ls].len + (m * (m + 1) * (2 * m + 1) - (l - 1) * l * (2 * l - 1)) / 6;
		t[ls].xy = t[ls].len * (t[p].S2 + t[p].T2) * (t[p].S2 + t[p].T2) + (t[p].S2 + t[p].T2) * (l + m) * t[ls].len + (m * (m + 1) * (2 * m + 1) - (l - 1) * l * (2 * l - 1)) / 6;
		
		t[rs].x = t[rs].len * t[p].S2 + (m + 1 + r) * t[rs].len / 2;
		t[rs].x2 = t[rs].len * t[p].S2 * t[p].S2 + t[p].S2 * (m + 1 + r) * t[rs].len + (r * (r + 1) * (2 * r + 1) - m * (m + 1) * (2 * m + 1)) / 6;
		t[rs].y = t[rs].len * t[p].T2 + (m + 1 + r) * t[rs].len / 2;
		t[rs].y2 = t[rs].len * t[p].T2 * t[p].T2 + t[p].T2 * (m + 1 + r) * t[rs].len + (r * (r + 1) * (2 * r + 1) - m * (m + 1) * (2 * m + 1)) / 6;
		t[rs].xy = t[rs].len * (t[p].S2 + t[p].T2) * (t[p].S2 + t[p].T2) + (t[p].S2 + t[p].T2) * (m + 1 + r) * t[rs].len + (r * (r + 1) * (2 * r + 1) - m * (m + 1) * (2 * m + 1)) / 6;	
		
		t[ls].S1 = t[rs].T1 = 0; t[ls].S2 = t[rs].S2 = t[p].S2; t[ls].T2 = t[rs].T2 = t[p].T2; t[p].S2 = t[p].T2 = N;	
	}	
	if(t[p].S1 != 0 || t[p].T1 != 0)
	{
		t[ls].xy += (t[ls].x + t[ls].y) * (t[p].S1 + t[p].T1) * 2 + t[ls].len * (t[p].S1 + t[p].T1) * (t[p].S1 + t[p].T1);
		t[ls].x2 += t[ls].x * t[p].S1 * 2 + t[ls].len * t[p].S1 * t[p].S1; 
		t[ls].x += t[ls].len * t[p].S1;
		t[ls].y2 += t[ls].y * t[p].T1 * 2 + t[ls].len * t[p].T1 * t[p].T1;
		t[ls].y += t[ls].len * t[p].T1;

		t[rs].xy += (t[rs].x + t[rs].y) * (t[p].S1 + t[p].T1) * 2 + t[rs].len * (t[p].S1 + t[p].T1) * (t[p].S1 + t[p].T1);
		t[rs].x2 += t[rs].x * t[p].S1 * 2 + t[rs].len * t[p].S1 * t[p].S1; 
		t[rs].x += t[rs].len * t[p].S1;
		t[rs].y2 += t[rs].y * t[p].T1 * 2 + t[rs].len * t[p].T1 * t[p].T1;
		t[rs].y += t[rs].len * t[p].T1;
		
		t[ls].S1 += t[p].S1; t[rs].S1 += t[p].S1; t[ls].T1 += t[p].T1; t[rs].T1 += t[p].T1; t[p].S1 = t[p].T1 = 0;
	}
}

inline void build(int l, int r, int p)
{
	t[p].S2 = t[p].T2 = N;
	if(l == r)
	{
		t[p].x = a[l];
		t[p].x2 = a[l] * a[l];
		t[p].y = b[l];
		t[p].y2 = b[l] * b[l];
		t[p].xy = (a[l] + b[l]) * (a[l] + b[l]);
		t[p].len = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls);
	build(mid + 1, r, rs);
	pushup(p);
	t[p].len = t[ls].len + t[rs].len;
}

inline tree ask(int l, int r, int p)
{
	if(ql <= l && r <= qr) return t[p];
	pushdown(l, r, p);
	int mid = (l + r) >> 1;
	if(ql > mid) return ask(mid + 1, r, rs);
	if(qr <= mid) return ask(l, mid, ls);
	tree res, r1 = ask(l, mid, ls), r2 = ask(mid + 1, r, rs);
	res.x = r1.x + r2.x;
	res.x2 = r1.x2 + r2.x2;
	res.y = r1.y + r2.y;
	res.y2 = r1.y2 + r2.y2;
	res.xy = r1.xy + r2.xy;
	return res;
}

void modify(int l, int r, int p)
{
	if(ql <= l && r <= qr)
	{
		t[p].xy += (t[p].x + t[p].y) * (c + d) * 2 + t[p].len * (c + d) * (c + d);
		t[p].x2 += t[p].x * c * 2 + t[p].len * c * c; 
		t[p].x += t[p].len * c;
		t[p].y2 += t[p].y * d * 2 + t[p].len * d * d;
		t[p].y += t[p].len * d;
		t[p].S1 += c; t[p].T1 += d;
		return; 
	}
	pushdown(l, r, p);
	int mid = (l + r) >> 1;
	if(ql <= mid) modify(l, mid, ls);
	if(qr > mid) modify(mid + 1, r, rs);
	pushup(p); 
}

void change(int l, int r, int p)
{
	if(ql <= l && r <= qr)
	{
		t[p].x = t[p].len * c + (l + r) * t[p].len / 2;
		t[p].x2 = t[p].len * c * c + c * (l + r) * t[p].len + (r * (r + 1) * (2 * r + 1) - (l - 1) * l * (2 * l - 1)) / 6;
		t[p].y = t[p].len * d + (l + r) * t[p].len / 2;
		t[p].y2 = t[p].len * d * d + d * (l + r) * t[p].len + (r * (r + 1) * (2 * r + 1) - (l - 1) * l * (2 * l - 1)) / 6;
		t[p].xy = t[p].len * (c + d) * (c + d) + (c + d) * (l + r) * t[p].len + (r * (r + 1) * (2 * r + 1) - (l - 1) * l * (2 * l - 1)) / 6; 	
		t[p].S2 = c; t[p].T2 = d; t[p].S1 = t[p].T1 = 0;
		return;	
	}
	pushdown(l, r, p);
	int mid = (l + r) >> 1;
	if(ql <= mid) change(l, mid, ls);
	if(qr > mid) change(mid + 1, r, rs);
	pushup(p);
}

int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	for(int i = 1 ; i <= n ; i ++) cin >> b[i];
	build(1, n, 1);
	while(q --)
	{
		cin >> op;
		if(op == 1)
		{
			cin >> ql >> qr;
			int t = qr - ql + 1;
			tree ans = ask(1, n, 1);
			fz = t * (ans.xy - ans.x2 - ans.y2) / 2 - ans.x * ans.y;
			fm = t * ans.x2 - ans.x * ans.x;
			printf("%.10lf\n", fz / fm);
		}
		else
		{
			cin >> ql >> qr >> c >> d;
			if(op == 2) modify(1, n, 1);
			else change(1, n, 1);
		}
	}

    return 0;
}

2023/11/11 15:08
加载中...