铁轨 清北学堂 线段树

容易想到用线段树维护区间换乘数和来计算期望，对于每次修建，我们将区间\([1,x]\)覆盖为\(0\)，对于剩下的区间\([x+1, n]\)，我们发现换乘次数改变一定是同步的，于是我们区间减去\(val[x+1]-1\)即可（即将\(x+1\)修改为\(1\)）。

注意下放覆盖标记的写法

void push_down(int x, int l, int r){
    if(lazy_cover[x]){
        tre[sl]=tre[sr]=0;
        lazy[sl]=lazy[sr]=0;
        lazy_cover[sl]=lazy_cover[sr]=1;
        lazy_cover[x]=0;
    }
    if(lazy[x]==0) return;
    int mid=(l+r)>>1;
    tre[sl]+=lazy[x]*(mid-l+1);
    lazy[sl]+=lazy[x];
    tre[sr]+=lazy[x]*(r-(mid+1)+1);
    lazy[sr]+=lazy[x];
    lazy[x]=0;
}

注意精度，JXOJ的数据是用double跑出来的，所以要用double）

#include <cstdio>
#define MAXN 100010
#define sl (x<<1)
#define sr (x<<1|1)
using namespace std;
inline int read(){
    char ch=getchar();int s=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s;
}
int tre[MAXN*4];
int lazy[MAXN*4];
bool lazy_cover[MAXN*4];
void push_down(int x, int l, int r){
    if(lazy_cover[x]){
        tre[sl]=tre[sr]=0;
        lazy[sl]=lazy[sr]=0;
        lazy_cover[sl]=lazy_cover[sr]=1;
        lazy_cover[x]=0;
    }
    if(lazy[x]==0) return;
    int mid=(l+r)>>1;
    tre[sl]+=lazy[x]*(mid-l+1);
    lazy[sl]+=lazy[x];
    tre[sr]+=lazy[x]*(r-(mid+1)+1);
    lazy[sr]+=lazy[x];
    lazy[x]=0;
}
void cover(int x, int l, int r, int cl, int cr){
    if(cl<=l&&r<=cr){
        tre[x]=0;
        lazy[x]=0;
        lazy_cover[x]=1;
        //printf("cover[%d,%d]=%d\n", l, r, tre[x]);
        return;
    }
    push_down(x, l, r);
    int mid=(l+r)>>1;
    if(cl<=mid) cover(sl, l, mid, cl, cr);
    if(mid<cr) cover(sr, mid+1, r, cl, cr);
    tre[x]=tre[sl]+tre[sr];
    //printf("cover[%d,%d]=%d\n", l, r, tre[x]);
}
void change(int x, int l, int r, int cl, int cr, int val){
    if(cl<=l&&r<=cr){
        tre[x]+=val*(r-l+1);
        lazy[x]+=val;
        return;
    }
    push_down(x, l, r);
    int mid=(l+r)>>1;
    if(cl<=mid) change(sl, l, mid, cl, cr, val);
    if(mid<cr) change(sr, mid+1, r, cl, cr, val);
    tre[x]=tre[sl]+tre[sr];
}
int query(int x, int l, int r, int ql, int qr){
    if(ql<=l&&r<=qr){
        //printf("query[%d,%d]=%d\n", l, r, tre[x]);
        return tre[x];
    }
    push_down(x, l, r);
    int mid=(l+r)>>1;
    int res=0;
    if(ql<=mid) res+=query(sl, l, mid, ql, qr);
    if(mid<qr) res+=query(sr, mid+1, r, ql, qr);
    //printf("query[%d,%d]=%d\n", l, r, res);
    return res;
}
inline void myswap(int &a, int &b){
    int t=a;
    a=b;
    b=t;
}
int n,m;
int s[MAXN],top;
int main(){
    scanf("%d %d", &n, &m);
    while(m--){
        int opt,x,y;
        scanf("%d", &opt);
        if(opt==0){
            scanf("%d", &x);
            cover(1, 1, n, 1, x);
            change(1, 1, n, x+1, n, 1-query(1, 1, n, x+1, x+1));
        }else{
            scanf("%d %d", &x, &y);
            if(x>y) myswap(x, y);
            printf("%.4lf\n", (double)query(1, 1, n, x, y)*1.0/(y-x+1));
        }
    }
    return 0;
}