lwyznoip @ 2024-07-11 20:44:25
#include <bits/stdc++.h>
#define lc id << 1
#define rc id << 1 | 1
#define int long long
using namespace std;
int n, m;
struct node{
int l, r;
int add, cov;
int maxx;
} tr[4000005];
void pushdown (int id){
tr[id].maxx = max (tr[lc].maxx, tr[rc].maxx);
}
void build (int id, int x, int y){
tr[id].l = x;
tr[id].r = y;
tr[id].cov = 0x3f3f3f3f;
tr[id].add = 0;
if (x == y) {
cin >> tr[id].maxx;
return;
}
int mid = (x + y) / 2;
build (lc, x, mid);
build (rc, mid + 1, y);
pushdown (id);
}
void pushup (int id){
if (tr[id].cov != 0x3f3f3f3f){
tr[lc].cov = tr[id].cov;
tr[rc].cov = tr[id].cov;
tr[lc].maxx = tr[id].cov;
tr[rc].maxx = tr[id].cov;
tr[lc].add = tr[id].cov;
tr[rc].add = tr[id].cov;
tr[id].cov = 0x3f3f3f3f;
}
if (tr[id].add){
tr[lc].maxx += tr[id].add;
tr[rc].maxx += tr[id].add;
tr[lc].add += tr[id].add;
tr[rc].add += tr[id].add;
tr[id].add = 0;
}
}
void covv (int id, int x, int y, int k){
if (x > tr[id].r || y < tr[id].l) return;
if (x <= tr[id].l && tr[id].r <= y){
tr[id].maxx = k;
tr[id].cov = k;
tr[id].add = k;
return;
}
pushdown (id);
covv (lc, x, y, k);
covv (rc, x, y, k);
pushup (id);
}
void addd (int id, int x, int y, int k){
if (x > tr[id].r || y < tr[id].l) return;
if (x <= tr[id].l && tr[id].r <= y){
tr[id].maxx += k;
tr[id].add += k;
return;
}
pushdown (id);
addd (lc, x, y, k);
addd (rc, x, y, k);
pushup (id);
}
int query (int id, int x, int y){
if (x > tr[id].r || y < tr[id].l) return 0;
if (x <= tr[id].l && tr[id].r <= y){
return tr[id].maxx;
}
pushdown (id);
return max (query (lc, x, y), query(rc, x, y));
}
signed main(){
cin >> n >> m;
build (1, 1, n);
while (m --){
int op, x, y, k;
cin >> op >> x >> y;
if (op == 1){
cin >> k;
covv (1, x, y, k);
}
if (op == 2){
cin >> k;
addd (1, x, y, k);
}
if (op == 3){
cout << query (1, x, y) << endl;
}
}
}by lwyznoip @ 2024-07-11 20:44:48
在线等，挺急的
by FOX_konata @ 2024-07-12 08:44:41
#include <bits/stdc++.h>
#define lc id << 1
#define rc id << 1 | 1
#define int long long
#define INF (1ll << 60)
using namespace std;
int n, m;
struct node{
int l, r;
int add, cov;
int maxx;
} tr[4000005];
void pushup (int id){
tr[id].maxx = max (tr[lc].maxx, tr[rc].maxx);
}
void build (int id, int x, int y){
tr[id].l = x;
tr[id].r = y;
tr[id].cov = INF;
tr[id].add = 0;
if (x == y) {
cin >> tr[id].maxx;
return;
}
int mid = (x + y) / 2;
build (lc, x, mid);
build (rc, mid + 1, y);
pushup (id);
}
void pushdown (int id){
if (tr[id].cov != INF){
tr[lc].cov = tr[id].cov;
tr[rc].cov = tr[id].cov;
tr[lc].maxx = tr[id].cov;
tr[rc].maxx = tr[id].cov;
tr[lc].add = 0;
tr[rc].add = 0;
tr[id].cov = INF;
}
if (tr[id].add){
tr[lc].maxx += tr[id].add;
tr[rc].maxx += tr[id].add;
tr[lc].add += tr[id].add;
tr[rc].add += tr[id].add;
tr[id].add = 0;
}
}
void covv (int id, int x, int y, int k){
if (x > tr[id].r || y < tr[id].l) return;
if (x <= tr[id].l && tr[id].r <= y){
tr[id].maxx = k;
tr[id].cov = k;
tr[id].add = 0;
return;
}
pushdown (id);
covv (lc, x, y, k);
covv (rc, x, y, k);
pushup (id);
}
void addd (int id, int x, int y, int k){
if (x > tr[id].r || y < tr[id].l) return;
if (x <= tr[id].l && tr[id].r <= y){
tr[id].maxx += k;
tr[id].add += k;
return;
}
pushdown (id);
addd (lc, x, y, k);
addd (rc, x, y, k);
pushup (id);
}
int query (int id, int x, int y){
if (x > tr[id].r || y < tr[id].l) return -INF;
if (x <= tr[id].l && tr[id].r <= y){
return tr[id].maxx;
}
pushdown (id);
return max (query (lc, x, y), query(rc, x, y));
}
signed main(){
scanf("%lld%lld", &n, &m);
build (1, 1, n);
while (m --){
int op, x, y, k;
scanf("%lld%lld%lld", &op, &x, &y);
if (op == 1){
scanf("%lld", &k);
covv (1, x, y, k);
}
if (op == 2){
scanf("%lld", &k);
addd (1, x, y, k);
}
if (op == 3){
printf("%lld\n", query(1, x, y));
}
}
}