bzoj4821

线段树

这题真是无聊

把式子拆开，然后可知维护xi,yi,xi^2,xi*yi,重点在于标记下传，当我们进行2号操作时，直接累加进答案和标记即可，进行3号操作时，update时先把自己这层赋值成要改变的值，再清空这层2号标记，每次pushdown把这层的下一层的标记清空，因为下一层被覆盖了，pushdown先执行3号标记，再执行2号标记，因为存在的2号标记肯定在3号标记后打的，否则肯定会被清空，所以2号标记应该在三号标记后。

而下一层的2号标记肯定是在三号标记之前打的，因为标记已经下传。

#include
using namespace std;
typedef double ld;
const int N = 100010;
int n, m;
ld x[N], y[N];
struct node {double sumx, sumy, sumxx, sumxy;node(ld sumx = 0, ld sumy = 0, ld sumxx = 0, ld sumxy = 0) : sumx(sumx), sumy(sumy), sumxx(sumxx), sumxy(sumxy) {}void print(){printf("sumx=%.10f sumy=%.10f sumxx=%.10f sumxy=%.10f\n", sumx, sumy, sumxx, sumxy);}
};
struct seg {node tree[N << 2];ld tagx2[N << 2], tagy2[N << 2], tagx3[N << 2], tagy3[N << 2];bool can1[N << 2], can2[N << 2];ld calc(ld x){return (ld)x * (ld)(x + 1) * (ld)(2 * x + 1) / 6;}void pushdown(int o, int l, int r){int mid = (l + r) >> 1;if(can1[o]){tree[o << 1].sumx = (ld)(mid - l + 1) * tagx3[o] + (ld)(mid + l) * (ld)(mid - l + 1) / 2.0;  tree[o << 1 | 1].sumx = (ld)(r - mid) * tagx3[o] + (ld)(r + mid + 1) * (ld)(r - mid) / 2.0;tree[o << 1].sumy = (ld)(mid - l + 1) * tagy3[o] + (ld)(mid + l) * (ld)(mid - l + 1) / 2.0;  tree[o << 1 | 1].sumy = (ld)(r - mid) * tagy3[o] + (ld)(r + mid + 1) * (ld)(r - mid) / 2.0;tree[o << 1].sumxx = calc(tagx3[o] + mid) - calc(tagx3[o] + l - 1);tree[o << 1 | 1].sumxx = calc(tagx3[o] + r) - calc(tagx3[o] + mid);tree[o << 1].sumxy = (ld)(mid - l + 1) * tagx3[o] * tagy3[o] + (ld)(tagx3[o] + tagy3[o]) * (ld)(mid + l) * (ld)(mid - l + 1) / 2.0 + calc(mid) - calc(l - 1);    tree[o << 1 | 1].sumxy = (ld)(r - mid) * tagx3[o] * tagy3[o] + (ld)(tagx3[o] + tagy3[o]) * (ld)(r + mid + 1) * (ld)(r - mid) / 2.0 + calc(r) - calc(mid);tagx3[o << 1] = tagx3[o << 1 | 1] = tagx3[o];tagy3[o << 1] = tagy3[o << 1 | 1] = tagy3[o];tagx3[o] = tagy3[o] = 0;tagx2[o << 1] = tagx2[o << 1 | 1] = tagy2[o << 1] = tagy2[o << 1 | 1] = 0;can2[o << 1] = can2[o << 1 | 1] = 0;can1[o << 1] = can1[o << 1 | 1] = can1[o];can1[o] = 0;}if(can2[o]){tree[o << 1].sumxx += 2.0 * tree[o << 1].sumx * tagx2[o] + (ld)(mid - l + 1) * tagx2[o] * tagx2[o];tree[o << 1 | 1].sumxx += 2.0 * tree[o << 1 | 1].sumx * tagx2[o] + (ld)(r - mid) * tagx2[o] * tagx2[o];tree[o << 1].sumxy += tree[o << 1].sumx * tagy2[o] + tree[o << 1].sumy * tagx2[o] + (ld)(mid - l + 1) * tagx2[o] * tagy2[o];tree[o << 1 | 1].sumxy += tree[o << 1 | 1].sumx * tagy2[o] + tree[o << 1 | 1].sumy * tagx2[o] + (ld)(r - mid) * tagx2[o] * tagy2[o];tree[o << 1].sumx += tagx2[o] * (ld)(mid - l + 1);tree[o << 1 | 1].sumx += tagx2[o] * (ld)(r - mid); tree[o << 1].sumy += tagy2[o] * (ld)(mid - l + 1);tree[o << 1 | 1].sumy += tagy2[o] * (ld)(r - mid);tagx2[o << 1] += tagx2[o];tagx2[o << 1 | 1] += tagx2[o];tagy2[o << 1] += tagy2[o];tagy2[o << 1 | 1] += tagy2[o];tagx2[o] = 0;tagy2[o] = 0; can2[o << 1] = can2[o << 1 | 1] = can2[o];can2[o] = 0;}        }node merge(node B, node C){node A;A.sumx = B.sumx + C.sumx;A.sumy = B.sumy + C.sumy;A.sumxx = B.sumxx + C.sumxx;A.sumxy = B.sumxy + C.sumxy;return A;}void build(int l, int r, int o){if(l == r){tree[o] = node(x[l], y[l], x[l] * x[l], x[l] * y[l]);            return;}int mid = (l + r) >> 1;build(l, mid, o << 1);build(mid + 1, r, o << 1 | 1);tree[o] = merge(tree[o << 1], tree[o << 1 | 1]);}node query(int l, int r, int o, int a, int b){if(l > b || r < a) return tree[0];if(l >= a && r <= b) return tree[o];int mid = (l + r) >> 1;pushdown(o, l, r);node tx = query(l, mid, o << 1, a, b), ty = query(mid + 1, r, o << 1 | 1, a, b);return merge(tx, ty);}void update2(int l, int r, int o, int a, int b, ld s, ld t){if(l > b || r < a) return;if(l >= a && r <= b){tagx2[o] += s;tagy2[o] += t;tree[o].sumxx += 2.0 * tree[o].sumx * s + (ld)(r - l + 1) * s * s;tree[o].sumxy += t * tree[o].sumx + s * tree[o].sumy + (ld)(r - l + 1) * s * t;         tree[o].sumx += (ld)(r - l + 1) * s;tree[o].sumy += (ld)(r - l + 1) * t;can2[o] = 1;return;}pushdown(o, l, r);int mid = (l + r) >> 1;update2(l, mid, o << 1, a, b, s, t);update2(mid + 1, r, o << 1 | 1, a, b, s, t);tree[o] = merge(tree[o << 1], tree[o << 1 | 1]);}void update3(int l, int r, int o, int a, int b, ld s, ld t){if(l > b || r < a) return;if(l >= a && r <= b){tagx3[o] = s;tagy3[o] = t;tagx2[o] = tagy2[o] = 0;tree[o].sumx = (ld)(r - l + 1) * s + (ld)(l + r) * (ld)(r - l + 1) / 2.0; tree[o].sumy = (ld)(r - l + 1) * t + (ld)(l + r) * (ld)(r - l + 1) / 2.0;tree[o].sumxx = calc(s + r) - calc(s + l - 1);tree[o].sumxy = (ld)(r - l + 1) * s * t + ((ld)(l + r) * (ld)(r - l + 1) / 2.0) * (ld)(s + t) + calc(r) - calc(l - 1);can1[o] = 1;can2[o] = 0;return;}pushdown(o, l, r);int mid = (l + r) >> 1;update3(l, mid, o << 1, a, b, s, t);update3(mid + 1, r, o << 1 | 1, a, b, s, t);tree[o] = merge(tree[o << 1], tree[o << 1 | 1]);        }
} t;
int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i)scanf("%lf", &x[i]);for(int i = 1; i <= n; ++i)scanf("%lf", &y[i]);t.build(1, n, 1);for(int i = 1; i <= m; ++i){int opt, l, r;ld S, T;scanf("%d", &opt);if(opt == 1){scanf("%d%d", &l, &r);node o = t.query(1, n, 1, l, r);ld ox = o.sumx / (ld)(r - l + 1), oy =  o.sumy / (ld)(r - l + 1);ld up = ((ld)(r - l + 1) * o.sumxy - o.sumx * o.sumy), down = ((ld)(r - l + 1) * o.sumxx - o.sumx * o.sumx), ans = up / down; printf("%.10f\n", ans);}if(opt == 2){scanf("%d%d%lf%lf", &l, &r, &S, &T);t.update2(1, n, 1, l, r, S, T);}if(opt == 3){scanf("%d%d%lf%lf", &l, &r, &S, &T);t.update3(1, n, 1, l, r, S, T);}}return 0;
}

转载于:https://www.cnblogs.com/19992147orz/p/7223553.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！