Luogu P4915 帕秋莉的魔导书

题目链接：​​传送门​​

动态开点是真的麻烦
跟普通线段树差别还是挺大的
题意就是区间前缀和的和除以区间长度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int l, r; ll w, f;
}tree[A];
ll a, b;
int n, m, cnt, opt, root;
void down(int k, int l, int r, int ls = 0, int rs = 0) {
  if (!tree[k].l) ls = tree[k].l = ++cnt; else ls = tree[k].l;
  if (!tree[k].r) rs = tree[k].r = ++cnt; else rs = tree[k].r;
  int m = (l + r) >> 1;
  tree[ls].f += tree[k].f; tree[rs].f += tree[k].f;
  tree[ls].w += tree[k].f * (m - l + 1);
  tree[rs].w += tree[k].f * (r - m);
  tree[k].f = 0;
}
void add(int &k, int l, int r, int posl, int posr, ll val) {
  if (!k) k = ++cnt;
  if (posl > r or posr < l) return;
  if (posl >= l and posr <= r) {
    tree[k].w += (posr - posl + 1) * val;
    tree[k].f += val;
    return;
  }
  if (tree[k].f) down(k, posl, posr);
  int m = (posl + posr) >> 1;
  add(tree[k].l, l, r, posl, m, val);
  add(tree[k].r, l, r, m + 1, posr, val);
  tree[k].w = tree[tree[k].l].w + tree[tree[k].r].w;
}
ll ask(int k, int l, int r, int posl, int posr) {
  if (posl > r or posr < l) return 0;
  if (posl >= l and posr <= r) return tree[k].w;
  if (tree[k].f) down(k, posl, posr);
  int m = (posl + posr) >> 1; ll ans = 0;
  if (tree[k].l) ans += ask(tree[k].l, l, r, posl, m);
  if (tree[k].r) ans += ask(tree[k].r, l, r, m + 1, posr);
  return ans;
}

int main(int argc, char const *argv[]) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    add(root, a, INT_MAX, 1, INT_MAX, b);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &opt, &a, &b);
    if (opt == 1) printf("%.4lf\n", (double)ask(1, a, b, 1, INT_MAX) / (b - a + 1));
    else add(root, a, INT_MAX, 1, INT_MAX, b);
  }
}