题目地址：洛谷：【P4243】[JSOI2009]等差数列 – 洛谷、BZOJ：Problem 1558. — [JSOI2009]等差数列

题目背景

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

题目描述

为了检验学生的掌握情况，jyy布置了一道习题：给定一个长度为N （1≤N≤100,000）的数列，初始时第i个数为vi（vi是整数，−100,000≤vi≤100,000），学生们要按照jyy的给出的操作步骤来改变数列中的某些项的值。操作步骤的具体形式为：A s t a b （s, t, a, b均为整数，1≤s≤t≤N，−100,000≤a,b≤100,000），它表示，在序列的[s, t]区间上加上初值为a，步长为b的等差数列。即vi变为v_i + a + b \times (i - s)（对于s≤i≤t）。
在焦头烂额地计算之余，可怜的火星学生们还得随时回答jyy提出的问题。问题形式为：B s t（s, t均为整数，1≤s≤t≤N），表示jyy询问当前序列的[s, t]区间最少能划分成几段，使得每一段都是等差数列。比如说1 2 3 5 7最少能划分成2段，一段是1 2 3，另一段是5 7。询问是需要同学们计算出答案后，作为作业交上来的。
虽然操作数加问题数总共只有Q（1≤Q≤100,000）个，jyy还是觉得这个题很无聊很麻烦。于是他想让你帮他算一份标准答案。

输入输出格式

输入格式：
第1行：1个整数N，第2…N+1行：每行一个整数。第i+1行表示vi。
第N+2行：1个整数Q，第N+3…N+Q+2行：每行描述了一个操作或问题，格式如题中所述，不含引号。

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

输入输出样例

输入样例#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≤5000。
对100%的数据，1≤N,Q≤100,000。
其他数据范围见题面。

题解

本题题解思路来自bzoj1558 [JSOI2009]等差数列 – zbtrs – 博客园，感谢原作者。

转化：差分数列

看到维护等差数列，我们想到维护这个数列的差分数列。
差分数列是啥呀？简单来说就是把数列的每项换成相邻两项的差值，也就是说，b_i = a_{i+1} - a_i。等差数列在差分数列中的表现就是连续一段相同值，这个值就是等差数列的公差（或者叫步长）。
让我们探索一下在差分数列上加等差数列操作应该怎么做。可以发现这个操作只影响首项和前一项（l-1）、末项和后一项（r）的值。用线段树维护这个序列就是两个单点加加一个区间加公差。

询问：如何合并区间信息？

假如我们已经有了一个差分数列，连续的相同数字这一段就是一个等差数列，那么零散的不连续值呢？
让我们举个例子：
1 2 3 (4 4 4) 1 2 (3 3) 1 2差分数列
1 2 4 (7 11 15 19) 20 (22 25 28) 29 31原数列
显然原数列中那些属于零散值的数字可以成对构成等差数列。也就是说，连续一段零散值能构成的等差数列数量应该是这一段的长度/2。
接下来是一个问题：差分数列上一段数对应原数列中的长度应该+1，为什么直接/2是正确的呢？当我们求数列中间的一段零散值，实际上左右两边都是等差数列。如果使左右两边等差数列的长度最大，实际上原数列中零散的数量应该是-1的，因为左右端点被包含进左右的等差数列了。如果是左右端的零散值，则有一端无法包含进等差数列，原数列对应的长度即为差分数列零散值的长度。
这一段是很多博主并没有注明的细节，我在理解中也遇到了困惑，在这里特别讲解了一下。
为什么我们需要知道以上内容呢？因为维护左右两端的零散值数量方便区间的合并，而区间合并是线段树的基本操作。

线段树题的套路

区间记下什么？

记下这个区间左右两端的零散值长度、左右两端点值（合并区间时检查左儿子的右端和右儿子的左端是否值相等，即并成一个等差数列）、除了零散值以外的那一段能够划分成最少多少等差数列、区间长度。另外区间加操作的lazy标记在这里也是可以用的。

怎么设置初值？

从长度为1的区间开始设置初值即可。

重要！怎么合并左右儿子上传的信息？

不可避免地，这题会遇到分类讨论。下面让我们慢慢地整理一下。
默认：本区间划分数为左右儿子划分数之和。

1.左右儿子都是纯零散值
需要检查左儿子的右端点和右儿子的左端点是否相等。（以下省略这句话）
相等→中间构成长为2的等差数列，左端零散值长为左儿子-1，右端零散值长为右儿子-1，本区间内除两端零散值以外的部分的划分数（以下简称划分数）为1。
不相等→左右两端零散值长都为本区间长，划分数为0。
2.左儿子是纯零散值，右儿子不是
本区间右端零散值长为右儿子右端零散值长。
相等→中间构成长为2的等差数列，左端零散值长为左儿子-1，将右儿子左端零散值构成的等差数列数加入划分数。
不相等→将左儿子和右儿子左端零散值合并作为本区间左端零散值。
3.右儿子是纯零散值，左儿子不是
从2情况翻转一下即可。自己推一下吧。

以下情况即可认为：本区间左端零散值长等于左儿子左端零散值长，右端同理。
4.左儿子右端和右儿子左端无零散值
相等→划分数要-1，除去重复计算的跨左右儿子的等差数列。
不相等→算到当前步骤的结果就是本区间结果。
5.左儿子右端无零散值，右儿子左端有零散值
不相等→将右儿子左端零散值构成的等差数列数加入划分数。
相等→加入后-1，理由同上。
6.右儿子左端无零散值，左儿子右端有零散值
从5情况翻转一下即可。自己推一下吧。
7.除上的一般情况
不相等→将左儿子右端和右儿子左端零散值构成的等差数列数加入划分数。
相等→左儿子右端和右儿子左端零散值数先都-1再计算构成等差数列数，加入划分数后加1，为了特殊处理跨左右儿子的等差数列。

到此所有的情况都讨论完成了。把这些情况写全了就不会出事。

总结一下

这个题是个线段树直接维护答案的题，关键点在差分数列和区间合并的讨论。细节处理很要命，考场上要冷静分析，讨论全面。我反正是写不出的（笑）。
其他细节参考一下底下的代码吧，自认为代码风格还是很整洁的。没有注释可能看起来比较费劲。可以尝试对应着上面的解析看。

代码

注：区间信息中，l、r是左右端点值，llen、rlen是左右端零散值长，ans是划分数，tag是lazy标记，siz是区间长。

// Code by KSkun, 2018/2 
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc(); 
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

LL n, q, s, t, a, b;
char op;

inline bool isop(char c) {
    return c == 'A' || c == 'B';
}

inline char readop() {
    char c = fgc();
    while(!isop(c)) c = fgc();
    return c;
}

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

struct Data {
    LL l, r, llen, rlen, ans, tag, siz;
} tree[MAXN << 2];

LL val[MAXN];

inline void pushdown(int o) {
    if(tree[o].tag) {
        tree[lch].tag += tree[o].tag;
        tree[lch].l += tree[o].tag;
        tree[lch].r += tree[o].tag;
        tree[rch].tag += tree[o].tag;
        tree[rch].l += tree[o].tag;
        tree[rch].r += tree[o].tag;
        tree[o].tag = 0;
    }
}

inline void merge(Data *dest, Data lson, Data rson) {
    Data *rt = dest, *ls = &lson, *rs = &rson;
    bool flag = ls->r == rs->l;
    memset(rt, 0, sizeof(Data));
    rt->siz = ls->siz + rs->siz;
    rt->l = ls->l;
    rt->r = rs->r;
    rt->ans = ls->ans + rs->ans;
    if(ls->ans == 0 && rs->ans == 0) {
        if(flag) {
            rt->llen = ls->llen - 1;
            rt->rlen = rs->rlen - 1;
            rt->ans++;
        } else {
            rt->llen = rt->rlen = rt->siz;
        }
        return;
    }
    if(ls->ans == 0) {
        rt->rlen = rs->rlen;
        if(flag) {
            rt->llen = ls->llen - 1;
            if(rs->llen) {
                rt->ans += (rs->llen - 1) / 2 + 1;
            }
        } else {
            rt->llen = ls->siz + rs->llen;
        }
        return;
    }
    if(rs->ans == 0) {
        rt->llen = ls->llen;
        if(flag) {
            rt->rlen = rs->rlen - 1;
            if(ls->rlen) {
                rt->ans += (ls->rlen - 1) / 2 + 1;
            }
        } else {
            rt->rlen = rs->siz + ls->rlen;
        }
        return;
    }
    rt->llen = ls->llen;
    rt->rlen = rs->rlen;
    if(ls->rlen == 0 && rs->llen == 0) {
        if(flag) {
            rt->ans--;
        }
        return;
    }
    if(ls->rlen == 0) {
        if(flag) {
            rt->ans += (rs->llen - 1) / 2;
        } else {
            rt->ans += rs->llen / 2;
        }
        return;
    }
    if(rs->llen == 0) {
        if(flag) {
            rt->ans += (ls->rlen - 1) / 2
        } else {
            rt->ans += ls->rlen / 2;
        }
        return;
    }
    LL toadd = (ls->rlen + rs->llen) / 2;
    if(flag) {
        toadd = std::min(toadd, (ls->rlen - 1) / 2 + (rs->llen - 1) / 2 + 1);
    }
    rt->ans += toadd;
} 

inline void build(int o, int l, int r) {
    if(l == r) {
        tree[o].l = tree[o].r = val[l];
        tree[o].llen = tree[o].rlen = tree[o].siz = 1;
        return;
    }
    build(lch, l, mid);
    build(rch, mid + 1, r);
    merge(&tree[o], tree[lch], tree[rch]);
}

inline void add(int o, int l, int r, int ll, int rr, LL v) {
    if(l >= ll && r <= rr) {
        tree[o].l += v;
        tree[o].r += v;
        tree[o].tag += v;
        return;
    }
    pushdown(o);
    if(mid >= ll) {
        add(lch, l, mid, ll, rr, v);
    }
    if(mid < rr) {
        add(rch, mid + 1, r, ll, rr, v);
    }
    merge(&tree[o], tree[lch], tree[rch]);
}

inline Data query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return tree[o];
    }
    pushdown(o);
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        Data res;
        merge(&res, query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
        return res; 
    }
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        val[i] = readint();
    }
    for(int i = 1; i <= n - 1; i++) {
        val[i] = val[i + 1] - val[i];
    }
    n--;
    build(1, 1, n);
    q = readint();
    while(q--) {
        op = readop();
        if(op == 'A') {
            s = readint();
            t = readint();
            a = readint();
            b = readint();
            if(s > 1) {
                add(1, 1, n, s - 1, s - 1, a);
            }
            if(t <= n) {
                add(1, 1, n, t, t, -(a + (t - s) * b));
            }
            if(s < t) {
                add(1, 1, n, s, t - 1, b);
            }
        } 
        if(op == 'B') {
            s = readint();
            t = readint();
            if(s == t) {
                printf("1\n");
                continue;
            }
            Data res = query(1, 1, n, s, t - 1);
            LL ans = (t - s + 2) / 2;
            if(res.ans == 0) {
                printf("%lld\n", ans);
            } else {
                ans = std::min(ans, res.ans + (res.llen + 1) / 2 + (res.rlen + 1) / 2);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}