cancan123456 @ 2024-06-22 10:59:16
代码放二楼
by cancan123456 @ 2024-06-22 10:59:23
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int B = 250;
const int N = 100005;
ll a[N];
struct Point {
int x;
ll y;
Point() {
x = 0;
y = 0;
}
Point(int a, ll b) {
x = a;
y = b;
}
ll calc(ll add) {
return x * add + y;
}
void print(char ch = ' ') const {
printf("(%d, %lld)%c", x, y, ch);
}
};
Point operator + (const Point & a, const Point & b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator - (const Point & a, const Point & b) {
return Point(a.x - b.x, a.y - b.y);
}
ll operator * (const Point & a, const Point & b) {
return a.x * b.y - a.y * b.x;
}
Point memory_pool[N];
static Point * iuhdfvuighdfuygduyf;
void clear_point() {
iuhdfvuighdfuygduyf = memory_pool;
}
Point * allocate_point(int size) {
Point * ans = iuhdfvuighdfuygduyf;
iuhdfvuighdfuygduyf += size;
return ans;
}
ll max(ll a, ll b) {
return a > b ? a : b;
}
struct VectorPoint {
int n, maxlen;
Point * point;
// max n = maxlen - 1
void allocate(int len) {
maxlen = len;
point = allocate_point(len);
}
void init(ll x) {
n = 1;
point[0] = Point(0, 0);
point[1] = Point(1, x);
}
const Point operator [] (int i) const {
return point[i];
}
Point & operator [] (int i) {
return point[i];
}
void push_tag(ll add) {
for (int i = 0; i <= n; i++) {
point[i].y += point[i].x * add;
}
}
// debug
void print() const {
for (int i = 0; i <= n; i++) {
point[i].print();
}
printf("\n");
}
};
struct ConvexHull {
VectorPoint point;
void allocate(int len) {
point.allocate(len);
}
void init(ll x) {
point.init(x);
}
void push_tag(int add) {
point.push_tag(add);
}
void construct() {
int top = 0;
for (int i = 0; i <= point.n; i++) {
while (top >= 2 && (point[i] - point[top - 2]) * (point[top - 1] - point[top - 2]) <= 0) {
top--;
}
point[top] = point[i];
top++;
}
point.n = top - 1;
}
void merge(const ConvexHull & __a, const ConvexHull & __b, ll add) {
// printf("---- merge ----\n");
// __a.print();
// __b.print();
// printf("add = %lld\n", add);
const VectorPoint & a = __a.point;
const VectorPoint & b = __b.point;
point.n = a.n + b.n;
for (int i = 0; i <= a.n; i++) {
point[i] = a[i];
}
point[a.n].y = max(point[a.n].y, b[0].y + add);
for (int i = 1; i <= b.n; i++) {
point[i + a.n] = b[i] + Point(a.maxlen - 1, add);
}
// print();
construct();
// print();
// printf("---- merge ----\n\n\n");
}
void Minkowski(const ConvexHull & __a, const ConvexHull & __b) {
const VectorPoint & a = __a.point;
const VectorPoint & b = __b.point;
point.n = a.n + b.n;
point[0] = a.point[0] + b.point[0];
int i = 0, j = 0;
while (i != a.n || j != b.n) {
if (i == a.n) {
j++;
point[i + j] = a[i] + b[j];
} else if (j == b.n) {
i++;
point[i + j] = a[i] + b[j];
} else {
if ((a[i + 1] + b[j] - point[i + j]) * (a[i] + b[j + 1] - point[i + j]) <= 0) {
i++;
point[i + j] = a[i] + b[j];
} else {
j++;
point[i + j] = a[i] + b[j];
}
}
}
}
void update(const ConvexHull & __a) {
const VectorPoint & a = __a.point;
const int n = point.n;
int m = -1, i = 0, j = 0;
while (i != point.n + 1 && j != a.n + 1) {
if (point[i].x == a[j].x) {
i++;
j++;
m++;
} else if (point[i].x < a[j].x) {
i++;
m++;
} else {
j++;
m++;
}
}
m += point.n - i + 1;
m += a.n - j + 1;
i = n;
j = a.n;
int cur = m;
while (i != -1 && j != -1) {
if (i == -1) {
point[cur] = a[j];
cur--;
j--;
} else if (j == -1) {
point[cur] = point[i];
cur--;
i--;
} else {
if (point[i].x == a[j].x) {
point[cur] = Point(point[i].x, max(point[i].y, a[j].y));
cur--;
i--;
j--;
} else if (point[i].x > a[j].x) {
point[cur] = point[i];
cur--;
i--;
} else {
point[cur] = a[j];
cur--;
j--;
}
}
}
point.n = m;
}
int p;
void clear_p() {
p = 0;
}
ll jump(ll add) {
while (p + 1 <= point.n && point[p + 1].calc(add) > point[p].calc(add)) {
p++;
}
return point[p].calc(add);
}
// debug
void print() const {
point.print();
}
};
struct Result {
ll pre, suf, ans, sum;
Result() {
pre = suf = ans = sum = 0;
}
Result(ll x) {
pre = suf = ans = max(x, 0);
sum = x;
}
Result(ll a, ll b, ll c, ll d) {
pre = a;
suf = b;
ans = c;
sum = d;
}
} res[N];
Result operator + (const Result & a, const Result & b) {
Result c;
c.pre = max(a.pre, a.sum + b.pre);
c.suf = max(b.suf, a.suf + b.sum);
c.ans = max(max(a.ans, b.ans), a.suf + b.pre);
c.sum = a.sum + b.sum;
return c;
}
struct Node {
int l, r;
ConvexHull pre, suf, ans;
ll sum, tag;
void clear_p() {
pre.clear_p();
suf.clear_p();
ans.clear_p();
}
void allocate(int len) {
pre.allocate(len);
suf.allocate(len);
ans.allocate(len);
}
Result jump(ll x) {
return Result(pre.jump(x), suf.jump(x), ans.jump(x), sum + x * (r - l + 1));
}
void clear_tag() {
tag = 0;
}
void push_tag(ll add) {
tag += add;
pre.push_tag(add);
suf.push_tag(add);
ans.push_tag(add);
}
// debug
void print() const {
printf("Interval [%d, %d]\n", l, r);
printf("pre: ");
pre.print();
printf("suf: ");
suf.print();
printf("ans: ");
ans.print();
printf("sum = %lld\n", sum);
printf("tag = %lld\n", tag);
}
} node[4 * B];
void push_tag(int p, ll tag) {
node[p].tag += tag;
node[p].pre.push_tag(tag);
node[p].suf.push_tag(tag);
node[p].ans.push_tag(tag);
// if (p == 4) {
// printf("sum: %lld + %lld\n", node[p].sum, (node[p].r - node[p].l + 1) * tag);
// }
node[p].sum += (node[p].r - node[p].l + 1) * tag;
}
void push_down(int p) {
push_tag(2 * p, node[p].tag);
push_tag(2 * p + 1, node[p].tag);
node[p].tag = 0;
}
void push_up(int p) {
node[p].pre.merge(node[2 * p].pre, node[2 * p + 1].pre, node[2 * p].sum);
node[p].suf.merge(node[2 * p + 1].suf, node[2 * p].suf, node[2 * p + 1].sum);
// if (p == 1) {
// printf("Minkowski: ");
// node[2 * p].suf.print();
// printf("Minkowski: ");
// node[2 * p + 1].pre.print();
// }
node[p].ans.Minkowski(node[2 * p].suf, node[2 * p + 1].pre);
// if (p == 1) {
// printf("Minkowski: ");
// node[p].ans.print();
// }
node[p].ans.update(node[2 * p].ans);
node[p].ans.update(node[2 * p + 1].ans);
node[p].ans.construct();
node[p].sum = node[2 * p].sum + node[2 * p + 1].sum;
// if (p == 2) {
// printf("%lld + %lld = %lld\n", node[2 * p].sum, node[2 * p + 1].sum, node[p].sum);
// }
}
void build(int p, int l, int r) {
node[p].l = l;
node[p].r = r;
node[p].clear_tag();
node[p].allocate(r - l + 2);
if (l == r) {
node[p].pre.init(a[l]);
node[p].suf.init(a[l]);
node[p].ans.init(a[l]);
node[p].sum = a[l];
} else {
int mid = (l + r) / 2;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
push_up(p);
}
// printf("\n\n\nnode[%d]:\n", p);
// node[p].print();
}
void add(int p, int l, int r, int tag) {
if (l <= node[p].l && node[p].r <= r) {
push_tag(p, tag);
} else {
push_down(p);
int mid = (node[p].l + node[p].r) / 2;
if (l <= mid) {
add(2 * p, l, r, tag);
}
if (mid + 1 <= r) {
add(2 * p + 1, l, r, tag);
}
push_up(p);
}
// printf("\n\n\nnode[%d]:\n", p);
// node[p].print();
}
struct Input {
int op, l, r, x, type;
} input[N];
struct Query {
int id;
ll x;
} temp[N];
bool operator < (const Query & a, const Query & b) {
return a.x < b.x;
}
int blo[N];
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
// clear_point();
// build(1, 1, 5);
// return 0;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &input[i].op, &input[i].l, &input[i].r);
if (input[i].op == 1) {
scanf("%d", &input[i].x);
}
}
for (int i = 1; i <= n; i++) {
blo[i] = (i - 1) / B + 1;
}
int len = blo[n];
for (int i = 1; i <= len; i++) {
clear_point();
int left = (i - 1) * B + 1, right = min(i * B, n);
// printf("------------------- blo#%d [%d, %d]\n", i, left, right);
// printf("a = ");
// for (int j = left; j <= right; j++) {
// printf("%lld ", a[j]);
// }
// printf("\n");
build(1, left, right);
// printf("built.\n");
for (int j = 1; j <= m; j++) {
if (blo[input[j].l] <= i && i <= blo[input[j].r]) {
if (input[j].l <= left && right <= input[j].r) {
// 整体.
input[j].type = input[j].op * 2 - 2;
} else {
// 零散.
input[j].type = input[j].op * 2 - 1;
}
} else {
input[j].type = -1;
}
}
ll total_tag = 0;
for (int j = 1; j <= m; j++) {
// printf("type[%d] = %d\n", j, input[j].type);
if (input[j].type == 0) {
total_tag += input[j].x;
} else if (input[j].type == 1) {
for (int k = max(left, input[j].l); k <= min(right, input[j].r); k++) {
a[k] += input[j].x;
}
} else if (input[j].type == 3) {
for (int k = max(left, input[j].l); k <= min(right, input[j].r); k++) {
res[j] = res[j] + Result(a[k] + total_tag);
}
}
}
// printf("------------\n");
// type = 3 处理完成.
// 只需要考虑 type = 0, 1, 2.
total_tag = 0;
for (int l = 1; l <= m; l++) {
if (input[l].type == -1 || input[l].type == 3) {
continue;
}
if (input[l].type == 1) {
// 零散修改.
// printf("\n\n\nadd 1 %d %d %d\n\n\n", max(input[l].l, left), min(input[l].r, right), input[l].x);
add(1, max(input[l].l, left), min(input[l].r, right), input[l].x);
} else {
// 仅有 整体修改 (0) 与 整体查询 (2)
int len = 0;
ll sum_tag = 0;
l--;
while (l + 1 <= m && input[l + 1].type != 1) {
l++;
if (input[l].type != -1 && input[l].type != 3) {
if (input[l].type == 0) {
sum_tag += input[l].x;
} else {
len++;
temp[len].id = l;
temp[len].x = sum_tag;
}
}
}
sort(temp + 1, temp + len + 1);
node[1].clear_p();
for (int j = 1; j <= len; j++) {
res[temp[j].id] = res[temp[j].id] + node[1].jump(total_tag + temp[j].x);
}
total_tag += sum_tag;
}
}
}
for (int i = 1; i <= m; i++) {
if (input[i].op == 2) {
printf("%lld\n", res[i].ans);
}
}
return 0;
}