40pts 求调
查看原帖
40pts 求调
669825
SpringFullGarden楼主2023/8/3 16:20

RT\text{RT}

#include <bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define ull unsigned long long
#define Pow(x) x * x
#define now tree[x]
#define lt tree[x << 1]
#define rt tree[x << 1 | 1] 
using namespace std;

struct node {
	ll l, r, len; 
	double sum, psum, lz;
} tree[414514];
ll n, m;
double s[114514];

void build(ll x, ll l, ll r) {
	ll ls = x << 1, rs = x << 1 | 1, mid = (l + r) >> 1;
	now.l = l, now.r = r, now.len = r - l + 1;
	if(l == r) {
		now.sum = s[l], now.psum = Pow(s[l]);
		return;
	}
	build(ls, l, mid), build(rs, mid + 1, r);
	now.sum = lt.sum + rt.sum, now.psum = lt.psum + rt.psum;
	return;
}
void down(ll x) {
	lt.lz += now.lz, rt.lz += now.lz;
	lt.psum += 2 * now.lz * now.sum + lt.len * Pow(now.lz);
	rt.psum += 2 * now.lz * now.sum + rt.len * Pow(now.lz);
	lt.sum += now.lz * lt.len, rt.sum += now.lz * rt.len;
	now.lz = 0;
	return;
}
void add(ll x, ll l, ll r, double num) {
	ll ls = x << 1, rs = x << 1 | 1;
	if(now.r < l || now.l > r) return;
	if(now.l >= l && now.r <= r) {
		now.psum += 2 * num * now.sum + now.len * Pow(num);
		now.sum += num * now.len;
		now.lz += num;
		return;
	}
	if(now.lz) down(x);
	add(ls, l, r, num), add(rs, l, r, num);
	now.sum = lt.sum + rt.sum, now.psum = lt.psum + rt.psum;
	return;
}
double sfind(ll x, ll l, ll r) {
	ll ls = x * 2ll, rs = x * 2ll + 1ll;
	if(now.r < l || tree[x].l > r) return 0;
	if(now.l >= l && tree[x].r <= r) return now.sum;
	if(now.lz) down(x);
	return sfind(ls, l, r) + sfind(rs, l, r);
}
double pfind(ll x, ll l, ll r) {
	ll ls = x << 1, rs = x << 1 | 1;
	if(now.r < l || now.l > r) return 0;
	if(now.l >= l && now.r <= r) return now.psum;
	if(now.lz) down(x);
	return pfind(ls, l, r) + pfind(rs, l, r);
}
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("%lld%lld", &n, &m);
	for(ll i = 1; i <= n; i++) scanf("%lf", &s[i]);
	build(1, 1, n);
	for(ll i = 1; i <= m; i++) {
		ll flag, l, r; double k;
		scanf("%lld%lld%lld", &flag, &l, &r);
		ll len = r - l + 1;
		if(flag == 1) scanf("%lf", &k), add(1, l, r, k);
		double pj = sfind(1, l, r) / len;
		if(flag == 2) printf("%.4lf\n", pj);
		if(flag == 3) {
			double pp = pfind(1, l, r) / len;
			printf("%.4lf\n", pp - Pow(pj));
		}
	}
	return 0;
} 
2023/8/3 16:20
加载中...