社区讨论
哪里编译出错了?悬关求调
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 条回复,欢迎继续交流。
正在加载回复...