洛谷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$之和也可以保存在线段树节点中，维护起来比较方便。

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, m;

 const int maxn = 1e5 + ;

 struct node{

     LL i, a, ia, ii, iia, lazy;

 }tree[maxn * ];

 void build(int rt, int l, int r)

 {

     if(l == r){

         tree[rt].i = l;

         tree[rt].ii = 1ll * l * l;

         return;

     }

     int mid = (l + r) / ;

     build(rt << , l, mid);

     build(rt <<  | , mid + , r);

     tree[rt].i = tree[rt << ].i + tree[rt <<  | ].i;

     tree[rt].ii = tree[rt << ].ii + tree[rt <<  | ].ii;

 }

 void pushdown(int rt, int l, int r)

 {

     if(tree[rt].lazy){

         tree[rt << ].lazy += tree[rt].lazy;

         tree[rt <<  | ].lazy += tree[rt].lazy;

         int mid = (l + r) / ;

         tree[rt << ].a += 1ll * tree[rt].lazy * (mid - l + );

         tree[rt <<  | ].a += 1ll * tree[rt].lazy * (r - mid);

         tree[rt << ].ia += 1ll * tree[rt].lazy * tree[rt << ].i;

         tree[rt << |].ia += 1ll * tree[rt].lazy * tree[rt << |].i;

         tree[rt << ].iia += 1ll * tree[rt].lazy * tree[rt << ].ii;

         tree[rt << |].iia += 1ll * tree[rt].lazy * tree[rt << |].ii;

         tree[rt].lazy = ;

     }

 }

 void pushup(int rt)

 {

     tree[rt].a = tree[rt << ].a + tree[rt <<  |].a;

     tree[rt].ia = tree[rt << ].ia + tree[rt <<  | ].ia;

     tree[rt].iia = tree[rt << ].iia + tree[rt <<  | ].iia;

 }

 void update(int L, int R, int l, int r, int rt, int val)

 {

     if(L <= l && R >= r){

         tree[rt].a += 1ll * val * (r - l + );

         tree[rt].ia += 1ll * val * tree[rt].i;

         tree[rt].iia += 1ll * val * tree[rt].ii;

         tree[rt].lazy += val;

         return;

     }

     pushdown(rt, l, r);

     int mid = (l + r) / ;

     if(L <= mid)update(L, R, l, mid, rt << , val);

     if(R > mid)update(L, R, mid + , r, rt <<  | , val);

     pushup(rt);

 }

 LL sum1, sum2, sum3;

 void query(int L, int R, int l, int r, int rt)

 {

     if(L <= l && R >= r){

         sum1 += tree[rt].a;

         sum2 += tree[rt].ia;

         sum3 += tree[rt].iia;

         return;

     }

     pushdown(rt, l, r);

     int mid = (l + r) / ;

     if(L <= mid)query(L, R, l, mid, rt << );

     if(R > mid)query(L, R, mid + , r, rt <<  | );

 }

 LL gcd(LL a, LL b)

 {

     if(!b)return a;

     else return gcd(b, a % b);

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     build(, , n - );

     for(int i = ; i < m; i++){

         string type;

         int l, r;

         cin>>type>>l>>r; r--;

         if(type[] == 'C'){

             int val;

             scanf("%d", &val);

             update(l, r, , n - , , val);

         }

         else{

             sum1 = sum2 = sum3 = ;

             query(l, r, , n - , );

             LL fac = (1ll * r - l +  - 1ll * r * l) * sum1 + (r + l) * sum2 - sum3;

             LL div = 1ll * (r - l + ) * (r - l + ) / ;

 //            cout<<sum1<<" "<<sum2<<" "<<sum3<<endl;

 //            cout<<fac<<" "<<div<<endl;

             LL g = gcd(fac, div);

             fac /= g;

             div /= g;

             printf("%lld/%lld\n", fac, div);

         }

     }

     return ;

 }

巴特西

洛谷P2221 高速公路【线段树】

最新文章

热门文章