自动搬运

查看原文

来自洛谷，原作者为

	KSkun May all the beauty be blessed.

搬运于2025-08-24 21:58:03，当前版本为作者最后更新于2018-02-21 19:12:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

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

本题题解同步发布于我的博客[JSOI2009]等差数列 题解 | KSkun's Blog，欢迎来逛~

转化：差分数列

看到维护等差数列，我们想到维护这个数列的差分数列。 差分数列是啥呀？简单来说就是把数列的每项换成相邻两项的差值，也就是说，$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;
}