首页 > > 程序设计 > C/C++ >

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

2018-08-26 17:16:54来源：博客园阅读 ()

题意

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 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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 == 1 && T[k].add == 0) return ;
    pr(k, ls); pr(k, rs); 
    T[k].mul = 1; T[k].add = 0; 
}
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 + 1; T[k].l = ll; T[k].r = rr; T[k].mul = 1;
    if(ll == rr) {
        T[k].sum = a[ll];
        return ;
    }
    int mid = (ll + rr) >> 1;
    Build(ls, ll, mid); Build(rs, mid + 1, 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 >> 1;
    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 >> 1;
    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 = 0;
    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 >> 1;
    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 = 1; i <= N; i++) a[i] = read();
    Build(1, 1, N);
    while(Q--) {
        int opt = read();
        if(opt == 1) {
            int l1 = read(), r1 = read(), l2 = read(), r2 = read();
            double d1 = Query(1, l1, r1);
            double d2 = Query(1, l2, r2), len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
            IntervalMul(1, l1, r1, (len1 - 1) / len1 ); IntervalMul(1, l2, r2, (len2 - 1) / len2);
            IntervalAdd(1, l1, r1, d2 / len1 / len2); IntervalAdd(1, l2, r2, d1 / len1 / len2);
        } else {
            int l = read(), r = read();
            printf("%.10lf\n", Query(1, l, r));
        }
    }
    return 0;
}