Februrary @ 2024-03-16 15:36:29
#include <iostream>
#include <fstream>
using namespace std;
typedef long long ll;
const int maxn = 1000500;
ll a[maxn];
struct node {
int l, r;
ll w; // 代表区间内最大的值
ll tag1; // 用于将区间均修改为x
ll tag2; // 用于将区间均加上x
pair<int, int> q; // 用于后面向下传标签时,确定两个标签的顺序
} stree[4 * maxn];
int n, q;
void pushup(const int u);
inline bool inRange(int L, int R, int l, int r) {return (l <= L) && (R <= r);}
inline bool outRange(int L, int R, int l, int r) {return (R < l) || (L > r);}
void build(const int u, int L, int R) {
if(L == R) {
stree[u].w = a[L];
stree[u].l = stree[u].r = L;
stree[u].tag1 = 1e9 + 1; // 考虑数据范围<=1e9
return;
}
stree[u].l = L;
stree[u].r = R;
stree[u].tag1 = 1e9 + 1;
int M = (L + R) >> 1;
build(2 * u, L, M);
build(2 * u + 1, M + 1, R);
pushup(u);
}
void maketag1(const int u, ll change_value) {
// 防止下传标签被任意修改
if(change_value == 1e9 + 1) return;
stree[u].tag1 = change_value;
stree[u].w = change_value;
stree[u].q.first == 0 ? stree[u].q.first = 1 : stree[u].q.second = 1;
}
void maketag2(const int u, ll change_value) {
stree[u].tag2 += change_value;
stree[u].w += change_value;
stree[u].q.first == 0 ? stree[u].q.first = 2 : stree[u].q.second = 2;
}
void pushdown(const int u) {
// 两个标签的下传会有顺序,通过pair标记顺序
if(stree[u].q.first == 1) {
maketag1(2 * u, stree[u].tag1);
maketag1(2 * u + 1, stree[u].tag1);
maketag2(2 * u, stree[u].tag2);
maketag2(2 * u + 1, stree[u].tag2);
}
else if(stree[u].q.first == 2) {
maketag2(2 * u, stree[u].tag2);
maketag2(2 * u + 1, stree[u].tag2);
maketag1(2 * u, stree[u].tag1);
maketag1(2 * u + 1, stree[u].tag1);
}
stree[u].tag1 = 1e9 + 1;
stree[u].tag2 = 0;
stree[u].q.first = 0;
stree[u].q.second = 0;
}
void pushup(const int u) {
stree[u].w = max(stree[2 * u].w, stree[2 * u + 1].w);
}
void update(const int u, int l, int r, ll change_value, int opt) {
int L = stree[u].l;
int R = stree[u].r;
if(inRange(L, R, l, r)) {
if(opt == 1) maketag1(u, change_value);
else maketag2(u, change_value);
return;
}
else if(!outRange(L, R, l, r)) {
int M = (L + R) >> 1;
// 下放标签
pushdown(u);
update(2 * u, l, r, change_value, opt);
update(2 * u + 1, l, r, change_value, opt);
// 上传数据
pushup(u);
}
}
ll query(const int u, int l, int r) {
int L = stree[u].l;
int R = stree[u].r;
if(inRange(L, R, l, r)) {
return stree[u].w;
}
else if(outRange(L, R, l, r)) {
return -1e12;
}
pushdown(u);
return max(query(2 * u, l, r), query(2 * u + 1, l, r));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int j = 0; j < q; j++) {
int opt = 0;
int l ,r, x;
cin >> opt;
if(opt == 1) {
cin >> l >> r >> x;
update(1, l, r, x, opt);
}
else if(opt == 2) {
cin >> l >> r >> x;
update(1, l, r, x, opt);
}
else {
cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
return 0;
}
无法通过6-10,还有另外一个问题
对于第6个测试点,query()函数第二个情况的返回值如果修改为-1e9就无法通过,题目说明的数据范围为abs(x) <= 1e9
by Februrary @ 2024-03-16 16:28:28
已经解决了,还是标记下传顺序的问题