WikDD @ 2024-08-02 00:19:47
#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll arr[N], maxx[N*4], add[N*4], change[N*4];
bool update[N*4];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9'){if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
void up(int i)
{
maxx[i] = max(maxx[i*2], maxx[i*2+1]);
}
void updatelazy(int i, ll v)
{
maxx[i] = v;
add[i] = 0;
change[i] = v;
update[i] = true;
}
void addlazy(int i, ll v)
{
maxx[i] += v;
add[i] += v;
}
void down(int i)
{
if (update[i])
{
updatelazy(i*2, change[i]);
updatelazy(i*2+1, change[i]);
update[i] = false;
}
if (add[i] != 0)
{
addlazy(i*2, add[i]);
addlazy(i*2+1, add[i]);
add[i] = 0;
}
}
void build(int l, int r, int i)
{
if (l == r)
maxx[i] = arr[l];
else
{
int mid = (l + r) / 2;
build(l, mid, i*2);
build(mid + 1, r, i*2+1);
up(i);
}
add[i] = 0;
change[i] = 0;
update[i] = false;
}
void Update(int jobl, int jobr, ll jobv, int l, int r, int i)
{
if (jobl <= l && r <= jobr)
updatelazy(i, jobv);
else
{
int mid = (l + r) / 2;
down(i);
if (jobl <= mid)
Update(jobl, jobr, jobv, l, mid, i*2);
if (jobr > mid)
Update(jobl, jobr, jobv, mid + 1, r, i*2+1);
up(i);
}
}
void Add(int jobl, int jobr, ll jobv, int l, int r, int i)
{
if (jobl <= l && r <= jobr)
addlazy(i, jobv);
else
{
int mid = (l + r) / 2;
down(i);
if (jobl <= mid)
Add(jobl, jobr, jobv, l, mid, i*2);
if (jobr > mid)
Add(jobl, jobr, jobv, mid + 1, r, i*2+1);
up(i);
}
}
ll query(int jobl, int jobr, int l, int r, int i)
{
if (jobl <= l && r <= jobr)
return maxx[i];
int mid = (l + r) / 2;
down(i);
ll ans = -1000000010;
if (jobl <= mid)
ans = max(ans, query(jobl, jobr, l, mid, i*2));
if (jobr > mid)
ans = max(ans, query(jobl, jobr, mid + 1, r, i*2+1));
return ans;
}
int main()
{
ll n, m;
n = read();
m = read();
for (ll i = 1; i <= n; i++)
arr[i] = read();
build(1, n, 1);
while (m--)
{
int zuo, x, y; ll k;
zuo = read();
if (zuo == 1)
{
x = read(); y = read(); k = read();
Update(x, y, k, 1, n, 1);
}
else if (zuo == 2)
{
x = read(); y = read(); k = read();
Add(x, y, k, 1, n, 1);
}
else
{
x = read(); y = read();
printf("%lld\n", query(x, y, 1, n, 1));
}
}
}
by 2024wangyuxuan @ 2024-08-02 07:07:06
你这是哪一题? 线段树求最大值+区间修改吗?
by forgotmyhandle @ 2024-08-02 07:56:12
@2024wangyuxuan 但凡你看一下这篇讨论的所属板块。
by 2024wangyuxuan @ 2024-08-02 08:01:57
@forgotmyhandle 我傻掉了