宁波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;
}
