NC 200195
线段树维护区间和，考虑到等差数列差值为常数 1 1 1，同时记录区间左端点的数值即可。
#include <bits/stdc++.h> using namespace std; #define maxn 200005 #define sg_size (1 << 19) - 1 typedef long long ll; int a[maxn]; ll sum[sg_size], lz[sg_size]; inline void pushup(int k, int chl, int chr) { sum[k] = sum[chl] + sum[chr]; } void init(int k, int l, int r) { if (r - l == 1) sum[k] = a[l]; else { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; init(chl, l, m); init(chr, m, r); pushup(k, chl, chr); } } inline ll calc(ll x, ll n) { return x * n + (n - 1) * n / 2; } inline void pushdown(int k, int chl, int chr, int l, int r, int m) { if (lz[k]) { lz[chl] = lz[k], lz[chr] = lz[k] + m - l; sum[chl] = calc(lz[chl], m - l), sum[chr] = calc(lz[chr], r - m); lz[k] = 0; } } void update(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { lz[k] = x + l - a; sum[k] = calc(lz[k], r - l); } else if (l < b && r > a) { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; pushdown(k, chl, chr, l, r, m); update(a, b, x, chl, l, m); update(a, b, x, chr, m, r); pushup(k, chl, chr); } } ll query(int a, int b, int k, int l, int r) { if (b <= l || r <= a) { return 0; } else if (a <= l && r <= b) { return sum[k]; } else { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; pushdown(k, chl, chr, l, r, m); return query(a, b, chl, l, m) + query(a, b, chr, m, r); } } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", a + i); } init(0, 0, n); while (m--) { int op; scanf("%d", &op); if (op == 1) { int l, r, k; scanf("%d%d%d", &l, &r, &k); --l; update(l, r, k, 0, 0, n); } else { int l, r; scanf("%d%d", &l, &r); --l; printf("%lld\n", query(l, r, 0, 0, n)); } } return 0; }