[HAOI2012]高速公路

题目描述

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将期望花费多少费用呢?

输入输出格式

输入格式：

第一行2个正整数N,M，表示有N个收费站，M次调整或询问

接下来M行，每行将出现以下两种形式中的一种

C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v

Q l r 表示对于给定的l,r，要求回答小A的问题

所有C与Q操作中保证1<=l<r<=N

输出格式：

对于每次询问操作回答一行，输出一个既约分数

若答案为整数a，输出a/1

输入输出样例

输入样例#1：

输出样例#1：

1/1
8/3
17/6

说明

所有C操作中的v的绝对值不超过10000

在任何时刻任意道路的费用均为不超过10000的非负整数

所有测试点的详细情况如下表所示



数学期望+线段树+GCD(就约分用了)
首先我们考虑在l到r之间的期望(第i到i+1为第i段，所以线段树长度为n-1)
Σp val[p]*(r-i)*(i-l+1)/(r-l+1)*(r-l)
我们来分析一下：
分母部分为r-l+1个路段中选两个端点的方案种数
分子部分考虑每一个位置p对期望的贡献可以得到
接着要动态修改val值并查询答案
把上式拆开：
Σval[p]*(r-l*r)+val[p]*p*(l+r-1)-val[p]*p*p
用一种支持区间修改查询的数据结构:线段树。来维护3种信息：区间signma(val[p]),signma(val[p]*p),signma(val[p]*p*p)
signma(val[p])的维护：直接在和上+(r-l+1)*add
signma(val[p]*p)的维护：利用等差数列公式，+(r-l+1)*(l+r)/2*add
signma(val[p]*p*p)的维护:利用平方和公式：1²+2²+.....+n²=(2*n+1)*(n+1)*n/6
注意long long小心整形溢出

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 typedef long long lol;
  7 struct Node
  8 {
  9     lol s[5];
 10     lol lazy;
 11     lol l,r;
 12 }c[400001];
 13 lol n,m;
 14 lol ans[5];
 15 //2signma(vp(L-LR)+vp*p(L+R-1)-vp*p*p)/(R-L+1)(R-L) 
 16 char get_op()
 17 {
 18     char ch=getchar();
 19     while (ch!='C'&&ch!='Q') ch=getchar();
 20     return ch;
 21 }
 22 lol gcd(lol x,lol y)
 23 {
 24     if (!y) return x;
 25     return gcd(y,x%y);
 26 } 
 27 lol get(lol r,lol l)
 28 {
 29     return ((2*r+1)*(r+1)*r/6-(2*l-1)*(l-1)*l/6);
 30 }
 31 void change(int rt,lol v)
 32 {
 33     c[rt].s[1]+=v*(c[rt].r-c[rt].l+1);
 34     c[rt].s[2]+=(c[rt].l+c[rt].r)*(c[rt].r-c[rt].l+1)/2*v;
 35     c[rt].s[3]+=v*(get(c[rt].r,c[rt].l));
 36     c[rt].lazy+=v;    
 37 }
 38 void pushup(int rt)
 39 {
 40     int i;
 41     for (i=1;i<=3;i++)
 42     {
 43         c[rt].s[i]=c[rt*2].s[i]+c[rt*2+1].s[i];
 44     }
 45 }
 46 void pushdown(int rt)
 47 {
 48     if (c[rt].lazy)
 49     {
 50         change(rt*2,c[rt].lazy);
 51         change(rt*2+1,c[rt].lazy);
 52         c[rt].lazy=0;
 53     }
 54 }
 55 void update(int rt,lol l,lol r,lol L,lol R,lol d)
 56 {
 57     if (l>=L&&r<=R)
 58     {
 59         change(rt,d);
 60         return;
 61     }
 62     lol mid=(l+r)/2;
 63     pushdown(rt);
 64     if (L<=mid) update(rt*2,l,mid,L,R,d);
 65     if (R>mid) update(rt*2+1,mid+1,r,L,R,d);
 66     pushup(rt);
 67 }
 68 lol query(int rt,lol l,lol r,lol L,lol R,int k)
 69 {
 70     if (l>=L&&r<=R)
 71     {
 72         return c[rt].s[k]; 
 73     }
 74     lol mid=(l+r)/2,ss=0;
 75     pushdown(rt);
 76     if (L<=mid) ss+=query(rt*2,l,mid,L,R,k);
 77     if (R>mid) ss+=query(rt*2+1,mid+1,r,L,R,k);
 78  pushup(rt);
 79  return ss;
 80 }
 81 void build(int rt,lol l,lol r)
 82 {
 83    c[rt].l=l;c[rt].r=r;
 84     if (l==r) return;
 85      lol mid=(l+r)/2;
 86      build(rt*2,l,mid);
 87       build(rt*2+1,mid+1,r);
 88 }
 89 int main()
 90 {lol i,l,r,j;
 91 lol p,d;
 92  char opt;
 93     cin>>n>>m;
 94     build(1,1,n-1);
 95      for (i=1;i<=m;i++)
 96      {
 97          opt=get_op();
 98          if (opt=='C') 
 99          {
100              scanf("%lld%lld%lld",&l,&r,&d);
101              update(1,1,n-1,l,r-1,d);
102         }
103         else 
104         {
105             scanf("%lld%lld",&l,&r);
106             p=(r-l+1)*(r-l)/2;
107             for (j=1;j<=3;j++)
108              ans[j]=query(1,1,n-1,l,r-1,j);
109              //cout<<ans[1]<<' '<<ans[2]<<' '<<ans[3]<<endl;
110              ans[0]=(r-l*r)*ans[1]+(l+r-1)*ans[2]-ans[3];
111              //cout<<ans[0]<<' '<<p<<endl;
112              lol g=gcd(ans[0],p);
113              printf("%lld/%lld
",ans[0]/g,p/g);
114         }
115      }
116 }