题面

传送门

Sol

线段树维护区间 DP D P 差分，你会发现就是选一些区间，第一个值可以不一样 那么我们维护原数组左右端点是否选的情况，一共四种 注意差分数组只有 n−1 n − 1 的长度，并且每个数维护的是两个相邻的原数组的数

# include <bits/stdc++.h> # define RG register # define IL inline # define Fill(a, b) memset(a, b, sizeof(a)) # define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout) using namespace std; typedef long long ll; const int _(1e5 + 5); IL int Input(){ RG int x = 0, z = 1; RG char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * z; } int n, Q, a[_]; struct Data{ int s[4], l, r; //0:l0r0, 1:l1r0, 2:l0r1, 3:l1r1 }; struct Segment{ int tag; Data v; } T[_ << 2]; IL Data Merge(RG Data A, RG Data B){ RG Data C; RG int tmp = A.r == B.l; C.l = A.l, C.r = B.r; C.s[0] = A.s[2] + B.s[1] - tmp; C.s[0] = min(C.s[0], min(A.s[0] + B.s[1], A.s[2] + B.s[0])); C.s[1] = A.s[3] + B.s[1] - tmp; C.s[1] = min(C.s[1], min(A.s[1] + B.s[1], A.s[3] + B.s[0])); C.s[2] = A.s[2] + B.s[3] - tmp; C.s[2] = min(C.s[2], min(A.s[0] + B.s[3], A.s[2] + B.s[2])); C.s[3] = A.s[3] + B.s[3] - tmp; C.s[3] = min(C.s[3], min(A.s[1] + B.s[3], A.s[3] + B.s[2])); return C; } IL void Build(RG int x, RG int l, RG int r){ RG Data &X = T[x].v; if(l == r){ X.s[1] = X.s[2] = X.s[3] = 1, X.l = X.r = a[l] - a[l - 1]; return; } RG int mid = (l + r) >> 1; Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r); X = Merge(T[x << 1].v, T[x << 1 | 1].v); } IL void Adjust(RG int x, RG int tag){ RG Data &X = T[x].v; T[x].tag += tag, X.l += tag, X.r += tag; } IL void Pushdown(RG int x){ if(!T[x].tag) return; Adjust(x << 1, T[x].tag), Adjust(x << 1 | 1, T[x].tag); T[x].tag = 0; } IL void Modify(RG int x, RG int l, RG int r, RG int L, RG int R, RG int v){ if(L <= l && R >= r){ Adjust(x, v); return; } Pushdown(x); RG int mid = (l + r) >> 1; if(L <= mid) Modify(x << 1, l, mid, L, R, v); if(R > mid) Modify(x << 1 | 1, mid + 1, r, L, R, v); T[x].v = Merge(T[x << 1].v, T[x << 1 | 1].v); } IL Data Query(RG int x, RG int l, RG int r, RG int L, RG int R){ if(L == l && R == r) return T[x].v; Pushdown(x); RG int mid = (l + r) >> 1; if(R <= mid) return Query(x << 1, l, mid, L, R); else if(L > mid) return Query(x << 1 | 1, mid + 1, r, L, R); else return Merge(Query(x << 1, l, mid, L, mid), Query(x << 1 | 1, mid + 1, r, mid + 1, R)); } int main(RG int argc, RG char *argv[]){ n = Input(); for(RG int i = 0; i < n; ++i) a[i] = Input(); --n, Build(1, 1, n); for(Q = Input(); Q; --Q){ RG char op; scanf(" %c", &op); if(op == 'B'){ RG int l = Input(), r = Input(); (l == r) ? puts("1") : printf("%d\n", Query(1, 1, n, l, r - 1).s[3]); } else{ RG int l = Input(), r = Input(), x = Input(), y = Input(); if(l > 1) Modify(1, 1, n, l - 1, l - 1, x); if(l < r) Modify(1, 1, n, l, r - 1, y); if(r < n) Modify(1, 1, n, r, r, -(x + y * (r - l))); } } return 0; }