通过建立线段树的数据结构,添加Lazy-Tag,实现区间修改和区间查询的操作
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 100015;
int a[N], tree[N << 2], tag[N << 2], ma[N << 2];
void push_up(int p)
{
tree[p] = tree[p << 1] + tree[p << 1 | 1];
ma[p] = max(ma[p << 1], ma[p << 1 | 1]);
}
void build(int p, int pl, int pr)
{
tag[p] = 0;
if (pl == pr)
{
tree[p] = a[pl];
ma[p] = a[pl];
return;
}
int mid = (pl + pr) >> 1;
build(p << 1, pl, mid);
build(p << 1 | 1, mid + 1, pr);
push_up(p);
}
void addtag(int p, int pl, int pr, int d)
{
tag[p] += d;
tree[p] += d * (pr - pl + 1);
ma[p] += d;
}
void push_down(int p, int pl, int pr)
{
if (tag[p])
{
int mid = (pl + pr) >> 1;
addtag(p << 1, pl, mid, tag[p]);
addtag(p << 1 | 1, mid + 1, pr, tag[p]);
tag[p] = 0;
}
}
void update(int l, int r, int p, int pl, int pr, int d)
{
if (l <= pl && pr <= r)
{
addtag(p, pl, pr, d);
return;
}
push_down(p, pl, pr);
int mid = (pl + pr) >> 1;
if (l <= mid)
update(l, r, p << 1, pl, mid, d);
if (r > mid)
update(l, r, p << 1 | 1, mid + 1, pr, d);
push_up(p);
}
int querySum(int l, int r, int p, int pl, int pr)
{
if (pl >= l && r >= pr)
return tree[p];
push_down(p, pl, pr);
int res = 0;
int mid = (pl + pr) >> 1;
if (l <= mid)
res += querySum(l, r, p << 1, pl, mid);
if (r > mid)
res += querySum(l, r, p << 1 | 1, mid + 1, pr);
return res;
}
int queryMax(int l, int r, int p, int pl, int pr)
{
if (pl >= l && r >= pr)
return ma[p];
push_down(p, pl, pr);
int res = SUB;
int mid = (pl + pr) >> 1;
if (l <= mid)
res = max(res, queryMax(l, r, p << 1, pl, mid));
if (r > mid)
res = max(res, queryMax(l, r, p << 1 | 1, mid + 1, pr));
return res;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
while (m--)
{
int q, l, r, d;
scanf("%d", &q);
if (q == 0)
{
scanf("%d%d%d", &l, &r, &d);
update(l, r, 1, 1, n, d);
}
else if (q == 1)
{
scanf("%d%d", &l, &r);
printf("%d\n", queryMax(l, r, 1, 1, n));
}
else if (q == 2)
{
scanf("%d%d", &l, &r);
printf("%d\n", querySum(l, r, 1, 1, n));
}
}
return 0;
}