HAOI2012 高速公路

DP 线段树

其实就是要求维护一个区间里面所有子qujian区间的和的总和，那么单独考虑维护每个点的贡献，$\sum\limits_{i=l}^{r} val_i(i-l+1)(r-i+1)$，用线段树维护三个值的总和，分别是 $val_i,val_ii,val_ii^2$。具体实现就是在区间加的同时还多维护一个系数和。

#include <iostream>
#include <cstdio>
typedef long long LL;
#define int LL
const int MAXN = 1e5;
int n, m;
inline int read() {
  register int x = 0, v = 1;
  register char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') v = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * v;
}
namespace Segtree {
  struct Node {
    int sumv, sumc, sumr, sumg, sumf;
    int lazy;
    Node *ch[2];
    Node() : sumv(0), sumc(0), sumr(0), sumg(0), sumf(0), lazy(0) {
      ch[0] = ch[1] = NULL;
    }
  } *root;
  void push_up(Node *o) {
    o -> sumv = o -> ch[0] -> sumv + o -> ch[1] -> sumv;
    o -> sumc = o -> ch[0] -> sumc + o -> ch[1] -> sumc;
    o -> sumr = o -> ch[0] -> sumr + o -> ch[1] -> sumr;
    o -> sumg = o -> ch[0] -> sumg + o -> ch[1] -> sumg;
    o -> sumf = o -> ch[0] -> sumf + o -> ch[1] -> sumf;
  }
  void push_down(Node *o, int l, int r) {
    if (o -> lazy) {
      int mid = (l + r) >> 1;
      o -> ch[0] -> sumv += (mid - l + 1) * o -> lazy;
      o -> ch[1] -> sumv += (r - mid) * o -> lazy;
      o -> ch[0] -> sumc += o -> ch[0] -> sumg * o -> lazy;
      o -> ch[1] -> sumc += o -> ch[1] -> sumg * o -> lazy;
      o -> ch[0] -> sumr += o -> ch[0] -> sumf * o -> lazy;
      o -> ch[1] -> sumr += o -> ch[1] -> sumf * o -> lazy;
      o -> ch[0] -> lazy += o -> lazy;
      o -> ch[1] -> lazy += o -> lazy;
      o -> lazy = 0;
    }
  }
  void build(Node *&o, int l, int r) {
    o = new Node;
    if (l == r) {
      o -> sumg = l;
      o -> sumf = l * l;
      return;
    }
    int mid = (l + r) >> 1;
    build(o -> ch[0], l, mid);
    build(o -> ch[1], mid + 1, r);
    push_up(o);
  }
  void update(Node *o, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
      o -> sumv += (r - l + 1) * v;
      o -> sumc += o -> sumg * v;
      o -> sumr += o -> sumf * v;
      o -> lazy += v;
      return;
    }
    int mid = (l + r) >> 1;
    push_down(o, l, r);
    if (ql <= mid) update(o -> ch[0], l, mid, ql, qr, v);
    if (mid < qr) update(o -> ch[1], mid + 1, r, ql, qr, v);
    push_up(o);
  }
  int query(Node *o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return o -> sumv * (qr - ql - ql * qr + 1) + o -> sumc * (qr + ql) - o -> sumr;
    int mid = (l + r) >> 1, res = 0;
    push_down(o, l, r);
    if (ql <= mid) res = query(o -> ch[0], l, mid, ql, qr);
    if (mid < qr) res += query(o -> ch[1], mid + 1, r, ql, qr);
    return res;
  }
}
using namespace Segtree;
int gcd(int x, int y) {
  return y ? gcd(y, x % y) : x;
}
signed main() {
  n = read();
  m = read();
  build(root, 1, n);
  while (m--) {
    char opt[10];
    scanf("%s", opt);
    if (*opt == 'C') {
      int l = read(), r = read() - 1, v = read();
      update(root, 1, n, l, r, v);
    } else {
      int l = read(), r = read() - 1;
      int a = query(root, 1, n, l, r), b = (r - l + 2) * (r - l + 1) / 2, c = gcd(a, b);
      printf("%lld/%lld\n", a / c, b / c);
    }
  }
  return 0;
}