By

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2752

Solution

期望费用=总费用/总方案数。
刚开始发现最后一个收费站是没用的，所以后面操作前r-1。
很明显总方案数是(r-l+2)×(r-l+1)/2。
分析单个收费站，发现他对总费用的贡献=经过该点的路径条数
即：v[i]×(i-l+1)×(r-i+1)
然后就用线段树维护
但是直接写你会疯掉的
把原式转化成：
Σ(i=l,r)-i^2×a[i]+i×a[i]×(l+r)-(r+1)×(l-1)×a[i]=-Σ(i=l,r)i^2×a[i]+(l+r)Σ(i=1,r)i×a[i]-(r+1)×(l-1)Σ(i=l,r)a[i]
现在你只要维护a[i],a[i]×i,以及a[i]×i^2就可以了。

Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 600005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct data{
    ll t1,t2,t3;
}val[N];
ll left[N],right[N],lazy[N],t1[N],t2[N];
ll n,m,x,y,z; char ch[10];
void build(ll l,ll r,ll p){
    left[p]=l; right[p]=r;
    if (l==r) return;
    ll mid=l+r>>1;
    build(l,mid,p<<1); build(mid+1,r,p<<1|1);
}
void updata(ll p){
    ll l=p<<1,r=l|1; val[p].t1=val[l].t1+val[r].t1;  
    val[p].t2=val[l].t2+val[r].t2; val[p].t3=val[l].t3+val[r].t3;
}
void add(ll p,ll v){
    ll l=left[p],r=right[p]; lazy[p]+=v;
    val[p].t2+=v*(t2[r]-t2[l-1]);
    val[p].t1+=v*(t1[r]-t1[l-1]); val[p].t3+=v*(r-l+1);
}
void pushdown(ll p){
    if (lazy[p]){
        add(p<<1,lazy[p]); add(p<<1|1,lazy[p]);
        lazy[p]=0;
    }
}
void insert(ll l,ll r,ll v,ll p){
    if (left[p]==l&&right[p]==r){
        add(p,v);
        return;
    }
    ll mid=left[p]+right[p]>>1;
    pushdown(p);
    if (y<=mid) insert(l,r,v,p<<1);
    else if (x>mid) insert(l,r,v,p<<1|1);
    else insert(l,mid,v,p<<1),insert(mid+1,r,v,p<<1|1);
    updata(p);
}
data query(ll l,ll r,ll p){
    if (left[p]==l&&right[p]==r) return val[p];
    ll mid=left[p]+right[p]>>1;
    pushdown(p);
    if (r<=mid) return query(l,r,p<<1);
    else if (l>mid) return query(l,r,p<<1|1);
    else {
        data t1=query(l,mid,p<<1),t2=query(mid+1,r,p<<1|1);
        t1.t1+=t2.t1; t1.t2+=t2.t2; t1.t3+=t2.t3;
        return t1;
    }
}
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
int main(){
    n=read(); m=read();
    build(1,n,1);
    for (ll i=1;i<=n;i++){
        t1[i]=t1[i-1]+i*i;
        t2[i]=t2[i-1]+i;
    }
    while (m--){
        scanf("%s",ch);
        if (ch[0]=='Q'){
            x=read(); y=read()-1;
            data ans=query(x,y,1);
            ll fz=-ans.t1+ans.t2*(x+y)-ans.t3*(y+1)*(x-1),fm=t2[y-x+1];
            ll t=gcd(fz,fm); printf("%lld/%lld\n",fz/t,fm/t);
        }else{
            x=read(); y=read()-1; z=read();
            insert(x,y,z,1);
        }
    }
}
文章目录
  1. 1. Solution
  2. 2. Code