80分求助,疑似被卡精度
查看原帖
80分求助,疑似被卡精度
764666
LostKeyToReach楼主2024/9/29 09:53
#include <bits/stdc++.h>
#define int long long 
#define double long double
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int N = 1e5 + 6;
int n, px[N], py[N], m;
struct sg {
  int sx, sy, sxy, sx2, si, si2, set_S_tag, set_T_tag, add_S_tag, add_T_tag, is_set;
} tr[N << 2]; 
void pushup(int u) {
  tr[u].sx = tr[ls].sx + tr[rs].sx;
  tr[u].sy = tr[ls].sy + tr[rs].sy;
  tr[u].sxy = tr[ls].sxy + tr[rs].sxy;
  tr[u].sx2 = tr[ls].sx2 + tr[rs].sx2;
}
void apply_set(int u, int l, int r, int set_S_tag, int set_T_tag) {
  tr[u].sx = set_S_tag * (r - l + 1) + tr[u].si;
  tr[u].sy = set_T_tag * (r - l + 1) + tr[u].si;
  tr[u].sxy = set_S_tag * set_T_tag * (r - l + 1) 
  + (set_S_tag + set_T_tag) * tr[u].si + tr[u].si2;
  tr[u].sx2 = set_S_tag * set_S_tag * (r - l + 1)
  + 2 * set_S_tag * tr[u].si + tr[u].si2;
  tr[u].is_set = 1, tr[u].set_S_tag = set_S_tag;
  tr[u].set_T_tag = set_T_tag;
  tr[u].add_S_tag = tr[u].add_T_tag = 0;
} 
void apply_add(int u, int l, int r, int add_S_tag, int add_T_tag) {
  tr[u].sxy += add_S_tag * tr[u].sy 
  + add_T_tag * tr[u].sx 
  + add_T_tag * add_S_tag * (r - l + 1);
  tr[u].sx2 += 2 * add_S_tag * tr[u].sx 
  + add_S_tag * add_S_tag * (r - l + 1);
  tr[u].sx += add_S_tag * (r - l + 1);
  tr[u].sy += add_T_tag * (r - l + 1);
  if (tr[u].is_set) {
    tr[u].set_S_tag += add_S_tag;
    tr[u].set_T_tag += add_T_tag;
  } else {
    tr[u].add_S_tag += add_S_tag;
    tr[u].add_T_tag += add_T_tag;
  }
}
void pushdown(int u, int l, int r) {
  int mid = l + r >> 1;
  if (tr[u].is_set) {
    apply_set(ls, l, mid, tr[u].set_S_tag, tr[u].set_T_tag);
    apply_set(rs, mid + 1, r, tr[u].set_S_tag, tr[u].set_T_tag);
    tr[u].is_set = 0;
  }
  if (tr[u].add_S_tag || tr[u].add_T_tag) {
    apply_add(ls, l, mid, tr[u].add_S_tag, tr[u].add_T_tag);
    apply_add(rs, mid + 1, r, tr[u].add_S_tag, tr[u].add_T_tag);
    tr[u].add_S_tag = tr[u].add_T_tag = 0;
  }
}
void build(int u, int l, int r) {
  tr[u].is_set = tr[u].set_S_tag = tr[u].set_T_tag
  = tr[u].add_S_tag = tr[u].add_T_tag = 0;
  if (l == r) {
    tr[u].sx = px[l], tr[u].sy = py[l];
    tr[u].sxy = px[l] * py[l];
    tr[u].sx2 = px[l] * px[l];
    tr[u].si = l, tr[u].si2 = l * l;
    return;
  }
  int mid = l + r >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  pushup(u);
  tr[u].si = tr[ls].si + tr[rs].si;
  tr[u].si2 = tr[ls].si2 + tr[rs].si2;
}
void modify_add(int u, int l, int r, int ql, int qr, int s, int t) {
  if (ql <= l && r <= qr) {
    apply_add(u, l, r, s, t);
    return;
  }
  pushdown(u, l, r);
  int mid = l + r >> 1;
  if (ql <= mid) modify_add(ls, l, mid, ql, qr, s, t);
  if (qr > mid) modify_add(rs, mid + 1, r, ql, qr, s, t);
  pushup(u);
}
void modify_set(int u, int l, int r, int ql, int qr, int s, int t) {
  if (ql <= l && r <= qr) {
    apply_set(u, l, r, s, t);
    return;
  }
  pushdown(u, l, r);
  int mid = l + r >> 1;
  if (ql <= mid) modify_set(ls, l, mid, ql, qr, s, t);
  if (qr > mid) modify_set(rs, mid + 1, r, ql, qr, s, t);
  pushup(u);
} 
sg ans;
void query_range(int u, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    ans.sx += tr[u].sx;
    ans.sy += tr[u].sy;
    ans.sxy += tr[u].sxy;
    ans.sx2 += tr[u].sx2;
    return;
  }
  pushdown(u, l, r);
  int mid = l + r >> 1;
  if (ql <= mid) query_range(ls, l, mid, ql, qr);
  if (qr > mid) query_range(rs, mid + 1, r, ql, qr);
}
int32_t main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> px[i];
  for (int i = 1; i <= n; ++i) cin >> py[i];
  build(1, 1, n);
  while (m--) {
    int op, l, r, s, t;
    cin >> op >> l >> r;
    if (op == 1) {
      ans = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
      query_range(1, 1, n, l, r);
      cout << fixed << setprecision(13) << 1.0 * (1.0 * ans.sxy 
        - 1.0 * (double)ans.sx * ans.sy / (double)(r - l + 1)) 
      / (1.0 * (double)ans.sx2 - 1.0 * ans.sx * ans.sx / (double)(r - l + 1)) << '\n';
    } else if (op == 2) {
      cin >> s >> t;
      modify_add(1, 1, n, l, r, s, t);
    } else {
      cin >> s >> t;
      modify_set(1, 1, n, l, r, s, t);
    }
  }
}
2024/9/29 09:53
加载中...