Codeforces 138C Mushroom Gnomes

Mushroom Gnomes - 2

感觉没啥东西， 用线段树算算每个被覆盖的概率， 坑点是有很多个在同一个点。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long

using namespace std;

const int N = 4e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

int A[N], h[N], b[N], X[N], n, m, tot;
double pl[N], pr[N], z[N], val[N];

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
double a[N << 2], lazy[N << 2];
void push(int rt) {
    if(fabs(lazy[rt] - 1) > eps) {
        a[rt << 1] *= lazy[rt];
        a[rt << 1 | 1] *= lazy[rt];
        lazy[rt << 1] *= lazy[rt];
        lazy[rt << 1 | 1] *= lazy[rt];
        lazy[rt] = 1;
    }
}
void build(int l, int r, int rt) {
    lazy[rt] = 1;
    if(l == r) {
        a[rt] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(lson); build(rson);
}
void update(int L, int R, double val, int l, int r, int rt) {
    if(L > R) return;
    if(l >= L && r <= R) {
        a[rt] *= val;
        lazy[rt] *= val;
        return;
    }
    int mid = l + r >> 1;
    push(rt);
    if(L <= mid) update(L, R, val, lson);
    if(R > mid)  update(L, R, val, rson);
}
double query(int p, int l, int r, int rt) {
    if(l == r) return a[rt];
    int mid = l + r >> 1;
    push(rt);
    if(p <= mid) return query(p, lson);
    else return query(p, rson);
}

int getId(int x) {
    return lower_bound(X, X + tot, x) - X + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &A[i], &h[i]);
        scanf("%lf%lf", &pl[i], &pr[i]);
        pl[i] /= 100; pr[i] /= 100;
        X[tot++] = A[i];
        X[tot++] = A[i] + h[i];
        X[tot++] = A[i] - h[i];
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d%lf", &b[i], &z[i]);
        X[tot++] = b[i];
    }
    sort(X, X + tot);
    tot = unique(X, X + tot) - X;
    build(1, tot, 1);
    for(int i = 1; i <= m; i++) {
        val[getId(b[i])] += z[i];
    }
    for(int i = 1; i <= tot; i++) {
        update(i, i, val[i], 1, tot, 1);
    }
    for(int i = 1; i <= n; i++) {
        update(getId(A[i]) + 1, getId(A[i] + h[i]), 1 - pr[i], 1, tot, 1);
        update(getId(A[i] - h[i]), getId(A[i]) - 1, 1 - pl[i], 1, tot, 1);
    }
    double ans = 0;
    for(int i = 1; i <= tot; i++) {
        ans += query(i, 1, tot, 1);
    }
    printf("%.12f
", ans);
    return 0;
}

/*
*/