线段树上维护各种区间和.

先推式子.

我们要求: $\begin{align}\sum_{i=L}^{R}{\sum_{j = i}^{n}{s[j]-s[j-i+1]}}\end{align}$.

变换一下顺序, 就是$\begin{align}\sum_{i=L}^{R}(S_s[n]-S_s[i-1])-\sum_{i=n-R}^{n-L}{S_s[i]}\end{align}$.

然后$\begin{align}(R-L+1)S_s[n] - \sum_{i=L-1}^{R-1}{S_s[i]} - \sum_{i=n-R}^{n-L}S_s[i]\end{align}$.

这式子可以线段树区间查询的.

区间更新? 分情况考虑:

对于$[l,r]$区间, 一个$v$的更新会对位置$i$二次前缀和产生$\frac{(i-L+2)(i-L+1)}{2}v$的影响.

对于$[r+1,n]$区间, 会产生$(r-l+1)(i-r)v$的影响.

这些可以一次对应到$i$的常数项, 一次项, 二次项的系数, 维护三个tag, 更新即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define mod 1000000007
#define inv 500000004

using namespace std;
typedef long long ll;

const int maxn = 2e+5 + 5;

int n, m, a[maxn];
ll lnsum[maxn], sqsum[maxn];
ll tg1[maxn << 2], tg2[maxn << 2], tg3[maxn << 2], vsum[maxn << 2];
ll lens[maxn << 2], lns[maxn << 2], sqs[maxn << 2];
int s[maxn], s2[maxn];

inline void addval(int cur, ll v1, ll v2, ll v3) {
  vsum[cur] = (vsum[cur] + v1 * lens[cur] % mod + v2 * lns[cur] % mod + v3 * sqs[cur] % mod) % mod;
  tg1[cur] += v1;
  tg2[cur] += v2;
  tg3[cur] += v3;
  (tg1[cur] >= mod) ? tg1[cur] -= mod : 0;
  (tg2[cur] >= mod) ? tg2[cur] -= mod : 0;
  (tg3[cur] >= mod) ? tg3[cur] -= mod : 0;
}
inline void pushdown(int cur) {
  if (!tg1[cur] && !tg2[cur] && !tg3[cur]) 
    return;
  addval(cur << 1, tg1[cur], tg2[cur], tg3[cur]);
  addval(cur << 1|1, tg1[cur], tg2[cur], tg3[cur]);
  tg1[cur] = tg2[cur] = tg3[cur] = 0;
}
inline void pushup(int cur) {
  vsum[cur] = (vsum[cur << 1] + vsum[cur << 1|1]) % mod;
}
void build(int cur, int l, int r) {
  lens[cur] = r - l + 1;
  lns[cur] = (lnsum[r] - lnsum[max(l - 1, 0)] + mod) % mod;
  sqs[cur] = (sqsum[r] - sqsum[max(l - 1, 0)] + mod) % mod;
  if (l == r) {
    vsum[cur] = s2[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(cur << 1, l, mid);
  build(cur << 1|1, mid + 1, r);
  pushup(cur);
}
void update(int cur, int l, int r, int L, int R, 
            ll v1, ll v2, ll v3) {
  if (L > R) return;
  if (L <= l && r <= R) {
    addval(cur, v1, v2, v3);
    return;
  }
  int mid = (l + r) >> 1; pushdown(cur);
  /*if (L <= mid) update(cur << 1, l, mid, L, R, v1, v2, v3);
  if (R > mid) update(cur << 1|1, mid + 1, r, L, R, v1, v2, v3);*/
  if (R <= mid) update(cur << 1, l, mid, L, R, v1, v2, v3);
  else if (L > mid) update(cur << 1|1, mid + 1, r, L, R, v1, v2, v3);
  else {
    update(cur << 1, l, mid, L, mid, v1, v2, v3);
    update(cur << 1|1, mid + 1, r, mid + 1, R, v1, v2, v3);
  }
  pushup(cur);
}
ll query(int cur, int l, int r, int L, int R) {
  if (L > R) return 0;
  if (L <= l && r <= R) return vsum[cur];
  int mid = (l + r) >> 1; pushdown(cur);
  ll ret = 0;
  /*if (L <= mid) ret = query(cur << 1, l, mid, L, R);
  if (R > mid) ret = (ret + query(cur << 1|1, mid + 1, r, L, R)) % mod;*/
  if (R <= mid) return query(cur << 1, l, mid, L, R);
  else if (L > mid) return query(cur << 1|1, mid + 1, r, L, R);
  else return (query(cur << 1, l, mid, L, mid) + query(cur << 1|1, mid + 1, r, mid + 1, R)) % mod;
  // return ret;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    lnsum[i] = (lnsum[i - 1] + i) % mod;
    sqsum[i] = (sqsum[i - 1] + 1ll * i * i % mod) % mod;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    s[i] = (s[i - 1] + a[i]) % mod;
    s2[i] = (s2[i - 1] + s[i]) % mod;
  }
  build(1, 1, n);
  int opt, u, v; ll val;
  while (m--) {
    scanf("%d%d%d", &opt, &u, &v);
    if (u > v) swap(u, v);
    if (opt == 1) {
      scanf("%lld", &val);
      ll len = v - u + 1, vhf = val * inv % mod;
      update(1, 1, n, u, v, vhf * (u - 1) % mod * (u - 2) % mod,
                            vhf * (3 - 2 * u + mod) % mod, vhf);
      update(1, 1, n, v + 1, n, ((len * (len + 1) / 2 % mod * val - len * val % mod * v) % mod + mod) % mod,
                                 val * len % mod, 0);
    } else {
      u = max(u, 1);
      ll pt1 = query(1, 1, n, n, n) * (v - u + 1) % mod;
      ll pt2 = query(1, 1, n, max(u - 1, 1), v - 1);
      ll pt3 = query(1, 1, n, max(n - v, 1), n - u);
      printf("%lld\n", (pt1 - (pt2 + pt3) % mod + mod) % mod);
    }
  }
  return 0;
}