题面
Sol
线段树维护区间(DP)
差分，你会发现就是选一些区间，第一个值可以不一样
那么我们维护原数组左右端点是否选的情况，一共四种
注意差分数组只有(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
", 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;
}