CF895 E. Eyes Closed(线段树 期望)

题意

Sol

今天考试的T3，，我本来留了一个小时去写。但是T2一刚就刚了两个小时

最后也没来的及写。。

然后考完 开始写，，25min就A了。。

感觉自己太高估自己的思维，太低估自己的码力了。。。

这题比较简单吧

期望的和等于和的期望

然后线段树维护每个节点的值就可以了

交换的时候分自己不变和变成哪个数讨论一下

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<vector>

#include<set>

#include<queue>

#include<cmath>

#include<iostream>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#define ls k << 1

#define rs k << 1 | 1

#define int long long

#define LL long long

//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)

//char buf[(1 << 22)], *p1 = buf, *p2 = buf;

using namespace std;

const int MAXN = 1e6 + , INF = 1e9 + , mod = 1e9 + ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, Q;

struct Node {

    int l, r, siz;

    double sum, mul, add;

}T[MAXN];

int a[MAXN];

void pr(int k, int son) {

    T[son].sum *= T[k].mul;

    T[son].sum += T[son].siz * (T[k].add);

    T[son].mul *= T[k].mul;

    T[son].add *= T[k].mul;

    T[son].add += T[k].add;

}

void pushdown(int k) {

    if(T[k].mul ==  && T[k].add == ) return ;

    pr(k, ls); pr(k, rs);

    T[k].mul = ; T[k].add = ;

}

void update(int k) {

    T[k].sum = T[ls].sum + T[rs].sum;

}

void Build(int k, int ll, int rr) {

    T[k].siz = rr - ll + ; T[k].l = ll; T[k].r = rr; T[k].mul = ;

    if(ll == rr) {

        T[k].sum = a[ll];

        return ;

    }

    int mid = (ll + rr) >> ;

    Build(ls, ll, mid); Build(rs, mid + , rr);

    update(k);

}

void IntervalMul(int k, int ll, int rr, double val) {

    if(ll <= T[k].l && T[k].r <= rr) {

        T[k].sum *= val; T[k].mul *= val; T[k].add *= val;

        return ;

    }

    pushdown(k);

    int mid = T[k].l + T[k].r >> ;

    if(ll <= mid) IntervalMul(ls, ll, rr, val);

    if(rr >  mid) IntervalMul(rs, ll, rr, val);

    update(k);

}

void IntervalAdd(int k, int ll, int rr, double val) {

    if(ll <= T[k].l && T[k].r <= rr) {

        T[k].sum += T[k].siz * val; T[k].add += val;

        return ;

    }

    pushdown(k);

    int mid = T[k].l + T[k].r >> ;

    if(ll <= mid) IntervalAdd(ls, ll, rr, val);

    if(rr > mid)  IntervalAdd(rs, ll, rr, val);

    update(k);

}

double Query(int k, int ll, int rr) {

    double ans = ;

    if(ll <= T[k].l && T[k].r <= rr) {

        ans += T[k].sum; return ans;

    }

    pushdown(k);

    int mid = T[k].l + T[k].r >> ;

    if(ll <= mid) ans += Query(ls, ll, rr);

    if(rr > mid)  ans += Query(rs, ll, rr);

    return ans;

}

main() {

    N = read(); Q = read();

    for(int i = ; i <= N; i++) a[i] = read();

    Build(, , N);

    while(Q--) {

        int opt = read();

        if(opt == ) {

            int l1 = read(), r1 = read(), l2 = read(), r2 = read();

            double d1 = Query(, l1, r1);

            double d2 = Query(, l2, r2), len1 = r1 - l1 + , len2 = r2 - l2 + ;

            IntervalMul(, l1, r1, (len1 - ) / len1 ); IntervalMul(, l2, r2, (len2 - ) / len2);

            IntervalAdd(, l1, r1, d2 / len1 / len2); IntervalAdd(, l2, r2, d1 / len1 / len2);

        } else {

            int l = read(), r = read();

            printf("%.10lf\n", Query(, l, r));

        }

    }

    return ;

}