题解 P4243 【[JSOI2009]等差数列】
KSkun
2018-02-21 19:12:47
# 题解
本题题解思路来自[bzoj1558 [JSOI2009]等差数列 - zbtrs - 博客园](https://www.cnblogs.com/zbtrs/p/8424737.html)，感谢原作者。
本题题解同步发布于我的博客[[JSOI2009]等差数列 题解 | KSkun's Blog](https://ksmeow.moe/array_jsoi09_sol/)，欢迎来逛~
## 转化：差分数列
看到维护等差数列，我们想到维护这个数列的差分数列。
差分数列是啥呀？简单来说就是把数列的每项换成相邻两项的差值，也就是说，$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`是区间长。*
```cpp
// 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;
}
```