题解 CF895E 【Eyes Closed】

考虑第一个操作 设 $[l1,r1]$ 长度为 $x$,$[l2,r2]$ 长度为$y$ 对于区间为 $[l1,r1]$的数，每个数有$\frac{1}{x}$的概率与$[l2,r2]$的数交换 如果交换对这个数期望的贡献为 $\frac{\sum_{i=l2}^{r2}a_i}{xy}$ 如果不交换则第i个数对期望贡献为$\frac{x-1}{x}*a_i$ 所以我们可以维护一颗线段树，资瓷区间加，区间乘，区间求和 ``` #include<bits/stdc++.h> using namespace std; #define db double #define MAXN 100005 #define lc(i) ((i)<<1) #define rc(i) (((i)<<1)|1) #define wt(x) printf("%.3lf\n",x) int n,m; struct aa { int l,r,n; db s,c,j; }c[MAXN<<2]; int a[MAXN]; void maintain(int i) { if(c[i].l == c[i].r) return; c[i].s = c[lc(i)].s + c[rc(i)].s; } void jianshu(int i,int l,int r) { int mid = (l+r)>>1; c[i].l = l; c[i].r = r; c[i].c = 1; c[i].n = r-l+1; if(l == r) { c[i].s = a[l]; return; } jianshu(lc(i),l,mid); jianshu(rc(i),mid+1,r); maintain(i); } void QAQ(int i,db cc,db j) { bool fl = 0; c[i].s = c[i].s*cc+j*c[i].n; c[i].c *= cc; c[i].j *= cc; c[i].j += j; } void pushdown(int i){ if(c[i].l == c[i].r) return; QAQ(lc(i),c[i].c,c[i].j); QAQ(rc(i),c[i].c,c[i].j); c[i].j = 0; c[i].c = 1; } db he(int i,int l,int r) { pushdown(i); if(l <= c[i].l && c[i].r <= r) { return c[i].s; } if(c[i].l > r || c[i].r < l) return 0; db ans = he(lc(i),l,r) + he(rc(i),l,r); return ans; } void cheng(int i,int l,int r,db cc) { pushdown(i); if(l <= c[i].l && c[i].r <= r) { QAQ(i,cc,0); return; } if(c[i].l > r || c[i].r < l) return; cheng(lc(i),l,r,cc); cheng(rc(i),l,r,cc); maintain(i); } void jia(int i,int l,int r,db j) { pushdown(i); if(l <= c[i].l && c[i].r <= r) { QAQ(i,1,j); return; } if(c[i].l > r || c[i].r < l) return; jia(lc(i),l,r,j); jia(rc(i),l,r,j); maintain(i); } void rd() { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i ++) cin >> a[i]; } int main() { rd(); jianshu(1,1,n); for(int i = 1; i <= m; i ++) { int opt,la,lb,ra,rb; scanf("%d",&opt); if(opt == 1) { scanf("%d%d%d%d",&la,&ra,&lb,&rb); db x = ra-la+1,y = rb-lb+1; db ay = he(1,lb,rb)/y,ax = he(1,la,ra)/x;/ cheng(1,la,ra,(x-1)/x); jia(1,la,ra,ay/x); cheng(1,lb,rb,(y-1)/y); jia(1,lb,rb,ax/y); } if(opt == 2) { int l,r; scanf("%d%d",&l,&r); db ans = he(1,l,r); printf("%.6lf\n",ans); } } return 0; } ```