首页 > 代码库 > bzoj 2752

bzoj 2752

2024-08-06 12:51:03   218人阅读

传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=2752

这道题其实想到线段树并不难，而且如果正确的推出了公式写起来也就是有点恶心而已＝ ＝实现不太容易出错。但是公式推起来确实比较的酸爽，加上我的公式又比较的迷，然后跑的飞慢＝ ＝

这道题对于一个区间的期望，是整个区间的路径和除上区间的路径数目。数目可以O(1), 然后就在线段树中维护这个路径和。考虑区间合并（线段树都是这样＝ ＝），那么对于两个区间l, r， 那么路径和首先等于l的路径和加上r路径和，然后对于l中的一段路径，那么它的更新就是这条路径左边点的个数(包括左端点）* r中点的个数 * v，而出了r中的点的个数以外，其余部分作为一个元素up进行维护。 同样右边同理一个down 维护。 同时在更新这两个值的时候还需要维护一个区间和sum＝ ＝

然后lazy 标记的下放：sum 直接搞，然后up 和down 都是 * len［区间长度］* (len - 1) * v; 

ans += lazy * (1 * len * + 2 * (len - 1)  + 3 * (len - 3) ... + (len - 1) * 2 + len * 1) = len * (len + 1) * (len + 2) / 6 * lazy

然后就搞搞＝ ＝ 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long qword;const qword maxn = 101000;struct node {    qword up, down, ans, lazy, sum;    node *l, *r;}e[maxn * 3]; qword ne = 0;node* root;node* build(qword l, qword r) {    node* now = e + ne ++;    if(l ^ r) {        qword mid = (l + r) >> 1;        now-> l = build(l, mid);        now-> r = build(mid + 1, r);    }    return now;}void update(node* x, qword l, qword r, qword mid) {    if(l ^ r) {        x-> ans = x-> l-> ans + x-> r-> ans + x-> l-> up * (r - mid) + x-> r-> down * (mid - l + 1);        x-> sum = x-> l-> sum + x-> r-> sum;        x-> up = x-> l-> up + x-> r-> up + x-> r-> sum * (mid - l + 1);        x-> down = x-> l-> down + x-> r-> down + x-> l-> sum * (r - mid);    }}void pushdown(node* x, qword l, qword r) {    if(x-> l) {        qword mid = (l + r) >> 1, v = x-> lazy, ln = mid - l + 1, rn = r - mid;        x-> l-> ans += ln * (ln + 1) / 2 * (ln + 2) / 3 * v;        x-> r-> ans += rn * (rn + 1) / 2 * (rn + 2) / 3 * v;        x-> l-> sum += ln * v;        x-> r-> sum += rn * v;        x-> l-> up += ln * (ln + 1) / 2 * v;        x-> r-> up += rn * (rn + 1) / 2 * v;        x-> l-> down += ln * (ln + 1) / 2 * v;        x-> r-> down += rn * (rn + 1) / 2 * v;        x-> l-> lazy += v, x-> r-> lazy += v;        x-> lazy = 0;    }}void addlazy(node* now, qword l, qword r, qword ls, qword rs, qword v) {    if(now-> lazy != 0) pushdown(now, l, r);    if(l == ls && r == rs) {        qword nn = rs - ls + 1;         now-> ans += nn * (nn + 1) / 2 * (nn + 2) / 3 * v;        now-> sum += nn * v;        now-> up += nn * (nn + 1) / 2 * v;        now-> down += nn * (nn + 1) / 2 * v;        now-> lazy += v;    }    else {        qword mid = (l + r) >> 1;        if(rs <= mid) addlazy(now-> l, l, mid, ls, rs, v);        else if(ls > mid) addlazy(now-> r, mid + 1, r, ls, rs, v);        else addlazy(now-> l, l, mid, ls, mid, v), addlazy(now-> r, mid + 1, r, mid + 1, rs, v);        update(now, l, r, mid);    }}node ask(node* now, qword l, qword r, qword ls, qword rs) {    if(now-> lazy != 0) pushdown(now, l, r);    node ret;    if(l == ls && r == rs) ret = *now;    else {        qword mid = (l + r) >> 1;        if(rs <= mid) ret = ask(now-> l, l, mid, ls, rs);        else if(ls > mid) ret = ask(now-> r, mid + 1, r, ls, rs);        else {            node lr = ask(now-> l, l, mid, ls, mid);            node rr = ask(now-> r, mid + 1, r, mid + 1, rs);            ret.l = &lr, ret.r = &rr;            update(&ret, ls, rs, mid);        }    }    return ret;}qword qword_get() {    qword x = 0; char c = (char)getchar();    qword f = 0;    while(!isdigit(c) && c != ‘-‘) c = (char)getchar();    if(c == ‘-‘) c =(char)getchar(), f = 1;    while(isdigit(c)) {        x = x * 10 + (qword)(c - ‘0‘);        c = (char)getchar();    }    if(f) x = -x;    return x;}qword n, m;qword gcd(qword a, qword b) {    return a % b == 0 ? b : gcd(b, a % b);}void test(node* now, qword l, qword r) {    cout << l <<" "<< r <<" "<< now-> ans <<" "<< now-> sum <<" " << now-> up <<" "<< now-> down <<" "<< now-> lazy << endl;    if(l ^ r) {        qword mid = (l + r) >> 1;        test(now-> l, l, mid), test(now-> r, mid + 1, r);    }}void sov() {    n = qword_get(), m = qword_get();    root = build(1, n - 1);    char s[10];     while(m --) {        scanf("%s", s + 1);        if(s[1] ==‘C‘) {            qword ls, rs, v;             ls = qword_get(); rs = qword_get(); v = qword_get();            rs --;            addlazy(root, 1, n - 1, ls, rs, v);        }        if(s[1] == ‘Q‘) {            qword ls, rs;             ls = qword_get(), rs = qword_get();            rs --;            node ret = ask(root, 1, n - 1, ls, rs);            qword a = ret.ans;            qword b = (rs - ls + 1) * (rs - ls + 2) / 2;            qword g = gcd(a, b);            printf("%lld/%lld\n", a / g, b / g);        }    }}int main() {    //freopen("test.in", "r", stdin);    //freopen("test.out", "w", stdout);    sov();    return 0;}

 

bzoj 2752


联系
我们