建站系统主要包括,品牌seo公司,建设部网站四库一平台,西安行业网站思路#xff1a;
首先他是实数 线段树结构#xff1a; 每个节点存储三个关键值#xff1a;区间和sum、区间平方和sum2、延迟标记lazy。sum用于计算区间平均数#xff0c;sum2和sum一起用于计算区间方差。 延迟标记优化#xff1a; 当需要更新一个区间时#xff0c;不立… 思路
首先他是实数 线段树结构 每个节点存储三个关键值区间和sum、区间平方和sum2、延迟标记lazy。sum用于计算区间平均数sum2和sum一起用于计算区间方差。 延迟标记优化 当需要更新一个区间时不立即更新所有子节点而是将更新操作存储在延迟标记中。当需要访问某个节点时先将延迟标记下传到子节点确保数据的正确性。 方差计算 方差公式利用线段树维护的sum和sum2可以高效计算这两个部分。
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includebits/stdc.h
using namespace std;
int n, m;
struct {double sum;double lazy;double sum2;
} a[400005];
double b[100005];
void Chu(int x, int y, int i) {if (x y) {a[i].sum b[x];a[i].sum2 pow(b[x], 2);a[i].lazy 0;return;}int mid (x y) / 2;Chu(x, mid, i * 2);Chu(mid 1, y, i * 2 1);a[i].sum2 a[i * 2].sum2 a[i * 2 1].sum2;a[i].sum a[i * 2].sum a[i * 2 1].sum;a[i].lazy 0;
}
void Xiu(int x, int y, int i, int l, int r, double k) {if (l x y r) {a[i].sum2 2 * a[i].sum * k (y - x 1) * pow(k, 2);a[i].sum k * (y - x 1);a[i].lazy k;return;}int mid (x y) / 2;if (a[i].lazy ! 0) {a[i * 2].sum2 2 * a[i * 2].sum * a[i].lazy (mid - x 1) * pow(a[i].lazy, 2);a[i * 2].sum a[i].lazy * (mid - x 1);a[i * 2].lazy a[i].lazy;a[i * 2 1].sum2 2 * a[i * 2 1].sum * a[i].lazy (y - mid) * pow(a[i].lazy, 2);a[i * 2 1].sum a[i].lazy * (y - mid);a[i * 2 1].lazy a[i].lazy;a[i].lazy 0;}if (mid l) {Xiu(x, mid, i * 2, l, r, k);}if (mid 1 r) {Xiu(mid 1, y, i * 2 1, l, r, k);}a[i].sum2 a[i * 2].sum2 a[i * 2 1].sum2;a[i].sum a[i * 2].sum a[i * 2 1].sum;
}
double Chasum(int x, int y, int i, int l, int r) {if (l x y r) {return a[i].sum;}int mid (x y) / 2;if (a[i].lazy ! 0) {a[i * 2].sum2 2 * a[i * 2].sum * a[i].lazy (mid - x 1) * pow(a[i].lazy, 2);a[i * 2].sum a[i].lazy * (mid - x 1);a[i * 2].lazy a[i].lazy;a[i * 21].sum2 2 * a[i * 21].sum * a[i].lazy (y-mid) * pow(a[i].lazy, 2);a[i * 2 1].sum a[i].lazy * (y - mid);a[i * 2 1].lazy a[i].lazy;a[i].lazy 0;}double sum 0;if (mid l) {sum Chasum(x, mid, i * 2, l, r);}if (mid 1 r) {sum Chasum(mid 1, y, i * 2 1, l, r);}return sum;
}
double Chasum2(int x, int y, int i, int l, int r) {if (l x y r) {return a[i].sum2;}int mid (x y) / 2;if (a[i].lazy ! 0) {a[i * 2].sum2 2 * a[i * 2].sum * a[i].lazy (mid - x 1) * pow(a[i].lazy, 2);a[i * 2].sum a[i].lazy * (mid - x 1);a[i * 2].lazy a[i].lazy;a[i * 2 1].sum2 2 * a[i * 2 1].sum * a[i].lazy (y - mid) * pow(a[i].lazy, 2);a[i * 2 1].sum a[i].lazy * (y - mid);a[i * 2 1].lazy a[i].lazy;a[i].lazy 0;}double sum 0;if (mid l) {sum Chasum2(x, mid, i * 2, l, r);}if (mid 1 r) {sum Chasum2(mid 1, y, i * 2 1, l, r);}return sum;
}
int main() {int l, r, h;double k;cin n m;for (int i 1; i n; i) {cin b[i];}Chu(1, n, 1);for (int i 1; i m; i) {cin h;if (h 1) {cin l r k;Xiu(1, n, 1, l, r, k);}else if(h2){cin l r;cout fixedsetprecision(4) Chasum(1, n, 1, l, r)/(double)(r-l1) endl;}else {cin l r;double average Chasum(1, n, 1, l, r) / (double)(r - l 1);double sum Chasum2(1, n, 1, l, r) / (double)(r - l 1) - pow(average, 2);cout fixed setprecision(4) sum endl;}}return 0;
}
