BZOJ2752：[HAOI2012]高速公路—

BZOJ2752：[HAOI2012]高速公路——题解

阅读量：6239 次

发布时间：2019-06-22

本文共 2313 字，大约阅读时间需要 7 分钟。

Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。
Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b，那么从a行驶到b将期望花费多少费用呢?

洛谷给它定的标签是“概率期望”，实际上难在维护线段树。

首先我们把路费变成点费，那么n--，所有询问r--。

那么期望=（所有路段的钱的和）/（路段个数），路段个数很好求，专注维护前面的。

对于一个数v[i]，它所提供的价值为：

(1+r-l-lr)*v[i]+(l+r)*i*v[i]-i*i*v[i]。

所以维护v[i],i*v[i],i*i*v[i]即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=400010;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}inline char getc(){ char ch=getchar(); while(ch<'A'||ch>'Z')ch=getchar(); return ch;}inline ll sig(ll l,ll r){ return (l+r)*(r-l+1)>>1;}inline ll ssig(ll l,ll r){ ll a=(l-1)*l*(2*l-1)/6; ll b=r*(r+1)*(2*r+1)/6; return b-a;}ll tr[N][3],lazy[N];void push(int a,int l,int r,int mid){ if(!lazy[a])return; tr[a<<1][0]+=(mid-l+1)*lazy[a]; tr[a<<1|1][0]+=(r-mid)*lazy[a]; tr[a<<1][1]+=sig(l,mid)*lazy[a]; tr[a<<1|1][1]+=sig(mid+1,r)*lazy[a]; tr[a<<1][2]+=ssig(l,mid)*lazy[a]; tr[a<<1|1][2]+=ssig(mid+1,r)*lazy[a]; lazy[a<<1]+=lazy[a]; lazy[a<<1|1]+=lazy[a]; lazy[a]=0;}void modify(int a,ll l,ll r,ll l1,ll r1,ll v){ if(r
            
             
              >1; push(a,l,r,mid); modify(a<<1,l,mid,l1,r1,v);modify(a<<1|1,mid+1,r,l1,r1,v); tr[a][0]=tr[a<<1][0]+tr[a<<1|1][0]; tr[a][1]=tr[a<<1][1]+tr[a<<1|1][1]; tr[a][2]=tr[a<<1][2]+tr[a<<1|1][2];}ll query(int a,ll l,ll r,ll l1,ll r1){ if(r
              
               
                >1; push(a,l,r,mid); return query(a<<1,l,mid,l1,r1)+query(a<<1|1,mid+1,r,l1,r1);}ll gcd(ll a,ll b){ return (!b)?a:gcd(b,a%b);}int main(){ int n=read()-1,m=read(); for(int i=1;i<=m;i++){ char ch=getc(); int l=read(),r=read()-1; if(ch=='C')modify(1,1,n,l,r,read()); else{ ll a=query(1,1,n,l,r),b=sig(1,r-l+1); ll g=gcd(a,b); printf("%lld/%lld\n",a/g,b/g); } } return 0;}