题目链接
题解
线段树维护期望和
写出修改两区间的相互影响
就是一个区间修改
emmm考试的代码过不去，这么松的spj都过不去Orz，每次和答案差0.001*ans左右…
可能是我每次直接对区间暴力统计右区间的影响，然后直接打个修改区间tag….
求解
代码
std:
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <complex>#define inf 0x3f3f3f3f
#define eps 1e-10#define lc k << 1
#define rc k << 1 | 1using namespace std;typedef long long ll;
typedef pair<ll, int> P;
ll p;
double tmp[200005];struct node{
double dat, tag1, tag2;
int l, r;
};
struct seg{
node d[800005]; void pushup(int k){
d[k].dat = d[lc].dat + d[rc].dat;
} void build(int k, int l, int r){
d[k].l = l; d[k].r = r; d[k].tag1 = 0; d[k].tag2 = 1;
if(l == r){
d[k].dat = tmp[l];
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(k);
} void add(int k, double x){
double len = d[k].r - d[k].l + 1;
d[k].dat = (d[k].dat + x * len);
d[k].tag1 = (d[k].tag1 + x);
} void mul(int k, double x){
d[k].dat = d[k].dat * x;
d[k].tag1 = d[k].tag1 * x;
d[k].tag2 = d[k].tag2 * x;
} void pushdown(int k){
if(fabs(d[k].tag2 - 1) > eps){
mul(lc, d[k].tag2);
mul(rc, d[k].tag2);
d[k].tag2 = 1;
}
if(fabs(d[k].tag1) > eps){
add(lc, d[k].tag1);
add(rc, d[k].tag1);
d[k].tag1 = 0;
}
} void add(int k, int l, int r, double x){
if(l <= d[k].l && d[k].r <= r){
add(k, x); return;
}
pushdown(k);
int mid = (d[k].l + d[k].r) >> 1;
if(l <= mid) add(lc, l, r, x);
if(r > mid) add(rc, l, r, x);
pushup(k);
} void mul(int k, int l, int r, double x){
if(l <= d[k].l && d[k].r <= r){
mul(k, x); return;
}
pushdown(k);
int mid = (d[k].l + d[k].r) >> 1;
if(l <= mid) mul(lc, l, r, x);
if(r > mid) mul(rc, l, r, x);
pushup(k);
} double query(int k, int l, int r){
if(l <= d[k].l && d[k].r <= r){
return d[k].dat;
}
pushdown(k); double sum = 0;
int mid = (d[k].l + d[k].r) >> 1;
if(l <= mid) sum = (sum + query(lc, l, r));
if(r > mid) sum = (sum + query(rc, l, r));
return sum;
}}Seg;int n, m;int main(){//freopen("random.in", "r", stdin);freopen("random.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%lf", &tmp[i]);
Seg.build(1, 1, n);
while(m--){
int opt, l1, r1, l2, r2; ll x;
scanf("%d", &opt);
if(opt == 1){
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
double d1 = Seg.query(1, l1, r1);
double d2 = Seg.query(1, l2, r2);
Seg.mul(1, l1, r1, double(r1 - l1) / double(r1 - l1 + 1));
Seg.mul(1, l2, r2, double(r2 - l2) / double(r2 - l2 + 1));
Seg.add(1, l1, r1, d2 / double(r1 - l1 + 1) / double(r2 - l2 + 1));
Seg.add(1, l2, r2, d1 / double(r2 - l2 + 1) / double(r1 - l1 + 1));
}
if(opt == 2){
scanf("%d%d", &l1, &r1);
printf("%.8lf\n", Seg.query(1, l1, r1));
}
}
return 0;
}
mycode
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
inline int read() {
int x = 0 ,f = 1;
char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
} int n,m;
#define double long double
const int maxn = 2000007;
int a[maxn];
double t[maxn << 1] ;
double tag[maxn << 1];
int tagl[maxn << 1],tagr[maxn << 1]; void update(int x) {
t[x] = t[x << 1] + t[x << 1 | 1];
} double merge(double c1,double c2,int l,int r,int t1,int t2) {
double k1 = 1.0 * r - l + 1, k2 = 1.0 * t2;
return c1 * (k1 - 1) / k1 + c2 /t2 ;
} void pushdown(int x,int l,int r) {
int mid = l + r >> 1; t[x << 1] = merge(t[x << 1] , tag[x] , l , mid , tagl[x] , tagr[x]); t[x << 1 | 1] = merge(t[x << 1 | 1] , tag[x] , mid + 1,r , tagl[x] , tagr[x]); tag[x << 1] = tag[x << 1 | 1] = tag[x];
tagl[x << 1] = tagl[x << 1 | 1] = tagl[x];
tagr[x << 1] = tagr[x << 1 | 1] = tagr[x];
tagl[x] = tagr[x] = 0; tag[x] = 0.0;
} void build(int x,int l,int r) {
if(l == r) { t[x] = a[l]; return; } int mid = l + r >> 1; build(x << 1,l,mid); build(x << 1 | 1,mid + 1,r);
update(x);
}
double Query(int x,int l,int r,int L,int R) {
if(tag[x] != 0.0 && tagl[x] && tagr[x]) pushdown(x,l,r);
if(l >= L && r <= R) return t[x]; double ret = 0;
int mid = l + r >> 1;
if(L <= mid) ret += Query(x << 1,l,mid,L,R);
if(R > mid ) ret += Query(x << 1 | 1,mid + 1,r,L,R);
return ret;
//update(x);
}
void modify(int x,int l,int r,int L,int R,double CC,int t1,int t2) { if(tag[x] != 0.0&& tagr[x] && tagl[x]) pushdown(x,l,r);
if(l >= L && r <= R) {
t[x] = merge(t[x],CC,l,r,t1,t2);
if(l != r) {
tag[x] = CC;
tagl[x] = t1;
tagr[x] = t2;
}
return ;
}
int mid = l + r >> 1;
if(L <= mid) modify(x << 1,l,mid,L,R,CC, t1,t2);
if(R > mid ) modify(x << 1 | 1,mid + 1,r,L,R, CC,t1,t2);
update(x);
}
int main() {
//freopen("random.in","r",stdin); freopen("random.out","w",stdout);
n = read(),m = read();
for(int i = 1;i <= n;++ i) a[i] = read(); build(1,1,n);
for(int type,l,r,l1,r1,i = 1;i <= m;++ i) {
type = read();
if(type == 1) {
l = read(),r = read();
l1 = read();r1 = read();
double q1 = Query(1,1,n,l,r);
double q2 = Query(1,1,n,l1,r1);
modify(1,1,n,l,r,q2 , r - l + 1 , r1 - l1 + 1);
modify(1,1,n,l1,r1,q1 , r1 - l1 + 1 , r - l + 1);
}
else {
l = read(),r = read();
//printf("%llf\n",Query(1,1,n,l,r));
std::cout << Query(1,1,n,l,r) << std::endl;
}
}
return 0;
}
/*
4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2
*/
