社区讨论

哪里编译出错了?悬关求调

P5693EI 的第六分块参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lzpj8b38
此快照首次捕获于
2024/08/11 20:19
2 年前
此快照最后确认于
2024/08/11 21:03
2 年前
查看原帖
rt
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define il inline
#define inf (ll)(2e9)
using namespace std;

typedef long long ll;
ll n, q, a[400005], op, u, v, lazy;

struct Func {
    ll len, v;
    void add(ll tag) {
        v += len * tag;
    }
    Func operator+(const Func & f) const {
        return {len + f.len, v + f.v};
    }
};

inline Func maxfunc(Func f1, Func f2) {
#define k len
#define b v
    if (f1.k < f2.k || (f1.k == f2.k && f1.b < f2.b)) swap(f1, f2);
    return (f1.b >= f2.b)? f1 : f2;
}

inline ll intersect(Func f1, Func f2) {
    if (f1.k < f2.k || (f1.k == f2.k && f1.b < f2.b)) swap(f1, f2);
    if (f1.b >= f2.b) return inf;
    return (f2.b - f1.b) / (f1.k - f2.k);
}

struct Tree {
    Func l, r, sum, ans;
    ll x, tag;
    Tree operator+(const Tree & tr) const {
        Tree t;
        t.x = min({x, tr.x, intersect(ans, tr.ans), intersect(maxfunc(ans, tr.ans), r + tr.l), intersect(l, sum + tr.l), intersect(tr.r, tr.sum + r)});
        t.l = max(l, sum + tr.l);
        t.r = max(tr.r, tr.sum + r);
        t.sum = sum + tr.sum;
        t.ans = max({ans, tr.ans, r + tr.l});
        return t;
    }
} t[200005];

inline void move(ll x, ll tag) {
    t[x].tag += tag;
    t[x].x -= tag;
    t[x].l.add(tag);
    t[x].r.add(tag);
    t[x].sum.add(tag);
    t[x].ans.add(tag);
}

inline void up(ll x) {
    t[x] = t[ls] + t[rs];
}

inline void down(ll x) {
    move(ls, t[x].tag);
    move(rs, t[x].tag);
    t[x].tag = 0;
}

void build(ll x, ll l, ll r) {
    if (l == r) {
        Func f({1, a[l]});
        t[x] = {f, f, f, f, inf, 0};
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    up(x);
}

Tree query(ll x, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) return t[x];
    Tree ans({{-inf, 0}, {-inf, 0}, {0, 0}, {-inf, 0}, inf, 0});
    if (ql <= mid) {
        ans = ans + query(ls, l, mid, ql, qr);
    }
    if (mid < qr) {
        ans = ans + query(rs, mid + 1, r, ql, qr);
    }
    return ans;
}

void defeat(ll x, ll l, ll r, ll tag) {
    if (tag > t[x].x) {
        ll tag2 = t[x].tag + tag;
        t[x].tag = 0;
        defeat(ls, l, mid, tag2);
        defeat(rs, mid + 1, r, tag2);
        up(x);
    }
    else {
        move(x, tag);
    }
}

void update(ll x, ll l, ll r, ll ql, ll qr, ll tag) {
    if (ql <= l && r <= qr) {
        defeat(x, l, r, tag);
        return ;
    }
    down(x);
    if (ql <= mid) {
        update(ls, l, mid, ql, qr, tag);
    }
    if (mid < qr) {
        update(rs, mid + 1, r, ql, qr, tag);
    }
    up(x);
}

int main(){
    scanf("%lld%lld", &n, &q);
    for (ll i(1); i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    while (--q > -1) {
        scanf("%lld%lld%lld", &op, &u, &v);
        if (op & 1) {
            scanf("%lld", &lazy);
            update(1, 1, n, u, v, lazy);
        } else {
            printf("%lld\n", max(query(1, 1, n, u, v).ans.v, 0ll))
        }
    }
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...