高速公路

P2221 高速公路

简介题目

有一条链，$n$ 个点从左到右编号为：$1\sim n$，其中每相邻的两个点有一条路，共有 $n-1$ 个路。

两种操作：

• C：$l,r,v$ 代表从编号为 $l$ 的点到 $r$ 的点之间的边的权值加上 $v$。

• Q：$l,r$ 代表从 $l$ 到 $r$ 随机选出两个点 $a,b$，求 $a$ 到 $b$ 的期望。

代码思路

第一个操作，用线段树维护懒标记。

不难发现我们只要维护路即可，标记为 $1\sim n-1$。

每回的左右端点 $l,r$ 直接转换成边的编号 $l,r-1$ 即可。

对于第二个操作，$a$ 到 $b$ 的期望为：

$$\frac{\sum_{i=l}^{r}{\sum_{j=l}^{r}{len(i,j)}}}{C_{r-l+1}^2}$$

上面的部分代表所有取点的可能的两点之间的长度和，下面的部分是所有去点的可能情况数。

下面的很好求：

$$(r-l+1)\times(r-l)$$

主要是上面的处理：

$$\sum_{i=l}^{r}{\sum_{j=l}^{r}{len(i,j)}}=\sum_{i=l}^r{val[i]\times (r-i+1)(i-l+1)}$$

右边的统计方式是每个边出现的次数，$val[i]$ 代表每条路的权值。

那么将右边展开：

$$\sum_{i=l}^r{val[i]\times (r-i+1)(i-l+1)}$$ $$=\sum_{i=l}^r{val[i]\times (ri-rl+r-i^2+il-i+i-l+1)}$$ $$=(r-l+1-rl)\times \sum_{i=l}^r{val[i]}+(r+l)\times i\sum_{i=l}^r{val[i]}-i^2\sum_{i=l}^r{val[i]}$$

定义：

$$s_1=\sum_{i=l}^{r}{val[i]}$$ $$s_2=i\sum_{i=l}^{r}{val[i]}$$ $$s_3=i^2\sum_{i=l}^{r}{val[i]}$$

那么原式就可以表达成：

$$(r-l+1-rl)\times s_1+(r+l)\times s_2-s_3$$

并且 $s_1,s_2,s_3$ 都符合：$f(l,r)=f(l,k)+f(k+1,r)$ 的形式。

所以就可以通过线段树来维护区间和的形式，记录上面的部分。

最后直接按照访问查询分子，计算分母，约分输出即可（细节见代码）。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<string>
#include<cmath>
#include<map>
#include<ctime>
#include<random>
#include<unordered_map>
#include<queue>
using namespace std;
long long r_r(){//快读 
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=2e5+10;
long long g_d(long long a,long long b){//公因数 
  if(!b)return a;
  return g_d(b,a%b);
}
int l_l(int k){//左子树 
  return k<<1;
}
int r_r(int k){//右子树 
  return k<<1|1;
}
struct po{
    long long s_m[6];
    /*
  s_m[1] 第一部分 
  s_m[2] 第二部分 
  s_m[3] 第三部分 
  s_m[4] i 的平方和 
  s_m[5] i 的和 
  */ 
    long long l_n;
    long long l,r;
}t_r[o_o<<2];
long long s_1,s_2,s_3;
void u_p(long long k){//一二三部分更新 
    t_r[k].s_m[1]=t_r[l_l(k)].s_m[1]+t_r[r_r(k)].s_m[1];
    t_r[k].s_m[2]=t_r[l_l(k)].s_m[2]+t_r[r_r(k)].s_m[2];
    t_r[k].s_m[3]=t_r[l_l(k)].s_m[3]+t_r[r_r(k)].s_m[3];
    return;
}
void b_t(long long l,long long r,long long k){
  //记录左右子树编号 
    t_r[k].l=l;
  t_r[k].r=r;
    if(l==r){
      //第三部分的“基数” 
        t_r[k].s_m[4]=l*l;
        
        //第二部分的“基数” 
        t_r[k].s_m[5]=l;
        return;
    }
    long long m_i=(l+r)>>1;
    b_t(l,m_i,l_l(k));//左子树 
    b_t(m_i+1,r,r_r(k));//右子树 
    
    //更新区间信息 
    t_r[k].s_m[4]=t_r[l_l(k)].s_m[4]+t_r[r_r(k)].s_m[4];
    t_r[k].s_m[5]=t_r[l_l(k)].s_m[5]+t_r[r_r(k)].s_m[5];
    return;
}
void w_k(long long k,long long v){
    t_r[k].s_m[1]+=(t_r[k].r-t_r[k].l+1)*v;//第一部分更新 
    t_r[k].s_m[2]+=v*t_r[k].s_m[5];//第二部分更新 
    t_r[k].s_m[3]+=v*t_r[k].s_m[4];//第三部分更新 
    t_r[k].l_n+=v;//懒标记更新 
}
void p_d(long long k){
    w_k(l_l(k),t_r[k].l_n);//更新左子树 
    w_k(r_r(k),t_r[k].l_n);//更新右子树 
    t_r[k].l_n=0;//清空标记 
    return;
}
void a_d(long long l,long long r,long long k,long long v){
    if(t_r[k].l>=l&&t_r[k].r<=r){//在范围内 
        w_k(k,v);//增值 
        return;
    }
    if(t_r[k].l_n)p_d(k);//释放懒标记 
    long long m_i=(t_r[k].l+t_r[k].r)>>1;
    if(m_i>=l)a_d(l,r,l_l(k),v);//左子树 
    if(m_i<r)a_d(l,r,r_r(k),v);//右子树 
    u_p(k);//更新节点信息 
    return;
}
void q_i(long long l,long long r,long long k){
    if(t_r[k].l>=l&&t_r[k].r<=r){//在范围内 
        s_1+=t_r[k].s_m[1];//统计第一部分 
        s_2+=t_r[k].s_m[2];//统计第二部分 
        s_3+=t_r[k].s_m[3];//统计第三部分 
        return;
    }
    if(t_r[k].l_n)p_d(k);//释放懒标记 
    long long m_i=(t_r[k].l+t_r[k].r)>>1;
    if(m_i>=l)q_i(l,r,l_l(k));//左子树 
    if(m_i<r)q_i(l,r,r_r(k));//右子树 
    return;
}
int main(){
    char s[3];
    long long n=r_r(),m=r_r();
    b_t(1,n,1);//建树 
    while(m--){
        scanf("%s",&s);
        long long l=r_r(),r=r_r()-1;
        if(s[0]=='C'){//值增加 
            long long v=r_r();
            a_d(l,r,1,v);//增加值 
        }else{
            s_1=s_2=s_3=0;//初始化三部分 
            q_i(l,r,1);//处理三部分 
            long long a=(r-l+1-r*l)*s_1+(r+l)*s_2-s_3;//分子 
            long long b=(r-l+2)*(r-l+1)/2;//分母 
            long long g=g_d(a,b);//约分 
            printf("%lld/%lld\n",a/g,b/g);//输出 
        }
    }
    return 0;
}