[HAOI2012] 高速公路题解

题目要求我们求期望，先考虑一下求期望的公式。

根据期望的定义得：期望费用 \(E_v = \dfrac{所有可能路线的总费用}{所有可能路线的数量}\).

其中，所有可能路线的数量 \(= C_{R-L+1}^2 = (R-L+1)(R-L)\)，可以在常数时间内计算。（这里用大写的 \(L\)，\(R\) 代替题目中每次询问和修改操作中给出的 \(l\)，\(r\).）在每次询问中，\(R\)，\(L\) 都是不变的。所以对于每次询问，在这个值本身可以当作一个常数，而无需多次计算。下面，主要讨论所有可能路线的总费用的计算。

一般的思维方式是，从路线出发，遍历所有可能的起点与终点，对于每一组起点与终点所确定的路线，计算它的花费，并累加到总花费中。但这样的时间复杂度达到了 \(O(n^2)\) （对于每次询问），而且不好优化。

换一种思路，从每一个路段出发，直接统计它在所有可能的路线中被收费了多少次，再乘上它的花费，就是这个路段对总费用的贡献，即：\(所有可能路线的总费用 v_总 = \sum \limits _{L \le i < R} v_i \times i 收费站收费的次数\).

（注意这个式子中，是“收费站”而不是“路段”，这与题目中描述的不同，题面说的是经过某一条路段会收费，而不是在收费站收费。这里为了方便，把边权转化为点权，即每一条路段的费用转化为这一条路段起点收费站的费用。例如把 \(1 \sim 2\) 收费站之间路段的费用转化为 \(1\) 收费站的费用。这样改变之后，对于一整条路线的费用计算也要相应变化：以 \(l\) 收费站为起点，\(r\) 收费站为终点的路线，其总费用为 \(l\) 到 \(r-1\) 号收费站的费用之和。需要注意的是，对于反方向的行驶，即 \(r < l\) 的情况，费用的计算是相同的，因为题目中说明从 \(i\) 收费站行驶到 \(i+1\) 收费站和从 \(i+1\) 收费站行驶到 \(i\) 收费站的花费是相同的——在化边权为点权之后，这个费用就是 \(i\) 收费站的费用。下面再讨论时，便不再特殊考虑反方向行驶的情况。）

（当然，不把边权化为点权也是可行的，本质上没有区别，只是在考虑边界情况的时候有点不同。这里这样做只是为了方便。）

那么，如何计算 \(i\) 收费站收费的次数呢？设一条路线的起点为 \(l\)，终点为 \(r\)，那么这条路线上收费的收费站应该是 \(l \sim r-1\) 号收费站：注意，因为化边权为点权，所以最后一个收费站并不收费（这也是为什么我说的是“收费的次数”而不是“被经过”的次数）。反过来，对于一个收费站 \(i\) 进行了收费，那么这条路段的起点小于等于 \(i\) 而终点大于 \(i\) （再次强调是大于而不是大于等于），即 \(l \le i < r\). 在 \(L\) 和 \(R\) 都确定的情况下，对于收费站 \(i\)，在被它收费的所有路段中，可以作为起点的收费站有 \((i-L+1)\) 个，可以作为终点的收费站有 \((R-i)\) 个（根据化边权为点权的思想，收费站自己作为起点的时候，这条路段会被它收费，作为终点是则不会，所以是 \((R-i)\) 而不是 \((R-i+1)\)）。根据乘法原理，这些起点和终点所确定的路线有 \((i-L+1)(R-i)\) 条，所以 \(i\) 收费站对总费用的贡献为 \(v_i \times (i-L+1)(R-i)\).

这样一来，每次询问所需的事件复杂度为 \(O(n)\)：遍历 \(L \sim R\) 之间所有的收费站时 \(O(n)\) 的，而对于每一个收费站计算它的贡献是常数时间。但是 \(n\) 和操作次数都为 \(10^5\) 量级，这个时间复杂度仍然不够优。而看到区间修改和区间查询，我们很自然的想到了线段树。

线段树里面需要维护什么？重新审视这个问题，题目中的修改操作不过是简单的区间加，无需多言；而查询操作，根据上文的推导，是在求 \(\sum_{L \le i<R} v_i \times (i-L+1)(R-i)\). 这种形式并不好用线段树查询，因为式子中含有 \(L\)，\(R\) 这两个只在询问中给出的变量，我们应该把这个东西提出到求和符号之外，否则无法用线段树维护。下面开始对式子变形：

\[\begin{aligned} 所有可能路线的总费用 v_总 & = \sum \limits _{l \le i < r} v_i \times i 收费站收费的次数 \\ & = \sum \limits _{l \le i < r} v_i \times (i-l+1)(r-i) \\ & = \sum \limits _{l \le i < r} (ir - i^2 -lr + il + r - i)v_i \\ & = \sum \limits _{l \le i < r} -i^{2}v_i + (l+r-1)iv_i - (r-lr)v_i \\ & = -[\sum \limits _{l \le i < r} i^{2}v_i] + [(l+r-1) \sum \limits _{l \le i < r}iv_i] - [(r-lr)\sum \limits _{l \le i < r}v_i] \end{aligned} \]

这样就成功把 \(L\)，\(R\) 提到了求和符号之外，而求和符号里面的内容有三项：\(v_i\)，\(iv_i\)，\(i^2v_i\)，下面分别用 sv，svi，svii 表示。显然，第一项就是区间和，那么第二项和第三项怎么维护呢？从线段树的几个函数考虑：

合并 update：直接把父节点的值更新为左右子节点的值之和，即

void update(int id)
{
	t[id].sv = t[lson].sv + t[rson].sv;
	t[id].svi = t[lson].svi + t[rson].svi;
	t[id].svii = t[lson].svii + t[rson].svii;
}

下放 pushdown：进行区间加的时候，如何用更新这三个值？\(sv\) 不用再讨论，先考虑 \(svi\)：已知 \(svi_原 = \sum iv_i\)，\(svi_现 = \sum i(v_i+c)\)，要把 \(svi_原\) 修改成 \(svi_现\)，需要添加的值即为二者的差值，即 \(svi_现 - svi_原 = \sum iv_i - i(v_i + c) = \sum ic = c \sum i\). 事实上这与 sv 的修改没有本质区别，只是加上的 \(c\) 系数有所不同。对于这个 \(\sum i\)，这不就是前缀和吗？因为 \(i\) 是连续自然数，所以只要在程序开始先计算一下就可以。同理，对于 \(svii\)，得到 \(svii_现 - svii_原 = \sum i^2v_i - i^2(v_i + c) = \sum i^2c = c \sum i^2\)，其中的 \(\sum i^2\) 也可以用前缀和解决。代码如下：（为了便于观看，把求前缀和和求区间长度写到了 pushdown 外面。）

ll getlen(int id) {return t[id].right - t[id].left + 1;}
ll getsi(int id) {return si[t[id].right] - si[t[id].left - 1];}
ll getsii(int id) {return sii[t[id].right] - sii[t[id].left - 1];} // si，sii 是前缀和
void pushdown(int id)
{
	if(t[id].lazy)
	{
		t[lson].sv += t[id].lazy * getlen(lson), t[rson].sv += t[id].lazy * getlen(rson);
		t[lson].svi += t[id].lazy * getsi(lson), t[rson].svi += t[id].lazy * getsi(rson);
		t[lson].svii += t[id].lazy * getsii(lson), t[rson].svii += t[id].lazy * getsii(rson);
		t[lson].lazy += t[id].lazy, t[rson].lazy += t[id].lazy;
		t[id].lazy = 0;
	}
}

以上两个函数就是线段树维护的核心了，change 和 query 并没有什么特殊的地方，这里便掠过。

总结一下，对于每次求和，用 query 函数求出 \(\sum_{L \le i < R} v_i\)，\(\sum_{L \le i < R} iv_i\)，\(\sum_{L \le i < R} i^2v_i\) ，代入式子计算出所有可能路线的总费用；再 \(O(1)\) 计算出方案数量，然后把二者代入 \(E_v = \dfrac{所有可能路线的总费用}{所有可能路线的数量}\) 中计算出最终的答案。以及，别忘了约分。

至此，这道题的主要思想就讲完了，但是仍然有一些小细节需要注意：

此题要求输出最简分数，所以输出的时候分子分母要同时除以二者的最大公约数（gcd）。gcd 可以用欧几里得算法求得，属于基础内容，这里不做赘述。
考虑边界的问题：change 的时候，右边界必须减一，也就是要写成 change(1, l, r-1, c);，而查询的时候，是否减一都可以，因为即使不减一，最右边的收费站都不会被统计（对于最右边的收费站，式子 \(v_i \times (i-L+1)(R-i)\) 中 \((R-i)\) 这一项为 \(0\)）。
开 long long.

完整代码如下：

// P2221 [HAOI2012] 高速公路
#include<bits/stdc++.h>
#define lson (id << 1)
#define rson (id << 1 | 1)

using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;
int n, m;
ll si[MAXN], sii[MAXN];// const. sum of 1~n, sum of 1^2~n^2
ll sum1, sum2, sum3; // only used in main
struct Node
{
	int left, right;
	ll lazy;
	ll sv, svi, svii; // sum of value, sum of value*i, sum of value*i*i
}t[MAXN << 2];

template<typename T> T gcd(T a, T b)
{
	if(b > a) return gcd(b, a);
	return b ? gcd(b, a % b) : a;
}

inline ll getlen(int id) {return t[id].right - t[id].left + 1;}
inline ll getsi(int id){return si[t[id].right] - si[t[id].left - 1];}
inline ll getsii(int id){return sii[t[id].right] - sii[t[id].left - 1];}

void update(int id)
{
	t[id].sv = t[lson].sv + t[rson].sv;
	t[id].svi = t[lson].svi + t[rson].svi;
	t[id].svii = t[lson].svii + t[rson].svii;
}

void pushdown(int id)
{
	if(t[id].lazy)
	{
		t[lson].sv += t[id].lazy * getlen(lson), t[rson].sv += t[id].lazy * getlen(rson);
		t[lson].svi += t[id].lazy * getsi(lson), t[rson].svi += t[id].lazy * getsi(rson);
		t[lson].svii += t[id].lazy * getsii(lson), t[rson].svii += t[id].lazy * getsii(rson);
		t[lson].lazy += t[id].lazy, t[rson].lazy += t[id].lazy;
		t[id].lazy = 0;
	}
}

void buildtree(int id, int l, int r)
{
	t[id].left = l, t[id].right = r;
	if(l == r) return; // sv,svi,svii = 0
	int mid = (l + r) >> 1;
	buildtree(lson, l, mid), buildtree(rson, mid + 1, r);
}

void change(int id, int l, int r, ll c)
{
	if(l == t[id].left && r == t[id].right)
	{
		t[id].lazy += c;
		t[id].sv += c*getlen(id), t[id].svi += c*getsi(id), t[id].svii += c*getsii(id);
		return;
	}
	pushdown(id);
	if(r <= t[lson].right) change(lson, l, r, c);
	else if(l >= t[rson].left) change(rson, l, r, c);
	else change(lson, l, t[lson].right, c), change(rson, t[rson].left, r, c);
	update(id);
}

void query(int id, int l, int r)
{
	if(l == t[id].left && r == t[id].right)
	{
		sum1 += t[id].sv;
		sum2 += t[id].svi;
		sum3 += t[id].svii;
		return;
	}
	pushdown(id);
	if(r <= t[lson].right) query(lson, l, r);
	else if(l >= t[rson].left) query(rson, l, r);
	else query(lson, l, t[lson].right), query(rson, t[rson].left, r);
}

int main()
{
	scanf("%d%d", &n, &m);
	buildtree(1, 1, n);
	for(ll i = 1; i <= n; i++) si[i] = si[i-1] + i, sii[i] = sii[i-1] + i*i;
	while(m--)
	{
		char str[5]; int l, r; ll c;
		scanf("%s%d%d", str, &l, &r);
		if(str[0] == 'C')
		{
			scanf("%lld", &c);
			change(1, l, r-1, c); // can not be change(1, l, r, c)
		}
		else if(str[0] == 'Q')
		{
			sum1 = sum2 = sum3 = 0;
			query(1, l, r-1); // query(1,l,r) is also ok 
			ll num = 1ll * (r-l+1) * (r-l) / 2, val = -sum3 + (l+r-1) * sum2 + (r-1ll*l*r) * sum1; // l*r > int 
			ll g = gcd(num, val), _num = num/g, _val = val/g;
			printf("%lld/%lld\n", _val, _num);
		}
	}
	return 0;
}