题目链接：http://code.bupt.edu.cn/problem/p/451/
区间加上一个等差数列
这里涉及i的二次项
具体的做法见上一篇博文
实际上可以观察到
若化简后公式为s'[i] = s[i] + a*i*i + b*i + c
那么在l的地方 只需要在一次项及一次以上的项那加上对应的系数 然后在零次项那减掉a*(l-1)*(l-1) + b*(l-1)
在r的地方 在在一次项及一次以上的项那减掉对应的系数 最后在零次项那加上a*r*r + b*r
即可
一般常数项化出来都很复杂 用这种方法就可以省略常数项的化简
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <set> #include <map> #include <stack> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; const ull B = 9973; const int maxn = 110000; const ll M = 23333; ll bit0[maxn]; ll bit1[maxn]; ll bit2[maxn]; int n, q; ll sum(ll *b, int i) { ll s = 0; while(i > 0) { s += b[i]; i -= i & -i; } return s; } void add(ll *b, int i, ll v) { while(i <= n) { b[i] += v; i += i & -i; } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &q); memset(bit0, 0, sizeof(bit0)); memset(bit1, 0, sizeof(bit1)); memset(bit2, 0, sizeof(bit2)); for(int i = 1; i <= n; i++) { int t; scanf("%d", &t); add(bit0, i, (ll)2*t); } for(int i = 0; i < q; i++) { int mode; scanf("%d", &mode); if(mode == 1) { int l, r, x, d; scanf("%d%d%d%d", &l, &r, &x, &d); add(bit0, l, (ll)(-(ll)d*(l-1)*(l-1)-((ll)(2*x+d-2*l*d)*(l-1)))); add(bit1, l, (ll)(2*x+d-2*l*d)); add(bit2, l, (ll)d); add(bit0, r+1, (ll)((ll)d*r*r+(ll)(2*x+d-2*l*d)*r)); add(bit1, r+1, (ll)(-(2*x+d-2*l*d))); add(bit2, r+1, (ll)(-d)); } else { int l, r; scanf("%d%d", &l, &r); ll res = 0; res += sum(bit0, r) + sum(bit1, r)*r + sum(bit2, r)*r*r; res -= sum(bit0, l-1) + sum(bit1, l-1)*(l-1) + sum(bit2, l-1)*(l-1)*(l-1); printf("%lld ", res/2); } } } return 0; }