如题。这是我的线段树
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
double Abs(double x) {return max(x, -x);}
int n, m;
double a[N + 10];
double sum[N * 4 + 10], squ[N * 4 + 10], add[N * 4 + 10];
int ls(int x) {
return 2 * x;
}
int rs(int x) {
return 2 * x + 1;
}
void push_up(int x) {
sum[x] = sum[ls(x)] + sum[rs(x)];
squ[x] = squ[ls(x)] + squ[rs(x)];
}
void push_tag(int x, int s, int t, double val) {
squ[x] = squ[x] + 2.0 * val * sum[x] +
(double)(t - s + 1) * val * val;
sum[x] = sum[x] + (double)(t - s + 1) * val;
add[x] += val;
}
void push_down(int x, int s, int t) {
if(Abs(add[x]) > 1e-7) {
int mid = (s + t) >> 1;
push_tag(ls(x), s, mid, add[x]);
push_tag(rs(x), mid + 1, t, add[x]);
add[x] = 0;
}
}
void update(int ql, int qr, int s, int t, int now, double val) {
if(ql <= s && t <= qr) {
push_tag(now, s, t, val);
return ;
}
int mid = (s + t) >> 1;
push_down(now, s, t);
if(ql <= mid) update(ql, qr, s, mid, ls(now), val);
if(qr > mid) update(ql, qr, mid + 1, t, rs(now), val);
push_up(now);
}
double query1(int ql, int qr, int s, int t, int now) {
if(ql <= s && t <= qr) return sum[now];
int mid = (s + t) >> 1;
double rest = 0;
push_down(now, s, t);
if(ql <= mid) rest += query1(ql, qr, s, mid, ls(now));
if(qr > mid) rest += query1(ql, qr, mid + 1, t, rs(now));
return rest;
}
double query2(int ql, int qr, int s, int t, int now) {
if(ql <= s && t <= qr) return squ[now];
int mid = (s + t) >> 1;
double rest = 0;
push_down(now, s, t);
if(ql <= mid) rest += query2(ql, qr, s, mid, ls(now));
if(qr > mid) rest += query2(ql, qr, mid + 1, t, rs(now));
return rest;
}
void build(int l, int r, int x) {
if(l == r) {
sum[x] = a[l];
squ[x] = a[l] * a[l];
return ;
}
int mid = (l + r) >> 1;
build(l, mid, ls(x));
build(mid + 1, r, rs(x));
push_up(x);
}
int main() {
cin >> n >> m;
for(int p = 1; p <= n; p++)
cin >> a[p];
build(1, n, 1);
for(int p = 1; p <= m; p++) {
int opt, l, r;
cin >> opt >> l >> r;
if(opt == 1) {
double val;
cin >> val;
update(l, r, 1, n, 1, val);
}
else if(opt == 2) {
double tmp = query1(l, r, 1, n, 1);
cout << fixed << setprecision(4) <<
(double)(tmp / (double)(r - l + 1)) << endl;
}
else if(opt == 3) {
double tmp = query1(l, r, 1, n, 1);
double bax = (double)(tmp / (double)(r - l + 1));
double pa2 = query2(l, r, 1, n, 1) / (double)(r - l + 1);
double pa3 = 2 * bax * tmp / (double)(r - l + 1);
cout << fixed << setprecision(4) <<
bax * bax + pa2 - pa3 << endl;
}
}
}
然后我又写了一份暴力对拍。我自己对拍的时候将 A 开到 1e5 然后精度就寄了,但是我试着交了一发这个线段树是能 AC 的,所以想问下这个怎么样才能让精度掉的少一点。对拍的暴力代码放在下面。
顺便请问这道题题面给了 A 范围嘛?QAQ 我没有看到