洛谷P2221 高速公路【线段树】
题目：https://www.luogu.org/problemnew/show/P2221
题意：有n个节点排成一条链，相邻节点之间有一条路。
C u v val表示从u到v的路径上的每条边权值都加val。
Q l r表示在l到r中等概率选择两个城市的路径长度的期望值。
思路：首先期望值的分子肯定是可以选择的方案数也就是$C^2_{r - l + 1}$
分子应该是所有可能的路径和。我们可以通过计算每一条边算了多少次得到。
对于第$i$条边，他的左端点有$(i - l + 1)$种可能，右端点有$(r - i + 1)$种可能。因此这$(i - l + 1)*(r - i + 1)$种路径都包含第$i$条边
所以分子可以表示为$sum_{l}^{r}(i-l+1)*(r - i + 1) * a[i]$
把含$i$的和不含的都分离出来。可以变为$(r - l + 1-r*l)sum a[i] + (r + l)sum i *a[i] - sum i^2*a[i]$
分别用线段树维护$sum a[i], sum i * a[i], sum i^2 * a[i]$
小trick是$i$和$i^2$之和也可以保存在线段树节点中，维护起来比较方便。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x3f3f3f3f 14 using namespace std; 15 typedef long long LL; 16 typedef pair<int, int> pr; 17 18 int n, m; 19 const int maxn = 1e5 + 5; 20 struct node{ 21 LL i, a, ia, ii, iia, lazy; 22 }tree[maxn * 4]; 23 24 void build(int rt, int l, int r) 25 { 26 if(l == r){ 27 tree[rt].i = l; 28 tree[rt].ii = 1ll * l * l; 29 return; 30 } 31 int mid = (l + r) / 2; 32 build(rt << 1, l, mid); 33 build(rt << 1 | 1, mid + 1, r); 34 tree[rt].i = tree[rt << 1].i + tree[rt << 1 | 1].i; 35 tree[rt].ii = tree[rt << 1].ii + tree[rt << 1 | 1].ii; 36 } 37 38 void pushdown(int rt, int l, int r) 39 { 40 if(tree[rt].lazy){ 41 tree[rt << 1].lazy += tree[rt].lazy; 42 tree[rt << 1 | 1].lazy += tree[rt].lazy; 43 int mid = (l + r) / 2; 44 tree[rt << 1].a += 1ll * tree[rt].lazy * (mid - l + 1); 45 tree[rt << 1 | 1].a += 1ll * tree[rt].lazy * (r - mid); 46 tree[rt << 1].ia += 1ll * tree[rt].lazy * tree[rt << 1].i; 47 tree[rt << 1|1].ia += 1ll * tree[rt].lazy * tree[rt << 1|1].i; 48 tree[rt << 1].iia += 1ll * tree[rt].lazy * tree[rt << 1].ii; 49 tree[rt << 1|1].iia += 1ll * tree[rt].lazy * tree[rt << 1|1].ii; 50 tree[rt].lazy = 0; 51 } 52 53 } 54 55 void pushup(int rt) 56 { 57 tree[rt].a = tree[rt << 1].a + tree[rt << 1 |1].a; 58 tree[rt].ia = tree[rt << 1].ia + tree[rt << 1 | 1].ia; 59 tree[rt].iia = tree[rt << 1].iia + tree[rt << 1 | 1].iia; 60 } 61 62 void update(int L, int R, int l, int r, int rt, int val) 63 { 64 if(L <= l && R >= r){ 65 tree[rt].a += 1ll * val * (r - l + 1); 66 tree[rt].ia += 1ll * val * tree[rt].i; 67 tree[rt].iia += 1ll * val * tree[rt].ii; 68 tree[rt].lazy += val; 69 return; 70 } 71 pushdown(rt, l, r); 72 int mid = (l + r) / 2; 73 if(L <= mid)update(L, R, l, mid, rt << 1, val); 74 if(R > mid)update(L, R, mid + 1, r, rt << 1 | 1, val); 75 pushup(rt); 76 } 77 78 LL sum1, sum2, sum3; 79 void query(int L, int R, int l, int r, int rt) 80 { 81 if(L <= l && R >= r){ 82 sum1 += tree[rt].a; 83 sum2 += tree[rt].ia; 84 sum3 += tree[rt].iia; 85 return; 86 } 87 pushdown(rt, l, r); 88 int mid = (l + r) / 2; 89 if(L <= mid)query(L, R, l, mid, rt << 1); 90 if(R > mid)query(L, R, mid + 1, r, rt << 1 | 1); 91 92 } 93 94 LL gcd(LL a, LL b) 95 { 96 if(!b)return a; 97 else return gcd(b, a % b); 98 } 99 int main() 100 { 101 scanf("%d%d", &n, &m); 102 build(1, 1, n - 1); 103 for(int i = 0; i < m; i++){ 104 string type; 105 int l, r; 106 cin>>type>>l>>r; r--; 107 if(type[0] == 'C'){ 108 int val; 109 scanf("%d", &val); 110 update(l, r, 1, n - 1, 1, val); 111 } 112 else{ 113 sum1 = sum2 = sum3 = 0; 114 query(l, r, 1, n - 1, 1); 115 LL fac = (1ll * r - l + 1 - 1ll * r * l) * sum1 + (r + l) * sum2 - sum3; 116 LL div = 1ll * (r - l + 2) * (r - l + 1) / 2; 117 // cout<<sum1<<" "<<sum2<<" "<<sum3<<endl; 118 // cout<<fac<<" "<<div<<endl; 119 LL g = gcd(fac, div); 120 fac /= g; 121 div /= g; 122 printf("%lld/%lld ", fac, div); 123 } 124 } 125 return 0; 126 }