题解 P2221 【[HAOI2012]高速公路】

这道题让我们求边,因为题目是一条链,所以直接采用把边编上号.看成序列即可. $1$与$2$号点的边连得是. 编号为$1$的点.查询的时候把$r - 1$就好了. 这里的期望显然就是路径的平均值. 期望值: $$\dfrac{\sum_{i=l}^r\sum_{j=l}^{r}dis[i][j]}{C_{r-l+1}^2}$$ 下面部分可以直接算出: 上面这一部分比较难维护. 考虑每一条边会被走过多少次. $$ans = \sum_{i=l}^ra[i]*(r-i+1)(i-l+1)$$ 相当于枚举这个点左右两条路. 然后拆开. 再化简一下式子. 形成下面这个模样. $$ans = (r - l + 1 - r * l) * sum1 + (r + l) * sum2 - sum3$$ 其中 $sum1 = \sum_{i=l}^r a[i]$ $sum2 = \sum_{i=l}^r a[i]*i$ $sum3 = \sum_{i=l}^r a[i] * i * i$ 然后我们用线段树维护一下. 考虑合并. $sum1 = lson_{sum1} + rson_{sum1}$ $sum2 = lson_{sum2} + rson_{sum2}$ $sum3 = lson_{sum3} + rson_{sum3}$ 合并是比较简单了. 添加值得时候如何添加? 设添加的值为$k$ 此时的式子就变成了. $sum1$比较简单,直接加上区间的长度乘以$k$即可. $sum2$要加上$k*\sum i$然后维护一下区间$i$的和.我们称它为$sum5$,或者考虑等差数列求和的方法也可以. $sum3$要加上$k * \sum i ^2$我们这里必须要维护$sum4$,它代表$\sum i^2$ $sum4$ 和 $sum5$ 是一个定值.在建树的时候更新就行了. 然后这个题就完成了. 特别注意的是.由于我们**设边为点**.所以要$r -= 1$ 如果直接$r -=1$的话,下面的分母要改成.$C_{r-l + 2}^2$ ## 最后,打个广告:[My blog](https://www.cnblogs.com/tpgzy/) CODE: ```cpp #include <iostream> #include <cstdio> #define lson now << 1 #define rson now << 1 | 1 #define ll long long const ll maxN = 100000 + 7; inline ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();} return x * f; } ll gcd(ll a,ll b) { return !b ? a : gcd(b,a % b); } struct Node { ll sum[6]; ll lazy; ll l,r; }tree[maxN << 2]; ll sum1,sum2,sum3; void updata(ll now) { tree[now].sum[1] = tree[lson].sum[1] + tree[rson].sum[1]; tree[now].sum[2] = tree[lson].sum[2] + tree[rson].sum[2]; tree[now].sum[3] = tree[lson].sum[3] + tree[rson].sum[3]; return ; } void build(ll l,ll r,ll now) { tree[now].l = l;tree[now].r = r; if(l == r) { tree[now].sum[4] = l * l; tree[now].sum[5] = l; return ; } ll mid = (l + r) >> 1; build(l,mid,lson); build(mid + 1,r,rson); tree[now].sum[4] = tree[lson].sum[4] + tree[rson].sum[4]; tree[now].sum[5] = tree[lson].sum[5] + tree[rson].sum[5]; return ; } void work(ll now,ll k) { tree[now].sum[1] += (tree[now].r - tree[now].l + 1) * k; tree[now].sum[2] += k * tree[now].sum[5]; tree[now].sum[3] += k * tree[now].sum[4]; tree[now].lazy += k; } void pushdown(ll now) { work(lson,tree[now].lazy); work(rson,tree[now].lazy); tree[now].lazy = 0; return ; } void modify(ll l,ll r,ll now,ll val) { if(tree[now].l >= l && tree[now].r <= r) { work(now,val); return ; } if(tree[now].lazy) pushdown(now); ll mid = (tree[now].l + tree[now].r) >> 1; if(mid >= l) modify(l,r,lson,val); if(mid < r) modify(l,r,rson,val); updata(now); return ; } void query(ll l,ll r,ll now) { if(tree[now].l >= l && tree[now].r <= r) { sum1 += tree[now].sum[1]; sum2 += tree[now].sum[2]; sum3 += tree[now].sum[3]; return ; } if(tree[now].lazy) pushdown(now); ll mid = (tree[now].l + tree[now].r) >> 1; if(mid >= l) query(l,r,lson); if(mid < r) query(l,r,rson); return ; } int main() { ll n,m,l,r,v; char s[3]; n = read();m = read(); build(1,n,1); while(m --) { scanf("%s",&s); l = read();r = read() - 1; if(s[0] == 'C') { v = read(); modify(l,r,1,v); } else { ll a; sum1 = sum2 = sum3 = 0; query(l,r,1); a = (r - l + 1 - r * l) * sum1 + (r + l) * sum2 - sum3; ll b = ( r - l + 2 ) * (r - l + 1) / 2; ll g = gcd(a,b); printf("%lld/%lld\n", a / g,b / g); } } return 0; } ```