#include <bits/stdc++.h> using namespace std; long long n, sum[800001], add[800001], tr[800001], q; int A[200001]; inline void build1(int k, int l, int r) { if (l == r) { sum[k] = A[l]; return; } int mid = (l + r) >> 1; build1(k << 1, l, mid); build1(k << 1 | 1, mid + 1, r); sum[k] = sum[k << 1] + sum[k << 1 | 1]; } inline void build2(int k, int l, int r) { if (l == r) { tr[k] = abs(A[l + 1] - A[l]); return; } int mid = (l + r) >> 1; build2(k << 1, l, mid); build2(k << 1 | 1, mid + 1, r); tr[k] = tr[k << 1] + tr[k << 1 | 1]; } inline void push(int k, int len) { sum[k << 1] += add[k] * (len - (len >> 1)); sum[k << 1 | 1] += add[k] * (len >> 1); add[k << 1] += add[k]; add[k << 1 | 1] += add[k]; add[k] = 0; } inline void add1(int k, int l, int r, int x, int y) { if (x > r || y < l) return; if (x <= l && y >= r) { sum[k] += r - l + 1; add[k]++; return; } int mid = (l + r) >> 1; push(k, r - l + 1); add1(k << 1, l, mid, x, y); add1(k << 1 | 1, mid + 1, r, x, y); sum[k] = sum[k << 1] + sum[k << 1 | 1]; } inline void add2(int k, int l, int r, int x, int v) { if (x > r || x < l) return; if (l == r) { tr[k] = v; return; } int mid = (l + r) >> 1; add2(k << 1, l, mid, x, v); add2(k << 1 | 1, mid + 1, r, x, v); tr[k] = tr[k << 1] + tr[k << 1 | 1]; } inline long long query(int k, int l, int r, int x) { if (x > r || x < l) return 0; if (l == r) return sum[k]; int mid = (l + r) >> 1; push(k, r - l + 1); return query(k << 1, l, mid, x) + query(k << 1 | 1, mid + 1, r, x); } inline long long query2(int k, int l, int r, int x, int y) { if (x > r || y < l) return 0; if (x <= l && y >= r) return tr[k]; int mid = (l + r) >> 1; return query2(k << 1, l, mid, x, y) + query2(k << 1 | 1, mid + 1, r, x, y); } int main() { ios::sync_with_stdio(false); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> A[i]; build1(1, 1, n); build2(1, 1, n - 1); while (q--) { int op, l, r; cin >> op >> l >> r; if (op == 1) { cout << query(1, 1, n, l) + query2(1, 1, n - 1, l, r - 1) << "\n"; } else { add1(1, 1, n, l, r); add2(1, 1, n - 1, l - 1, abs(query(1, 1, n, l) - query(1, 1, n, l - 1))); add2(1, 1, n - 1, r, abs(query(1, 1, n, r + 1) - query(1, 1, n, r))); } } }
全部评论
(0) 回帖