[HAOI2012] 高速公路

题意

Y901 高速公路是一条由 段路以及 个收费站组成的东西向的链,收费站依次编号为 ,从收费站 行驶到 (或从 行驶到 ) 需要收取一定的费用,高速路刚建成时所有的路段都是免费的。

要求动态维护 个操作:

  1. 将收费站 之间的路上的收费加 (可能是负数).
  2. 求对于给定的 ,在第 个收费站里等概率随机取出两个不同的收费站 ,那么从 行驶到 期望花费的费用.

.

分析

这里的期望即平均值,那么

考虑维护分子,把它改写为用边的贡献次数求和

假设第 个收费站后面的路的收费是 ,那么从 的收费站的费用之和

考虑用线段树维护 ,考虑区间加的时候

维护

直接维护呢

维护

.

根据

那么

维护

区间加: .

根据

那么

最后再 GCD 一下就行

代码

#include<cstdio>
#define int long long
using namespace std;
const int N=1e5+5,SGT=1<<18;
int n,m;

struct segment{int l,r;};
segment t[SGT];
int s1[SGT],s2[SGT],s3[SGT],tg[SGT];

int S2(int l,int r){return r*(r+1)/2-l*(l-1)/2;}
int S3(int l,int r){return r*(r+1)*(2*r+1)/6-l*(l-1)*(2*l-1)/6;}

void pushup(int rt){
    s1[rt]=s1[rt<<1]+s1[rt<<1|1];
    s2[rt]=s2[rt<<1]+s2[rt<<1|1];
    s3[rt]=s3[rt<<1]+s3[rt<<1|1];
}
void modify(int rt,int v){
    s1[rt]+=(t[rt].r-t[rt].l+1)*v;
    s2[rt]+=S2(t[rt].l,t[rt].r)*v;
    s3[rt]+=S3(t[rt].l,t[rt].r)*v;
    tg[rt]+=v;
}
void pushdown(int rt){
    modify(rt<<1,tg[rt]);
    modify(rt<<1|1,tg[rt]);
    tg[rt]=0;
}
void build(int l,int r,int rt){
    t[rt].l=l,t[rt].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
}
void add(int L,int R,int v,int rt){
    if(L<=t[rt].l&&t[rt].r<=R){modify(rt,v);return;}
    if(tg[rt])pushdown(rt);
    if(L<=t[rt<<1].r)add(L,R,v,rt<<1);
    if(t[rt<<1].r<R)add(L,R,v,rt<<1|1);
    pushup(rt);
}
int sum1,sum2,sum3;
void query(int L,int R,int rt){
    if(L<=t[rt].l&&t[rt].r<=R){sum1+=s1[rt],sum2+=s2[rt],sum3+=s3[rt];
        return ;
    }
    if(tg[rt])pushdown(rt);
    if(L<=t[rt<<1].r)query(L,R,rt<<1);
    if(t[rt<<1].r<R)query(L,R,rt<<1|1);
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
signed main(){
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    for(int i=1,l,r,v;i<=m;i++){char opt[5];
        scanf("%s%lld%lld",opt,&l,&r),--r;// 点化线段!
        if(opt[0]=='C')scanf("%lld",&v),add(l,r,v,1);
        else {
            sum1=sum2=sum3=0;
            query(l,r,1);
            int a=-sum3+(l+r)*sum2-(r+1)*(l-1)*sum1,b=(r-l+2)*(r-l+1)/2,g=gcd(a,b);
            printf("%lld/%lld\n",a/g,b/g);
        }
    }
    return 0;
}

  转载请注明: Sshwy's Blog [HAOI2012] 高速公路

 上一篇
生成树算法 生成树算法
补一篇生成树(Spanning Tree)的文章 生成树一个比较鬼扯的定义:对于一个图 ,它的生成树是一个连通子图 ,其中 。 最小生成树对于一个加权图 G,最小生成树(M
2019.01.17
下一篇 
SCOI2008 奖励关 SCOI2008 奖励关
题意在奖励关里,系统将依次随机抛出 k 次宝物,每次你都可以选择吃或者不吃。宝物一共有 n 种,第 k 次抛出各个宝物的概率均为 。 获取第 i 种宝物将得到 分( 可以是负数),但第 i 种
2019.01.17
  目录