NC226172. 智乃酱的平方数列
描述
输入描述
第一行输入。
接下来行，对于每行，先读入一个整数
。
当时，还需读入两个整
表示需要对区间[l,r]进行操作，让第一个元素加
，第三个元素加
以此类推。
当时，还需读入两个整数
表示查询l到r的元素和
输出描述
对于每一个，输出一行一个非负整数，表示l到r的区间和mod
。
示例1
输入:
4 4 2 1 4 1 1 4 1 3 4 2 1 4
输出:
0 35
示例2
输入:
10 6 1 1 6 1 8 9 1 3 6 2 1 10 1 1 10 2 1 10
输出:
126 511
C++ 解法, 执行用时: 371ms, 内存消耗: 18448K, 提交时间: 2022-04-26 13:28:01
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 5, mod = 1e9 + 7, inv6 = 166666668;
LL tr1[maxn], tr2[maxn], tr3[maxn], tr4[maxn];
int n, m;
inline int lowbit(int x){
return x & -x;
}
void modify(int x, LL v){
for(int i = x; i <= n; i += lowbit(i)){
tr1[i] = (tr1[i] + v) % mod;
tr2[i] = (tr2[i] + v * x % mod) % mod;
tr3[i] = (tr3[i] + v * x % mod * x % mod) % mod;
tr4[i] = (tr4[i] + v * x % mod * x % mod * x % mod) % mod;
}
}
LL query(int x){
LL res = 0;
for(int i = x; i; i -= lowbit(i))
res = (res + tr1[i] * (x + 3) % mod * (x + 2) % mod * (x + 1) % mod
-(3LL * x * x % mod + 12LL * x % mod + 11) * tr2[i] % mod
+ (3LL * x + 6) * tr3[i] % mod
- tr4[i]) % mod;
return (res + mod) * inv6 % mod;
}
int main(){
scanf("%d%d", &n, &m);
while(m--){
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 1){
modify(l, 1);
if (l + 1 <= n) modify(l + 1, 1);
LL v = 1LL * (r - l + 1) * (r - l + 1) % mod;
if (r + 1 <= n) modify(r + 1, (-v - 2 * (r - l + 1) - 1 + mod + mod) % mod);
if (r + 2 <= n) modify(r + 2, 2 * v + 2 * (r - l + 1) - 1);
if (r + 3 <= n) modify(r + 3, (-v + mod) % mod);
}
else printf("%lld\n", (query(r) - query(l - 1) + mod) % mod);
}
}