P1471 0 pts 求助
  • 板块灌水区
  • 楼主Guoguo2013
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/2/2 15:25
  • 上次更新2025/2/2 21:09:49
查看原帖
P1471 0 pts 求助
1070982
Guoguo2013楼主2025/2/2 15:25

rt

#include<bits/stdc++.h>
#define int long long
#define PII pair< int, int >
#define lson rt << 1
#define rson rt << 1 | 1

using namespace std;

const int N = 1e6 + 5, mod = 998244353;
struct Node {
	double sum, lazy;
} s1[N], s2[N];
int n, m;
double a[N];

void push_up(int rt){
	s1[rt].sum = s1[lson].sum + s1[rson].sum;
	s2[rt].sum = s2[lson].sum + s2[rson].sum;
}
void build(int rt, int l, int r){
	s1[rt].lazy = 0;
	s2[rt].lazy = 0;
	if (l == r){
		s1[rt].sum = a[l];
		s2[rt].sum = a[l] * a[l];
		return ;
	}
	int mid = l + r >> 1ll;
	build(lson, l, mid);
	build(rson, mid + 1, r);
	push_up(rt);
//	printf("%lld %lld\n", rt, s[rt]);
}
void f1(int rt, int l, int r, int k){
	s1[rt].lazy += k;
	s1[rt].sum += (r - l + 1) * k;
}
void f2(int rt, int l, int r, int k){
	s2[rt].lazy += k;
	s2[rt].sum += 2 * k * s1[rt].sum + (r - l + 1) * k * k;
}
void push_down(int rt, int l, int r){
	int mid = l + r >> 1ll;
	f2(lson, l, mid, s2[rt].lazy);
	f2(rson, mid + 1, r, s2[rt].lazy);
	s2[rt].lazy = 0;
	f1(lson, l, mid, s1[rt].lazy);
	f1(rson, mid + 1, r, s1[rt].lazy);
	s1[rt].lazy = 0;
}
void update(int rt, int l, int r, int ql, int qr, double k){
	if (r < ql || l > qr) return ;
	if (ql <= l && r <= qr){
		f2(rt, l, r, k);
		f1(rt, l, r, k);
		return ;
	}
	push_down(rt, l, r);
	int mid = l + r >> 1ll;
	update(lson, l, mid, ql, qr, k);
	update(rson, mid + 1, r, ql, qr, k);
	push_up(rt);
}
double query1(int rt, int l, int r, int ql, int qr){
	if (r < ql || l > qr) return 0;
	if (ql <= l && r <= qr) return s1[rt].sum;
	int mid = l + r >> 1ll;
	push_down(rt, l, r);
	double ans = query1(lson, l, mid, ql, qr) + query1(rson, mid + 1, r, ql, qr);
	push_up(rt);
	return ans;
}
double query2(int rt, int l, int r, int ql, int qr){
	if (r < ql || l > qr) return 0;
	if (ql <= l && r <= qr) return s2[rt].sum;
	int mid = l + r >> 1ll;
	push_down(rt, l, r);
	double ans = query2(lson, l, mid, ql, qr) + query2(rson, mid + 1, r, ql, qr);
	push_up(rt);
	return ans;
}
template< typename T >inline void read(T &x){bool f=1;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=(f?x:-x);return;}
template< typename T, typename ... L > void read(T &a , L && ... b) { read(a); read(b ...); }
int ksm(int a, int b, int p){int ans = 1;while(b){if(b & 1)ans =(ans*a)%p;b >>= 1;a = (a*a) % p;}return ans;}
signed main(){
//	freopen("a.in", "r", stdin);
//	freopen("a.out","w",stdout);
	read(n, m);
	for (int i = 1; i <= n; i++) scanf("%lf", &a[i]);
	build(1, 1, n);
//    for (int i = 1; i <= 10; i++) printf("%.4lf ", s2[i].sum);
	for (int i = 1; i <= m; i++){
		int op, l, r;
        read(op, l, r);
        if (op == 1){
        	double k;
        	scanf("%lf", &k);
            update(1, 1, n, l, r, k);
        }
        else if (op == 2) printf("%.4lf\n", query1(1, 1, n, l, r) / (r - l + 1));
        else printf("%.4lf\n", query2(1, 1, n, l, r) / (r - l + 1) - (query1(1, 1, n, l, r) / (r - l + 1)) * (query1(1, 1, n, l, r) / (r - l + 1)));
    }
//    for (int i = 1; i <= 10; i++) printf("%.4lf ", s2[i].sum);
	return 0;
}
2025/2/2 15:25
加载中...