链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2752
题意：正常修改区间，然而取和需要求区间内随意找到两点这两点距离期望……
我们可以发现最后一个点没卵用……于是我们扔掉它，然后后面所有叙述基于$r--$之后进行……
首先，$E=totlength/(C(r-l+2,2))$，这个都能想出来。
然后对于这个式子我们暴力拆开，研究每一条边的情况，就会发现每一条边的期望长度就是$len[i]*((C(r-l+2,2)-C(i-l+1,2)-C(r-i+1,2))$。（考试就想到这）
但是这么写会死人的……长的很……我就这么被狗成了$30$分……
于是我们暴力求一波和……结果会得到$-sigma(i=l,r)len[i]*i^2+(l+r)*sigma(i=l,r)len[i]*i-(r+1)*(l-1)*sigma(i=l,r)len[i]$……然后我们维护三棵线段树就行了……
不要忘了开$long long$……
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=100005; 7 long long a[maxn<<2],ai[maxn<<2],ai2[maxn<<2],ii2[maxn],ii[maxn],se[maxn<<2],sei[maxn<<2],sei2[maxn<<2];int n,m; 8 long long gcd(long long a,long long b){return !b?a:gcd(b,a%b);} 9 #define mid ((l+r)>>1) 10 #define lc root<<1 11 #define rc root<<1|1 12 #define lson lc,l,mid 13 #define rson rc,mid+1,r 14 void Pushdown1(int root,int l,int r) 15 { 16 if(se[root]) 17 { 18 se[lc]+=se[root],se[rc]+=se[root]; 19 a[lc]+=se[root]*(mid-l+1),a[rc]+=se[root]*(r-mid); 20 se[root]=0; 21 } 22 } 23 void Pushup1(int root) 24 { 25 a[root]=a[lc]+a[rc]; 26 } 27 void Modify1(int root,int l,int r,int L,int R,int val) 28 { 29 if(L<=l&&r<=R){se[root]+=val;a[root]+=1ll*val*(r-l+1);return;} 30 Pushdown1(root,l,r); 31 if(L<=mid)Modify1(lson,L,R,val);if(R>mid)Modify1(rson,L,R,val); 32 Pushup1(root); 33 } 34 void Pushdown2(int root,int l,int r) 35 { 36 if(sei[root]) 37 { 38 sei[lc]+=sei[root],sei[rc]+=sei[root]; 39 ai[lc]+=1ll*sei[root]*(ii[mid]-ii[l-1]),ai[rc]+=sei[root]*1ll*(ii[r]-ii[mid]); 40 sei[root]=0; 41 } 42 } 43 void Pushup2(int root) 44 { 45 ai[root]=ai[lc]+ai[rc]; 46 } 47 void Modify2(int root,int l,int r,int L,int R,int val) 48 { 49 if(L<=l&&r<=R){sei[root]+=val;ai[root]+=1ll*val*(ii[r]-ii[l-1]);return;} 50 Pushdown2(root,l,r); 51 if(L<=mid)Modify2(lson,L,R,val);if(R>mid)Modify2(rson,L,R,val); 52 Pushup2(root); 53 } 54 void Pushdown3(int root,int l,int r) 55 { 56 if(sei2[root]) 57 { 58 sei2[lc]+=sei2[root],sei2[rc]+=sei2[root]; 59 ai2[lc]+=sei2[root]*1ll*(ii2[mid]-ii2[l-1]),ai2[rc]+=1ll*sei2[root]*(ii2[r]-ii2[mid]); 60 sei2[root]=0; 61 } 62 } 63 void Pushup3(int root) 64 { 65 ai2[root]=ai2[lc]+ai2[rc]; 66 } 67 void Modify3(int root,int l,int r,int L,int R,int val) 68 { 69 if(L<=l&&r<=R){sei2[root]+=val;ai2[root]+=1ll*val*(ii2[r]-ii2[l-1]);return;} 70 Pushdown3(root,l,r); 71 if(L<=mid)Modify3(lson,L,R,val);if(R>mid)Modify3(rson,L,R,val); 72 Pushup3(root); 73 } 74 void Modify(int l,int r,int val) 75 { 76 r--; 77 Modify1(1,1,n,l,r,val),Modify2(1,1,n,l,r,val),Modify3(1,1,n,l,r,val); 78 } 79 long long Query1(int root,int l,int r,int L,int R) 80 { 81 if(L<=l&&r<=R)return a[root]; 82 Pushdown1(root,l,r);long long ans=0; 83 if(L<=mid)ans+=Query1(lson,L,R);if(R>mid)ans+=Query1(rson,L,R); 84 return ans; 85 } 86 long long Query2(int root,int l,int r,int L,int R) 87 { 88 if(L<=l&&r<=R)return ai[root]; 89 Pushdown2(root,l,r);long long ans=0; 90 if(L<=mid)ans+=Query2(lson,L,R);if(R>mid)ans+=Query2(rson,L,R); 91 return ans; 92 } 93 long long Query3(int root,int l,int r,int L,int R) 94 { 95 if(L<=l&&r<=R)return ai2[root]; 96 Pushdown3(root,l,r);long long ans=0; 97 if(L<=mid)ans+=Query3(lson,L,R);if(R>mid)ans+=Query3(rson,L,R); 98 return ans; 99 } 100 void Query(int l,int r) 101 { 102 r--; 103 long long tmp1=Query1(1,1,n,l,r),tmp2=Query2(1,1,n,l,r),tmp3=Query3(1,1,n,l,r),fenzi=-1ll*tmp3+1ll*(l+r)*tmp2-1ll*tmp1*(r+1)*(l-1),fenmu=(1ll*(r-l+2)*(r-l+1))>>1; 104 long long g=gcd(fenzi,fenmu);fenzi/=g,fenmu/=g; 105 printf("%lld/%lld ",fenzi,fenmu); 106 } 107 int haha() 108 { 109 scanf("%d%d",&n,&m); 110 for(int i=1;i<=n;i++)ii[i]=ii[i-1]+1ll*i,ii2[i]=ii2[i-1]+1ll*i*i; 111 for(int i=1;i<=m;i++) 112 { 113 char opt[3];int x,y,z;scanf("%s%d%d",opt,&x,&y); 114 if(opt[0]=='C')scanf("%d",&z),Modify(x,y,z); 115 else Query(x,y); 116 } 117 } 118 int sb=haha(); 119 int main(){;}