题目链接
题解
等差数列，当然是差分一下
差分值相同的连续位置形成等差数列，我们所选的两个等差数列之间可以有一个位置舍弃
例如：
\(1 \; 2 \; 3 \; 6 \; 8 \; 10\)
差分后是
\(1\; 1\; 3 \; 2\; 2\)
左边两个\(1\)形成等差，右边两个\(2\)形成等差，中间的\(3\)位于两个等差数列的边界，可以舍弃
所以现在问题就转化为了：
在一个区间中选定若干个相同数字的区间，区间之间可以有一个空隙，求最少的区间数
可以用线段树维护
每个节点储存一下左右端点的值，以及\(c[2][2]\)表示左右端点选与不选时的答案
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define cls(s) memset(s,0,sizeof(s))
#define LL long long int
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int n,Q,A[maxn],D[maxn];
LL cnt[maxn << 2][2][2],add[maxn << 2],rn[maxn << 2],ln[maxn << 2];
void pd(int u){
if (add[u]){
ln[ls] += add[u]; rn[ls] += add[u]; add[ls] += add[u];
ln[rs] += add[u]; rn[rs] += add[u]; add[rs] += add[u];
add[u] = 0;
}
}
void pup(int u){
ln[u] = ln[ls]; rn[u] = rn[rs];
if (rn[ls] == ln[rs]){
cnt[u][0][0] = cnt[ls][0][1] + cnt[rs][1][0] - 1;
cnt[u][0][1] = cnt[ls][0][1] + cnt[rs][1][1] - 1;
cnt[u][1][0] = cnt[ls][1][1] + cnt[rs][1][0] - 1;
cnt[u][1][1] = cnt[ls][1][1] + cnt[rs][1][1] - 1;
}
else {
cnt[u][0][0] = min(cnt[ls][0][0] + cnt[rs][1][0],cnt[ls][0][1] + cnt[rs][0][0]);
cnt[u][0][1] = min(cnt[ls][0][1] + cnt[rs][0][1],cnt[ls][0][0] + cnt[rs][1][1]);
cnt[u][1][0] = min(cnt[ls][1][1] + cnt[rs][0][0],cnt[ls][1][0] + cnt[rs][1][0]);
cnt[u][1][1] = min(cnt[ls][1][1] + cnt[rs][0][1],cnt[ls][1][0] + cnt[rs][1][1]);
}
}
void build(int u,int l,int r){
if (l == r){
cnt[u][1][1] = 1; cnt[u][0][1] = cnt[u][1][0] = 1; cnt[u][0][0] = 0;
ln[u] = rn[u] = D[l];
return;
}
int mid = l + r >> 1;
build(ls,l,mid);
build(rs,mid + 1,r);
pup(u);
}
void modify(int u,int l,int r,int L,int R,int v){
if (l >= L && r <= R){
ln[u] += v; rn[u] += v; add[u] += v;
return;
}
pd(u);
int mid = l + r >> 1;
if (mid >= L) modify(ls,l,mid,L,R,v);
if (mid < R) modify(rs,mid + 1,r,L,R,v);
pup(u);
}
struct node{
LL ln,rn,cnt[2][2];
node(){}
node(LL a,LL b,LL c[][2]):ln(a),rn(b) {
cnt[0][0] = c[0][0]; cnt[0][1] = c[0][1];
cnt[1][0] = c[1][0]; cnt[1][1] = c[1][1];
}
};
node query(int u,int l,int r,int L,int R){
if (l >= L && r <= R) return node(ln[u],rn[u],cnt[u]);
pd(u);
int mid = l + r >> 1;
if (mid >= R) return query(ls,l,mid,L,R);
if (mid < L) return query(rs,mid + 1,r,L,R);
node a = query(ls,l,mid,L,R),b = query(rs,mid + 1,r,L,R);
LL c[2][2];
if (a.rn == b.ln){
c[0][0] = a.cnt[0][1] + b.cnt[1][0] - 1;
c[0][1] = a.cnt[0][1] + b.cnt[1][1] - 1;
c[1][0] = a.cnt[1][1] + b.cnt[1][0] - 1;
c[1][1] = a.cnt[1][1] + b.cnt[1][1] - 1;
}
else {
c[0][0] = min(a.cnt[0][0] + b.cnt[1][0],a.cnt[0][1] + b.cnt[0][0]);
c[0][1] = min(a.cnt[0][1] + b.cnt[0][1],a.cnt[0][0] + b.cnt[1][1]);
c[1][0] = min(a.cnt[1][1] + b.cnt[0][0],a.cnt[1][0] + b.cnt[1][0]);
c[1][1] = min(a.cnt[1][1] + b.cnt[0][1],a.cnt[1][0] + b.cnt[1][1]);
}
return node(a.ln,b.rn,c);
}
int main(){
n = read();
REP(i,n) A[i] = read(),D[i] = A[i] - A[i - 1];
build(1,1,n);
Q = read();
char opt; LL l,r,a,b;
while (Q--){
opt = getchar(); while (opt != 'A' && opt != 'B') opt = getchar();
l = read(); r = read();
if (opt == 'A'){
a = read(); b = read();
modify(1,1,n,l,l,a);
if (l < r) modify(1,1,n,l + 1,r,b);
if (r < n) modify(1,1,n,r + 1,r + 1,-(a + (r - l) * b));
}
else {
if (l == r) puts("1");
else{
node u = query(1,1,n,l + 1,r);
printf("%lld\n",u.cnt[1][1]);
}
}
}
return 0;
}