问题陈述：
https://www.hackerrank.com/contests/epiccode/challenges/square-array
给定一个整数数组 A1,A2,...AN，您必须在数组中执行两种类型的查询。
1 x y。将 1×2 加到 Ax，将 2×3 加到 Ax+1，将 3×4 加到 Ax+2，将 4×5 加到 Ax+3，依此类推，直到 Ay。
2 x y。求下标x到下标y的所有整数之和以109+7为模，即求(Ax+Ax+1+⋯+Ay)mod(109+7)。
您可以假设最初数组中的所有值都是 0。
输入格式：
第一行包含两个以空格分隔的整数 N 和 Q。N 表示数组的大小，Q 表示查询的数量。
接下来的 Q 行中的每一行都将包含一个 1 xy 或 2 x y 形式的查询。
约束：
1≤x≤y≤N 1≤N≤2×10^5 1≤Q≤2×10^5
输出格式 对于 2 xy 形式的每个查询，打印所需的答案。
Sample Input
10 5
1 1 10
2 2 7
1 4 8
1 5 6
2 6 6
Output:
166
60
解释：
After the first query, the array is [2,6,12,20,30,42,56,72,90,110]. The answer for the second query is 6+12+20+30+42=166. After the third query, the array is [2,6,12,22,36,54,76,102,90,110]. After the fourth query, the array is [2,6,12,22,38,60,76,102,90,110]. The answer for the fifth query is 60.
提交的解决方案之一：
#include <bits/stdc++.h>
const int N = 2 * 100005;
const long long MOD = 1000000007;
const long long INV = 333333336;
using namespace std;
int n;
int nQuery;
struct BIT {
int bit[N];
BIT() {
memset(bit, 0, sizeof(bit));
}
void inc(int i, int v) {
for (; i < N; i += i & -i) {
bit[i] += v;
bit[i] %= MOD;
}
}
void incRange(int i, int j, int v) {
inc(i, v); inc(j + 1, MOD - v);
}
int get(int i) {
int res = 0;
for (; i > 0; i -= i & -i)
res = (res + bit[i]) % MOD;
return res;
}
} First, Second, Third, Const;
int sum(long long x, long long y) {
return ((x + y) % MOD + MOD) % MOD;
}
void update(long long l, long long r) {
Third.incRange(l, r, 1);
Second.incRange(l, r, MOD - sum(l - 1, sum(l - 2, l - 3)));
First.incRange(l, r, sum((l - 1) * (l - 2) % MOD, sum((l - 2) * (l - 3) % MOD, (l - 1) * (l - 3) % MOD)));
Const.incRange(l, r, sum(MOD - (l - 1) * (l - 2) % MOD * (l - 3) % MOD, MOD));
Const.incRange(r + 1, n, (r - l + 1) * (r - l + 2) % MOD * (r - l + 3) % MOD);
}
int getSum(long long x) {
return (x * x % MOD * x % MOD * Third.get(x) % MOD + x * x % MOD * Second.get(x) % MOD + x * First.get(x) % MOD + Const.get(x)) % MOD * INV % MOD;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
freopen("square-array.txt", "r", stdin);
#endif // _LAD_
cin >> n >> nQuery;
int x, y, type;
while (nQuery--) {
cin >> type >> x >> y;
if (type == 1) {
update(x, y);
#ifdef _LAD_
for (int i = 1; i <= n; ++i)
cout << ((getSum(i) - getSum(i - 1) + MOD) % MOD) << ' ';
cout << endl;
#endif // _LAD_
}
else
cout << (getSum(y) - getSum(x - 1) + MOD) % MOD << '\n';
}
return 0;
}