This page looks best with JavaScript enabled

「HAOI2012」高速公路-期望+线段树

 ·  ✏️ About  726 words  ·  ☕ 2 mins read · 👀... views

Y901 高速公路是一条由 $N-1$ 段路以及 $N$ 个收费站组成的东西向的链,我们按照由西向东的顺序将收费站依次编号为 $1 \sim N$ ,从收费站 $i$ 行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况,会不定期地对连续路段的收费标准进行调整,根据政策涨价或降价。

求对于给定的 $l,r(l < r)$ ,在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ,那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?

链接

Luogu P2221

题解

位于某个位置的边只会被两个端点分居两边的路径经过,所以我们就可以暴力推式子qwq:

$$
\begin{aligned}{}
E(l,r) &= \frac{1}{(r-l-1)(r-l)}\sum_{i = l}^{r-1}(i-l+1)(r-i)V_i\
&= \frac{1}{(r-l-1)(r-l)}\sum_{i = l}^{r-1}[-i^2 V_i-(l+r-1)i V_i - r(l-1)V_i]
\end{aligned}
$$

所以需要记录的只有三个东西:$\sum V_i , \sum i V_i , \sum i^2 V_i$。

这三个东西都是可以用线段树维护的(就是 O(1) 完成打标记和标记下放)。

具体方法看代码吧。

披着期望外衣的线段树题。

代码

  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>
#define gcd __gcd
#define ll long long
using namespace std;

const int MAXN = 110000;

namespace SegTree{
    //0->sigma(V_i),1->sigma(i*V_i),2->sigma(i^2*V_i)
    struct node{
        ll sum[3];
        node(ll _a = 0,ll _b = 0,ll _c = 0){
            sum[0] = _a,sum[1] = _b,sum[2] = _c;
        }
        node operator + (const node &a)const{
            node newnode;
            newnode.sum[0] = sum[0] + a.sum[0];
            newnode.sum[1] = sum[1] + a.sum[1];
            newnode.sum[2] = sum[2] + a.sum[2];
            return newnode;
        }
    }sumn[MAXN<<2];
    ll tag[MAXN<<2];
    #define lson (nown<<1)
    #define rson (nown<<1|1)
    #define mid ((l+r)>>1)
    inline ll cal(int n){
        return 1LL*n*(n+1)*(2*n+1)/6;
    }
    inline void addtag(int nown,int l,int r,ll v){
        tag[nown] += v;
        static node tmp;
        tmp = node(v*(r-l+1),v*(l+r)*(r-l+1)/2,v*(cal(r)-cal(l-1)));
        sumn[nown] = sumn[nown] + tmp;
    }
    inline void push_down(int nown,int l,int r){
        if(tag[nown]){
            addtag(lson,l,mid,tag[nown]),addtag(rson,mid+1,r,tag[nown]);
            tag[nown] = 0;
        }
    }
    inline void push_up(int nown){
        sumn[nown] = sumn[lson] + sumn[rson];
    }
    inline void update(int nown,int l,int r,int ql,int qr,int v){
        if(ql <= l && r <= qr)
            addtag(nown,l,r,v);
        else{
            push_down(nown,l,r);
            if(ql <= mid) update(lson,l,mid,ql,qr,v);
            if(qr >= mid+1) update(rson,mid+1,r,ql,qr,v);
            push_up(nown);
        }
    }
    inline node query(int nown,int l,int r,int ql,int qr){
        if(ql <= l && r <= qr)
            return sumn[nown];
        else{
            push_down(nown,l,r);
            node ans;
            if(ql <= mid) ans = ans + query(lson,l,mid,ql,qr);
            if(qr >= mid+1) ans = ans + query(rson,mid+1,r,ql,qr);
            return ans;
        }
    }
}

int n,m;

void update(int l,int r,int v){
    SegTree::update(1,1,n,l,r-1,v);
}

void query(int l,int r,ll &x,ll &y){
    SegTree::node tmp = SegTree::query(1,1,n,l,r-1);
    x = -1LL*r*(l-1)*tmp.sum[0] + 1LL * (r+l-1)*(tmp.sum[1]) - tmp.sum[2];
    y = 1LL*(r-l+1)*(r-l)/2;
    ll d = gcd(x,y);
    x/=d,y/=d;
} 

void init(){
    scanf("%d %d",&n,&m);
}

void solve(){
    ll x, y;
    for(int i = 1;i<=m;i++){
        char op[10];int l,r,c;
        scanf("%s %d %d",op,&l,&r);
        if(op[0] == 'C')
            scanf("%d",&c),update(l,r,c);
        else
            query(l,r,x,y),printf("%lld/%lld\n",x,y);
    }
}

int main(){
    init();
    solve();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: