Acwing2370 等差数列

题目背景

“一个长度为$l$的数列$a_i$，若相邻两数间的差$a_i - a_{i-1} \ (2 \leq i \leq l)$全部相同，则这个数列为等差数列。”火星特级数学老师jyy，正在给他的火星学生们上数学课。

题目描述

为了检验学生的掌握情况，jyy布置了一道习题：给定一个长度为$N$（$1 \leq N \leq 100,000$）的数列，初始时第$i$个数为$v_i$（$v_i$是整数，$-100,000 \leq v_i \leq 100,000$），学生们要按照jyy的给出的操作步骤来改变数列中的某些项的值。操作步骤的具体形式为：A s t a b （$s, t, a, b$均为整数，$1 \leq s \leq t \leq N$，$-100,000 \leq a, b \leq 100,000$），它表示，在序列的$[s, t]$区间上加上初值为$a$，步长为$b$的等差数列。即$v_i$变为$v_i + a + b \times (i - s)$（对于$s \leq i \leq t$）。

在焦头烂额地计算之余，可怜的火星学生们还得随时回答jyy提出的问题。问题形式为：B s t（$s, t$均为整数，$1 \leq s \leq t \leq N$），表示jyy询问当前序列的$[s, t]$区间最少能划分成几段，使得每一段都是等差数列。比如说1 2 3 5 7最少能划分成$2$段，一段是1 2 3，另一段是5 7。询问是需要同学们计算出答案后，作为作业交上来的。

虽然操作数加问题数总共只有$Q$（$1 \leq Q \leq 100,000$）个，jyy还是觉得这个题很无聊很麻烦。于是他想让你帮他算一份标准答案。

输入格式

第$1$行：$1$个整数$N$，第$2 \cdots N + 1$行：每行一个整数。第$i + 1$行表示$v_i$。

第$N + 2$行：$1$个整数$Q$，第$N + 3 \cdots N + Q + 2$行：每行描述了一个操作或问题，格式如题中所述，不含引号。

输出格式

若干行，每行一个整数，表示对一个问题的回答。请按照输入中的顺序依次给出回答。

输入输出样例 #1

输入 #1

5
1
3
-1
-4
7
2
A 2 4 -1 5
B 1 5

输出 #1

2

说明/提示

样例说明：

原数列1 3 -1 -4 7。经过操作之后，数列变为1 2 3 5 7。如题中所述，最少能划分成$2$段。

数据规模：

对$30\%$的数据，$N, Q \leq 5000$。

对$100\%$的数据，$1 \leq N, Q \leq 100,000$。

思路：

第一眼看到是维护一个区间，直接使用线段树尝试解决

转化：

因为每一次相加与查询都是等差数列，于是将原数组转化为差分数列维护 （想不到可以看标签）

问1：如何进行修改：

因为每次进行区间加法时是等差数列，所以加在差分数组上时，可以对于三种进行分析 ：
part 1
s<i<t s[i]=a[i+1]+a+b?(i+1?s)-a[i]-a-b*(i-s)=s[i]+b
s[i]=s[i]+b

part 2

i=s && i!=1 s[i]=a[i+1]+a+b*(s-s)-a[i]=a[i+1]+a-a[i]=s[i]+a
s[i]=s[i]+a

part 3

i=t && i!=n s[i]=a[i+1]-a[i]-a-b(i-s)=s[i]-(a+b(t-s))
s[i]=s[i](a+b(t-s))

问2：如何进行区间合并：

我们最后查询的是区间内等差数列的个数，所以一定要维护的必然有当前区间等差数列的个数
我们可以继续思考：当前区间等差数列的个数有什么推出来？
首先我们把原数列划分成几段等差数列的时候可以发现，差分数列上划分出的每一段的第一个数是可以任意的，而后面的数作为公差都要相同，因此合并的时候我们也要考虑这个性质。即合并两个子区间的时候，可以不计算某一端点作为等差数列公差时的贡献，而是作为等差数列的第一个数。当然当左区间右端点和右区间左端点相同时，我们可以将其合并成一个区间。
所以我们用线段树去分别维护 [l,r] 区间中左右端点的值，[l,r] , [l,r) , (l,r] , (l,r) 四个区间最少能划分成几个等差数列。即s[0].s[1],s[2],s[3]

t[p].x=t[lc].x+t[rc].x;
//pushup
node operator +(node x,node y){//合并序列
    node z;
    z.l=x.l;
    z.r=y.r;
    //Min表示在三个数中取最小
    z.s[0]=Min(x.s[2]+y.s[1]-(x.r==y.l),x.s[0]+y.s[1],x.s[2]+y.s[0]);
    z.s[1]=Min(x.s[3]+y.s[1]-(x.r==y.l),x.s[1]+y.s[1],x.s[3]+y.s[0]);
    z.s[2]=Min(x.s[2]+y.s[3]-(x.r==y.l),x.s[2]+y.s[2],x.s[0]+y.s[3]);
    z.s[3]=Min(x.s[3]+y.s[3]-(x.r==y.l),x.s[1]+y.s[3],x.s[3]+y.s[2]);
    return z;
}

注意：无论两个数差值多大或多小,这两个数都是等差数列

C++ 代码

#include<bits/stdc++.h>
#define ll long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=1e5+5;
int n,q;
int a[N];
int Min(int a,int b,int c){return min(min(a,b),c);}
struct node{//要维护的信息
    int s[5],l,r;
    //l为左边的值,r为右边的值 (序列)
    //s[0] 左右端点都不选 
    //s[1] 只选左端点 
    //s[2] 只选右端点
    //s[3] 左右端点都选
};
node operator +(node x,node y){//合并序列
    node z;
    z.l=x.l;
    z.r=y.r;
    z.s[0]=Min(x.s[2]+y.s[1]-(x.r==y.l),x.s[0]+y.s[1],x.s[2]+y.s[0]);
    z.s[1]=Min(x.s[3]+y.s[1]-(x.r==y.l),x.s[1]+y.s[1],x.s[3]+y.s[0]);
    z.s[2]=Min(x.s[2]+y.s[3]-(x.r==y.l),x.s[2]+y.s[2],x.s[0]+y.s[3]);
    z.s[3]=Min(x.s[3]+y.s[3]-(x.r==y.l),x.s[1]+y.s[3],x.s[3]+y.s[2]);
    return z;
}
struct tree{//线段树
    int l,r;
    ll tag;
    node x;
}t[N<<3]; 
inline int read(){
    int f=1,ans=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans*f;
}
void build(int p,int l,int r){//建树
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].x.l=t[p].x.r=a[l];
        t[p].x.s[0]=0;
        t[p].x.s[1]=t[p].x.s[2]=t[p].x.s[3]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    t[p].x=t[lc].x+t[rc].x;
}
void pushdown(int p){
    if(t[p].tag == 0)return ;
    t[lc].tag+=t[p].tag,t[rc].tag+=t[p].tag;
    t[lc].x.l+=t[p].tag,t[rc].x.l+=t[p].tag;
    t[lc].x.r+=t[p].tag,t[rc].x.r+=t[p].tag;
    t[p].tag=0;
    return ;
}
void change(int p,int x,int y,int k){
    if(x<=t[p].l && t[p].r<=y){
        t[p].x.l+=k;
        t[p].x.r+=k;
        t[p].tag+=k;
        return ;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid)change(lc,x,y,k);
    if(y>mid)change(rc,x,y,k);
    t[p].x=t[lc].x+t[rc].x; 
}
node ask(int p,int x,int y){
    if(x<=t[p].l && t[p].r<=y)return t[p].x;
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(y<=mid)return ask(lc,x,y);
    if(x>mid)return ask(rc,x,y);
    return ask(lc,x,y)+ask(rc,x,y);
}
int main(){
    int root=0; 
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)a[i]=a[i+1]-a[i]; 
    build(1,1,n-1);
    q=read();
    char op;
    int s,t,x,y;
    while(q--){
        cin>>op;
        if(op=='A'){
            s=read(),t=read(),x=read(),y=read();
            if(s!=1)change(1,s-1,s-1,x);
            if(t!=n)change(1,t,t,-(x+y*(t-s)));
            if(s!=t)change(1,s,t-1,y);

        }else {
            s=read(),t=read();
            if(s==t)cout<<"1\n";
            else {
                node ans=ask(1,s,t-1);
                cout<<ans.s[3]<<'\n';
            }
        }
    }
    return 0;
}