我的代码:
#include <bits/stdc++.h>
using namespace std;
using db = double;
const int R = 1e5 + 10;
db a[R];
#define lc k << 1
#define rc k << 1 | 1
struct Node
{
int l, r;
db sum, sum1, tag; // 一个维护a1+a2+...+an,一个维护a1^2+a2^2+...+an^2
} s[R << 2];
void pushup(int k)
{
s[k].sum = s[lc].sum + s[rc].sum;
s[k].sum1 = s[lc].sum1 + s[rc].sum1;
}
void add(int k, db val)
{
s[k].tag += val;
s[k].sum1 += 2 * val * s[k].sum + db(s[k].r - s[k].l + 1) * val * val; // 有依赖,所以先处理平方和
s[k].sum += val * db(s[k].r - s[k].l + 1);
}
void pushdown(int k)
{ // 为什么lazytag的值和已经加上的值要同时存在?思考一下叶子结点就行了。如果update到了叶子结点,那么叶子结点的值就永远不会被更新
// 试验后发现,如果对叶子结点进行过add,那么它的tag就不会被清零,但是也不会影响结果
if (s[k].tag)
{
add(lc, s[k].tag);
add(rc, s[k].tag);
s[k].tag = 0;
}
}
void build(int k, int l, int r)
{
s[k].l = l;
s[k].r = r;
if (l == r)
{
s[k].sum = a[l];
s[k].sum1 = a[l] * a[l];
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(k);
}
void update(int k, int x, int y, db val)
{
// if (s[k].l < x || s[k].r > y)
// return;
if (s[k].l >= x && s[k].r <= y)
{
add(k, val);
return;
}
pushdown(k);
int mid = (s[k].l + s[k].r) >> 1;
// update(lc, x, y, val);
// update(rc, x, y, val);
if (x <= s[k].l)
update(lc, x, y, val);
if (y > s[k].r)
update(rc, x, y, val);
pushup(k);
}
db query1(int k, int x, int y)
{
// if (s[k].l < x || s[k].r > y)
// return 0;
if (s[k].l >= x && s[k].r <= y)
return s[k].sum;
int mid = (s[k].l + s[k].r) >> 1;
pushdown(k);
db res = 0;
// res = query1(lc, x, y) + query1(rc, x, y);
if (x <= mid)
res = query1(lc, x, y);
if (y > mid)
res += query1(rc, x, y);
return res;
}
db query2(int k, int x, int y)
{
// if (s[k].l < x || s[k].r > y)
// return 0;
if (s[k].l >= x && s[k].r <= y)
return s[k].sum1;
int mid = (s[k].l + s[k].r) >> 1;
pushdown(k);
db res = 0;
if (x <= mid)
res = query2(lc, x, y);
if (y > mid)
res += query2(rc, x, y);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, l, r, t;
cin >> n >> m;
int j;
for (j = 1; j <= n; ++j)
{
cin >> a[j];
}
build(1, 1, n);
db tmp, avg, k;
for (j = 1; j <= m; ++j)
{
cin >> t;
if (t == 1)
{
cin >> l >> r >> k;
update(1, l, r, k);
}
else if (t == 2)
{
cin >> l >> r;
avg = query1(1, l, r) / db(r - l + 1);
cout << fixed << setprecision(4) << avg << '\n';
}
else
{
cin >> l >> r;
// cout << query1(1, l, r) << ' ' << query2(1, l, r) << '\n';
avg = query1(1, l, r) / db(r - l + 1);
tmp = query2(1, l, r) / db(r - l + 1) - avg * avg;
cout << fixed << setprecision(4) << tmp << '\n';
}
}
// for (j = 1; j <= n * 4; ++j)
// {
// cout << s[j].tag << '\n';
// }
return 0;
}
看的别人的代码:
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 100005;
double a[N], sum[4 * N], sum2[4 * N];
double tag[4 * N];
void pushup(int k)
{
sum[k] = sum[k * 2] + sum[k * 2 + 1]; // 区间和
sum2[k] = sum2[k * 2] + sum2[k * 2 + 1]; // 区间平方和
return;
}
void Add(int k, int lt, int rt, double val)
{ // 打懒标记
tag[k] += val;
sum2[k] += 2 * val * sum[k] + val * val * (rt - lt + 1);
sum[k] += (rt - lt + 1) * val;
return;
}
void pushdown(int k, int lt, int rt)
{
if (tag[k] == 0)
return;
int mid = lt + (rt - lt) / 2;
Add(k * 2, lt, mid, tag[k]);
Add(k * 2 + 1, mid + 1, rt, tag[k]);
tag[k] = 0; // 将标记传给子节点后,父节点的标记要清零,否则会加重复
return;
}
void build(int k, int lt, int rt)
{ // 第k个结点, lt rt为要询问的区间范围
if (lt == rt)
{
sum[k] = a[lt]; // a为原始数组,sum[k]为第k个结点的区间和
sum2[k] = a[lt] * a[lt]; // 平方
return;
}
int mid = (lt + rt) >> 1;
build(k * 2, lt, mid);
build(k * 2 + 1, mid + 1, rt);
pushup(k);
return;
}
// 在qx, qy区间每个数加上val
void update(int k, int lt, int rt, int qx, int qy, double val)
{
if (lt > qy || rt < qx)
return;
else if (lt >= qx && rt <= qy)
{
Add(k, lt, rt, val);
return;
}
int mid = lt + (rt - lt) / 2;
pushdown(k, lt, rt);
update(k * 2, lt, mid, qx, qy, val);
update(k * 2 + 1, mid + 1, rt, qx, qy, val);
pushup(k);
return;
}
double query(int k, int lt, int rt, int qx, int qy)
{
if (lt > qy || rt < qx)
return 0;
else if (lt >= qx && rt <= qy)
return sum[k];
int mid = lt + (rt - lt) / 2;
pushdown(k, lt, rt); // 询问时才下传标记,因为需要知道子区间要加的值
return query(k * 2, lt, mid, qx, qy) + query(k * 2 + 1, mid + 1, rt, qx, qy);
}
double query2(int k, int lt, int rt, int qx, int qy)
{
if (lt > qy || rt < qx)
return 0;
else if (lt >= qx && rt <= qy)
return sum2[k];
int mid = lt + (rt - lt) / 2;
pushdown(k, lt, rt); // 询问时才下传标记,因为需要知道子区间要加的值
return query2(k * 2, lt, mid, qx, qy) + query2(k * 2 + 1, mid + 1, rt, qx, qy);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
build(1, 1, n); // 建树
for (int i = 1; i <= m; i++)
{
int option, x, y;
double v;
cin >> option;
if (option == 1)
{
cin >> x >> y >> v;
update(1, 1, n, x, y, v);
}
else if (option == 2)
{
cin >> x >> y;
cout << fixed << setprecision(4) << query(1, 1, n, x, y) / (y - x + 1) << "\n";
}
else
{
cin >> x >> y;
cout << query(1, 1, n, x, y) << ' ' << query2(1, 1, n, x, y) << '\n';
double avg = query(1, 1, n, x, y) / (y - x + 1);
// cout << fixed << setprecision(4) << -avg * avg + query2(1, 1, n, x, y) / (y - x + 1) << "\n";
}
}
// for (int j = 1; j <= n * 4; ++j)
// {
// cout << tag[j] << '\n';
// }
return 0;
}
样例的操作5始终过不去,被卡好久了,能救救孩子吗QAQ