$\texttt{Description}$

给你一个数列 $a$，长度为 $n-1$，每次操作可以将一段区间内的数字加上 $v$，也可以查询 $\sum\limits^{i\le r}_{i=l}\sum\limits^{j\le r}_{j=i}\sum\limits^{k\le r}_{k=l} a_i$。

然后你会发现这题挂着期望的标签其实就是套着期望的外壳出数据结构题。

$\texttt{solution}$

采用什么数据结构？

~~别告诉我你连这是个数据结构题都看不出来~~

数据范围 $n\le 10^5$。这是省选题，不可能给你太宽裕的时限，所以大概就是 $O(n\sqrt{n})$ 的分块或者 $O(nlogn)$ 的巨大常数线段树。个人更喜欢线段树，所以一开始就往线段树方面想了（主要是感觉这题线段树好做）。

线段树的每个节点维护什么？

设这个节点表示的区间为 $[l,r]$，则维护一个值 $w$ 表示 $\sum\limits^{i\le r}_{i=l}\sum\limits^{j\le r}_{j=i}\sum\limits^{k\le r}_{k=l} a_i$。

如何合并左右子树的信息？

左右子树光有这个 $w$ 显然我们没法合并。因为要考虑跨过左右子树的区间。那么，设左子树表示的区间为 $[l,mid]$，~~柚子树~~右子树表示的区间为 $[mid+1,r]$。

那么跨过左右子树的区间和就是：

$(r-mid)\times \sum\limits^{i\le mid}_{i=l}a_i\times (i-l+1)+(mid-l+1)\times \sum\limits^{i\le r}_{i=mid+1}a_i\times (r-i+1)$。

式子看起来挺恶心，但是我们会发现加号左边的部分就是左子树表示的区间的前缀和之和乘上右子树表示的区间的长度，加号右边的就是右子树表示区间的后缀和之和乘上左子树表示的区间长度。

因此对于每个节点，额外开辟两个变量 $sum1,sum2$。前者表示前缀和之和，后者表示后缀和之和。

那问题来了，似乎光有上面的信息，$sum1$ 和 $sum2$ 又没法通过左右子树的信息计算了？

~~完了无限递归了快跑不做了~~

其实我们只需要再额外新建一个变量 $sum$ 表示整个区间的和~~不会吧不会吧都是学过线段树的还有不会合并这个的吗~~，然后前缀和之和与后缀和之和就水到渠成了。自己动手画一下就会发现。

所以合并（pushup）代码如下：

c[O].w = c[O << 1].w + c[O << 1 | 1].w + c[O << 1].sum2 * (r - mid) + c[O << 1 | 1].sum1 * (mid - l + 1);
c[O].sum = c[O << 1].sum + c[O << 1 | 1].sum;
c[O].sum1 = c[O << 1].sum1 + c[O << 1 | 1].sum1 + c[O << 1].sum * (r - mid);
c[O].sum2 = c[O << 1].sum2 + c[O << 1 | 1].sum2 + c[O << 1 | 1].sum * (mid - l + 1);

查询时候的区间信息合并类似。

Lazytag如何处理？

sum变量很好处理Lazytag。sum1和sum2也比较容易，只需要计算lazytag乘上区间长度乘上区间长度加一除以二。

重点在于 $w$ 变量。设当前需要给整个区间加上 $x$，则 $w$ 需要加上多少？

设 $l$ 为区间长度，依次考虑这个区间内长度为 $1,2,3…l$ 的子区间。不难发现 $w$ 需要增加 $\sum\limits^{i\le l}_{i=1}\times (n-i-1)\times x$。

这个式子显然我们需要预处理 $p_i=\sum\limits^{j\le i}_{j=1}\times (n-j-1)$。而预处理还要讲究，不能暴力根据定义预处理，否则努力就白费了，跑得比暴力还慢。

手算可得递推式：$p_i=p_{i-1}+i\times (i+1)\div 2$。

因此Lazytag的处理如下：

if (L <= c[O].l && c[O].r <= R) {
	int t(c[O].r - c[O].l + 1);
	c[O].w += p[t] * d, c[O].Lazy += d, c[O].sum += t * d;
	c[O].sum1 += t * (t + 1) / 2 * d, c[O].sum2 += t * (t + 1) / 2 * d;
	return;
}

有了这些，在细节上还需注意query的时候，为了区间合并的方便，我把返回值设成了一个四元组。

~~血泪史就是式子推错了 $\infty$ 次~~

$\texttt{code}$

#include <cstdio>
#define int long long

typedef long long ll;
inline int min(const int x, const int y) {return x < y ? x : y;}
inline int max(const int x, const int y) {return x > y ? x : y;}
int gcd(ll x, ll y) {return y ? gcd(y, x % y) : x;}
ll p[100005];
struct Node {
	int l, r, Lazy;
	ll w, sum, sum1, sum2;
} c[400005];
struct Tuple {ll w, sum, sum1, sum2;};

void make_tree(const int O, const int L, const int R) {
	c[O].l = L, c[O].r = R;
	if (L != R) make_tree(O << 1, L, L + R >> 1), make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
}
inline void pushdown(const int O) {
	int t(c[O].Lazy), l(c[O].l), r(c[O].r);
	int lt(c[O << 1].r - c[O << 1].l + 1), rt(c[O << 1 | 1].r - c[O << 1 | 1].l + 1);
	c[O << 1].w += p[lt] * t, c[O << 1].Lazy += t, c[O << 1].sum += lt * t;
	c[O << 1].sum1 += lt * (lt + 1) / 2 * t, c[O << 1].sum2 += lt * (lt + 1) / 2 * t;
	c[O << 1 | 1].w += p[rt] * t, c[O << 1 | 1].Lazy += t, c[O << 1 | 1].sum += rt * t;
	c[O << 1 | 1].sum1 += rt * (rt + 1) / 2 * t, c[O << 1 | 1].sum2 += rt * (rt + 1) / 2 * t;
	c[O].Lazy = 0;
}

void update(const int O, const int L, const int R, const int d) {
	if (L <= c[O].l && c[O].r <= R) {
		int t(c[O].r - c[O].l + 1);
		c[O].w += p[t] * d, c[O].Lazy += d, c[O].sum += t * d;
		c[O].sum1 += t * (t + 1) / 2 * d, c[O].sum2 += t * (t + 1) / 2 * d;
		return;
	}
	pushdown(O);
	if (c[O << 1].r >= L) update(O << 1, L, R, d);
	if (c[O << 1 | 1].l <= R) update(O << 1 | 1, L, R, d);
	const int l(c[O].l), r(c[O].r), mid(l + r >> 1);
	c[O].w = c[O << 1].w + c[O << 1 | 1].w + c[O << 1].sum2 * (r - mid) + c[O << 1 | 1].sum1 * (mid - l + 1);
	c[O].sum = c[O << 1].sum + c[O << 1 | 1].sum;
	c[O].sum1 = c[O << 1].sum1 + c[O << 1 | 1].sum1 + c[O << 1].sum * (r - mid);
	c[O].sum2 = c[O << 1].sum2 + c[O << 1 | 1].sum2 + c[O << 1 | 1].sum * (mid - l + 1);
}
Tuple query(const int O, const int L, const int R) {
	if (L <= c[O].l && c[O].r <= R) return Tuple{c[O].w, c[O].sum, c[O].sum1, c[O].sum2};
	pushdown(O);
	if (c[O << 1].r < L) return query(O << 1 | 1, L, R);
	if (c[O << 1 | 1].l > R) return query(O << 1, L, R);
	Tuple ls(query(O << 1, L, R)), rs(query(O << 1 | 1, L, R));
	const int l(max(c[O].l, L)), r(min(c[O].r, R)), mid(c[O].l + c[O].r >> 1);
	return Tuple{ls.w + rs.w + ls.sum2 * (r - mid) + rs.sum1 * (mid - l + 1),
	ls.sum + rs.sum, ls.sum1 + rs.sum1 + ls.sum * (r - mid), ls.sum2 + rs.sum2 + rs.sum * (mid - l + 1)};
}

signed main() {
	int n, m;
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= n; ++ i) p[i] = p[i - 1] + i * (i + 1) / 2;
	make_tree(1, 1, n - 1);
	while (m --) {
		int l, r;
		char op;
		scanf(" %c%lld%lld", &op, &l, &r);
		if (op == 'C') {
			int x;
			scanf("%lld", &x);
			if (l < r) update(1, l, r - 1, x);
		}
		else if (l < r) {
			long long a(query(1, l, r - 1).w << 1), b((r - l) * (r - l + 1));
			printf("%lld/%lld\n", a / gcd(a, b), b / gcd(a, b));
		}
		else puts("0/1");
	}
}

zqs`s blog

洛谷P2221题解

$\texttt{Description}$

$\texttt{solution}$

$\texttt{code}$