// Luogu.org P1438 // https://www.cnblogs.com/cytus/p/9590071.html #include #include #include using namespace std; #define LL long long const int N = 1e5 + 7; int n, q, m; LL a[N], tr[N << 2], add[N << 2]; //快读 int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return x * f; } void modify(int x, int d) { for (x += m; x; x >>= 1) tr[x] += d; //单点修改,一路向上更新 } void modify(int l, int r, int d) { //区间修改 LL lc = 0, rc = 0, c = 1; for (l = l + m - 1, r = r + m + 1; l ^ r ^ 1; l >>= 1, r >>= 1, c <<= 1) { tr[l] += d * lc, tr[r] += d * rc; if (~l & 1) add[l ^ 1] += d, tr[l ^ 1] += d * c, lc += c; if (r & 1) add[r ^ 1] += d, tr[r ^ 1] += d * c, rc += c; } //一路向上走,修改sum值,但却没有修改add for (; l; l >>= 1, r >>= 1) tr[l] += d * lc, tr[r] += d * rc; } LL query(int l, int r) { LL res = 0, lc = 0, rc = 0, c = 1; for (l = l + m - 1, r = r + m + 1; l ^ r ^ 1; l >>= 1, r >>= 1, c <<= 1) { if (add[l]) res += add[l] * lc; if (add[r]) res += add[r] * rc; if (~l & 1) res += tr[l ^ 1], lc += c; if (r & 1) res += tr[r ^ 1], rc += c; } for (; l; l >>= 1, r >>= 1) res += add[l] * lc, res += add[r] * rc; return res; } int main() { //文件输入输出 #ifndef ONLINE_JUDGE freopen("P1438.in", "r", stdin); #endif n = read(), q = read(); // build for (m = 1; m <= n + 1;) m <<= 1; for (int i = 1; i <= n; i++) { a[i] = read(); tr[m + i] = a[i] - a[i - 1]; //记录差分值 } // debug // printf("m=%d\n", m); // for (int i = 0; i <= 6; i++) printf("%lld ", tr[m + i]); // puts(""); //所有父节点,从下向上,将值更新为左右子树的和,每个值都是自已所辖区间的差分和 for (int i = m - 1; i >= 1; i--) { tr[i] = tr[i << 1] + tr[i << 1 | 1]; // printf("tr[%d]=%d\n", i, tr[i]); } /* 1 2 3 4 5 1 2 3 4 5 1 3 5 ---------- 1 3 6 9 5 query(3)=6 tr 1 1 1 1 1 */ for (int i = 1; i <= q; i++) { int op = read(); if (op == 1) { int l = read(), r = read(); LL k = read(), d = read(); //首项:k,公差:d // 1 2 4 1 2 modify(l, k); //改2 modify(r + 1, -(k + (r - l) * d)); //改4+1 modify(l + 1, r, d); //改3-4 } else { LL x = read(); //查询单点 printf("%lld\n", query(1, x)); //以前缀和进行描述 } } return 0; }