和威威猫系列故事差不多，都是根据条件推出公式
/* 操作c a b d：a到b道路上的所有边权值加d 操作e a b:问a到b中包含的道路的平均权值 区间平均值=所有可能路径权值/所有路径数， 而路径数=len*(len+1)/2,那么只要求区间中所有路径的权值即可 对于属于路径[L,R]的路径[k,k+1](设为x路径)，那么可推出有(K-L+1)(R-K)条路径经过x路径，则路径x对于[L,R]的贡献就是w[k]*(K-L+1)(R-K) 化简得seg[k]*(-k*k+(R+L-1)*k+R*(1-L)),那么只要维护一元二次式中k的三个系数即可 那么[L,R]中所有路径权值的和就是sum{seg[k] * (-k*k + (R-L+1)*k + R*(1-L)} =-sum{seg[k]*k*k} + (R-L+1)sum{seg[k]*k} + R*(1-L)sum{seg[k]} 一颗线段树add维护区间累加的值，三颗线段sum1,sum2,sum3维护三个独立的sum,一颗二维mul线段树维护区间k*k，k，1的值(固定的) 另外将道路离散化成点[L,R]中的每个k可以对应[L,R-1] */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 100005 ll sum[maxn<<2],sumk[maxn<<2],sumkk[maxn<<2]; ll add[maxn<<2],multi[maxn<<2][3]; int N,M; ll S,SK,SKK;//分别是三个系数的和 inline void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; sumk[rt]=sumk[rt<<1]+sumk[rt<<1|1]; sumkk[rt]=sumkk[rt<<1]+sumkk[rt<<1|1]; } //区间每次加上Add都要进行更新，Add对每个sum的贡献量就是Add乘以multi inline void maintain(int rt,ll Add){ sum[rt]+=multi[rt][0]*Add; sumk[rt]+=multi[rt][1]*Add; sumkk[rt]+=multi[rt][2]*Add; } inline void pushdown(int rt){ if(add[rt]){ add[rt<<1]+=add[rt]; add[rt<<1|1]+=add[rt]; maintain(rt<<1,add[rt]); maintain(rt<<1|1,add[rt]); add[rt]=0; } } void build(int l,int r,int rt){ if(l==r){ sum[rt]=sumk[rt]=sumkk[rt]=0; add[rt]=0; multi[rt][0]=1; multi[rt][1]=(ll)r; multi[rt][2]=(ll)r*r; return; } int m=l+r>>1; build(lson); build(rson); pushup(rt); for(int i=0;i<3;i++) multi[rt][i]=multi[rt<<1][i]+multi[rt<<1|1][i]; } void update(int L,int R,ll C,int l,int r,int rt){ if(L<=l && R>=r){ add[rt]+=C; maintain(rt,C); return; } pushdown(rt); int m=l+r>>1; if(L<=m) update(L,R,C,lson); if(R>m) update(L,R,C,rson); pushup(rt); } //查询区间[L,R],求出区间[L,R]的三个sum分别是多少 void query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ S+=sum[rt]; SK+=sumk[rt]; SKK+=sumkk[rt]; return; } pushdown(rt); int m=l+r>>1; if(L<=m) query(L,R,lson); if(R>m) query(L,R,rson); } int main(){ while(scanf("%d%d",&N,&M)==2){ build(1,N,1); char s[20]; for(int i=1;i<=M;i++){ scanf("%s",s); if(s[0]=='c'){ int a,b,c; scanf("%d%d%d",&a,&b,&c); update(a,b-1,(ll)c,1,N,1); } else { int a,b; scanf("%d%d",&a,&b); S=(ll)0; SK=(ll)0; SKK=(ll)0; query(a,b-1,1,N,1); double ans=-SKK+((ll)a+b-1)*SK+(ll)b*(1-a)*S; ll tot=(ll)(b-a)*(b-a+1)/2; printf("%.10f ",ans/tot); } } } return 0; }