牛客小白月赛15-j-外挂-线段树

原题地址
第一眼看过去线段树，然后不会。看了题解，好简单。。一时间还真的没有看出那个公式。
补题的时侯也wa了好多次，以为是精度问题。嗯。。是我太蠢了
，主要就是维护一个区间和与平方区间和。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1,r
const int N = 1e5+5;
LL sum[N<<2], sum1[N<<2], a[N], lazy[N<<2], x1, x2;
void pushup(LL rt) {
  sum[rt] = sum[rt<<1] + sum[rt<<1|1];
  sum1[rt] = sum1[rt<<1] + sum1[rt<<1|1];
}
void pushdown(LL rt, LL l, LL r) {
  if(lazy[rt]) {
    int mid = (l + r) / 2;
    lazy[rt<<1] += lazy[rt];
    lazy[rt<<1|1] += lazy[rt];
    sum1[rt<<1] += lazy[rt]*lazy[rt]*(mid-l+1) + 2*lazy[rt]*sum[rt<<1];
    sum1[rt<<1|1] += lazy[rt]*lazy[rt]*(r-mid) + 2*lazy[rt]*sum[rt<<1|1];
    sum[rt<<1] += lazy[rt]*(mid-l+1);
    sum[rt<<1|1] += lazy[rt]*(r-mid);
    lazy[rt] = 0;
  }
}
void build(LL rt, LL l, LL r) {
  if(l == r) {
    sum[rt] = a[l];
    sum1[rt] = a[l]*a[l];
    return;
  }
  LL mid = (l + r) / 2;
  build(lson);
  build(rson);
  pushup(rt);
}
void update(LL rt, LL l, LL r, LL L, LL R, LL x) {
  if(l == L && r == R) {
    sum1[rt] += x*x*(R-L+1) + 2*sum[rt]*x;
    sum[rt] += x*(R-L+1);
    lazy[rt] += x;
    return ;
  }
  pushdown(rt, l, r);
  LL mid = (l + r) / 2;
  if(R <= mid) update(lson, L, R, x);
  else if(L > mid) update(rson, L, R, x);
  else {
    update(lson, L, mid, x);
    update(rson, mid+1, R, x);
  }
  pushup(rt);
}
void query(LL rt, LL l, LL r, LL L, LL R) {
  if(l == L && r == R) {
    x1 += sum[rt];
    x2 += sum1[rt];
    return ;
  }
  pushdown(rt, l, r);
  LL mid = (l + r) / 2;
  if(R <= mid) query(lson, L, R);
  else if(L > mid) query(rson, L, R);
  else {
    query(lson, L, mid); query(rson, mid+1, R);
  }
}
int main() {
  LL n, m, op, x, y, z;
  scanf("%lld%lld", &n, &m);
  for(int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  build(1,1,n);
  for (int i = 1; i <= m; i++) {
    scanf("%lld", &op);
    if(op == 1) {
      scanf("%lld%lld%lld", &x, &y, &z);
      update(1,1,n,x,y,z);
    }
    else if(op == 2){
      scanf("%lld%lld", &x, &y);
      x1 = x2 = 0;
      query(1,1,n,x,y);
      printf("%lld\n", (x1*x1 - x2)/2);
    }
  }
}

`