Exile_Code @ 2024-01-01 23:56:15
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <unordered_set>
#include <math.h>
#include <functional>
#include<unordered_map>
#define ull unsigned long long
#define ll long long
#define pii pair<ll,ll>
#define ft first
#define sd second
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define forn(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define forne(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n) for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n) for(ll (i)=n;i>=1;i--)
#define vv vector
#define inf 1e9
const int N = 4e5 + 100;
const int mod = 1e9 + 7;
ll T;
class Segment_tree {
/*
叶子节点储存元素本身，非叶子节点存储统计值，用来维护区间和，区间最值，区间GCD
父节点的编号是p，左孩子的编号是2p，右孩子的编号是2p+1
*/
struct node {
ll l, r, add,mx,upd;
};
vv<node>tr;
vv<ll>w;
#define lc p<<1
#define rc (p<<1)|1
//p<<2一定是一个偶数，偶数的末位是0，所以按位或1，相当于+1
#define LEN(x) (tr[(x)].r - tr[(x)].l + 1) //区间长度包括端点
#define MID(x) (tr[(x)].l + tr[(x)].r) >> 1 //中间点
#define trpl tr[p].l
#define trpr tr[p].r
#define trps tr[p].sum
#define trpd tr[p].add
public:
void init(int n) {
tr = vv<node>(4 * n + 3);
w = vv<ll>(n + 1);
forne(i, n)
cin >> w[i];
build(1, 1, n);
}
void pushup(int p) {
//trps = tr[lc].sum + tr[rc].sum;
tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}
void build(int p, int l, int r) {
tr[p] = { l,r,0,w[l],0 };
if (l == r) return;
int m = MID(p);
build(lc, l, m); build(rc, m + 1, r);
pushup(p);
}
ll query(int p, int l, int r) {
ll mx = -1e9-100;
if (l <= trpl && trpr <= r)
return tr[p].mx;
int m = MID(p); pushdown(p);
if (l <= m) mx=max(mx,query(lc, l, r));
if (r > m) mx=max(mx,query(rc, l, r));
return mx;
}
void pushdown(int p) {
if (tr[p].upd) {
tr[p].mx = tr[p].upd;
tr[lc].upd = tr[p].upd;
tr[rc].upd = tr[p].upd;
tr[lc].add =0;
tr[rc].add =0;
tr[p].upd = 0;
}
if (tr[p].add) {
tr[lc].mx += tr[p].add;
tr[rc].mx += tr[p].add;
tr[lc].add += trpd;
tr[rc].add += trpd;
tr[p].add = 0;
}
}
//区间查询，拆分拼凑
//如果查询区间完全覆盖掉当前的节点区间，就立刻返回当前的区间值 On
void update(int p, int l, int r, int k) {
if (l <= trpl && trpr <= r) {
if (tr[p].upd != 0)
tr[p].upd += k;
else
trpd += k;
tr[p].mx += k;
return;
}
int m = MID(p);
pushdown(p);
if (l <= m) update(lc, l, r, k);
if (r > m) update(rc, l, r, k);
pushup(p);
}
void update_all(int p, int l, int r, int x) {
if (l <= trpl && trpr <= r) {
tr[p].upd = x;
tr[p].add = 0;
tr[p].mx = x;
return;
}
int m = MID(p);
pushdown(p);
if (l <= m) update_all(lc, l, r, x);
if (r > m) update_all(rc, l, r, x);
pushup(p);
}
};
void solve() {
//1 1 4 5 1 4
//6 6 4 5 1 4
//6 6 6 7 1 4
//
int n, q;
cin >> n >> q;
Segment_tree fuction;
fuction.init(n);
while (q--) {
int ch; cin >> ch;
if (ch == 1) {
int l, r, x; cin >> l >> r >> x;
fuction.update_all(1, l, r, x);
}
else if(ch==2) {
int l, r, x; cin >> l >> r >> x;
fuction.update(1,l, r, x);
}
else {
int l, r; cin >> l >> r;
cout << fuction.query(1, l, r) << endl;
}
}
}
int main() {
T = 1;
//cin >> T;
while (T--)
solve();
}by 杜都督 @ 2024-01-30 06:03:04
修改的地方我基本上都用@@@标注了，如果漏标请自行消化（最近太累了检查不动了）
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <unordered_set>
#include <math.h>
#include <functional>
#include<unordered_map>
#define ull unsigned long long
#define ll long long
#define pii pair<ll,ll>
#define ft first
#define sd second
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define forn(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define forne(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n) for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n) for(ll (i)=n;i>=1;i--)
#define vv vector
#define inf (0x3f3f3f3f3f3f3f3f) // @@@inf也应该是ll级别的，1e9是不够的（至少对于query()来说）
const int N = 4e5 + 100;
const int mod = 1e9 + 7;
ll T;
class Segment_tree {
/*
叶子节点储存元素本身，非叶子节点存储统计值，用来维护区间和，区间最值，区间GCD
父节点的编号是p，左孩子的编号是2p，右孩子的编号是2p+1
*/
struct node {
ll l, r, add,mx,upd;
};
vv<node>tr;
vv<ll>w;
#define lc p<<1
#define rc (p<<1)|1
//p<<2一定是一个偶数，偶数的末位是0，所以按位或1，相当于+1
#define LEN(x) (tr[(x)].r - tr[(x)].l + 1) //区间长度包括端点
#define MID(x) (tr[(x)].l + tr[(x)].r) >> 1 //中间点
#define trpl tr[p].l
#define trpr tr[p].r
#define trps tr[p].sum
#define trpd tr[p].add
public:
void init(int n) {
tr = vv<node>(4 * n + 3);
w = vv<ll>(n + 1);
forne(i, n)
cin >> w[i];
build(1, 1, n);
}
void pushup(int p) {
//trps = tr[lc].sum + tr[rc].sum;
tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}
void build(int p, int l, int r) {
tr[p] = { l,r,0,w[l],inf }; // @@@upd操作存在x == 0的情况，所以直接用tr[p].upd是否为0来标识是否进行upd操作是狭隘的，可以考虑将inf视为不进行upd，而一切<inf的（包括0和负数）都视为进行upd
if (l == r) return;
int m = MID(p);
build(lc, l, m); build(rc, m + 1, r);
pushup(p);
}
ll query(int p, int l, int r) {
ll mx = -inf; // @@@
if (l <= trpl && trpr <= r)
return tr[p].mx;
int m = MID(p); pushdown(p);
if (l <= m) mx=max(mx,query(lc, l, r));
if (r > m) mx=max(mx,query(rc, l, r));
return mx;
}
void pushdown(int p) {
if (tr[p].upd < inf) { // @@@
// tr[p].mx = tr[p].upd; @@@你原来那么写也行
tr[lc].mx = tr[p].upd; // @@@
tr[rc].mx = tr[p].upd; // @@@
tr[lc].upd = tr[p].upd;
tr[rc].upd = tr[p].upd;
tr[lc].add =0;
tr[rc].add =0;
tr[p].upd = inf; // @@@
}
if (tr[p].add) {
tr[lc].mx += tr[p].add;
tr[rc].mx += tr[p].add;
if (tr[lc].upd < inf) tr[lc].upd += tr[p].add; // @@@重要逻辑，如果upd标记已存在，则直接将upd加上add即可，无需修改add标记，否则才修改add标记
else tr[lc].add += trpd; // @@@
if (tr[rc].upd < inf) tr[rc].upd += tr[p].add; // @@@
else tr[rc].add += trpd; // @@@
tr[p].add = 0;
}
}
//区间查询，拆分拼凑
//如果查询区间完全覆盖掉当前的节点区间，就立刻返回当前的区间值 On
void update(int p, int l, int r, int k) {
if (l <= trpl && trpr <= r) {
if (tr[p].upd < inf) // @@@
tr[p].upd += k;
else
trpd += k;
tr[p].mx += k;
return;
}
int m = MID(p);
pushdown(p);
if (l <= m) update(lc, l, r, k);
if (r > m) update(rc, l, r, k);
pushup(p);
}
void update_all(int p, int l, int r, int x) {
if (l <= trpl && trpr <= r) {
tr[p].upd = x;
tr[p].add = 0;
tr[p].mx = x;
return;
}
int m = MID(p);
pushdown(p);
if (l <= m) update_all(lc, l, r, x);
if (r > m) update_all(rc, l, r, x);
pushup(p);
}
};
void solve() {
// @@@不这么做会导致#10TLE
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//1 1 4 5 1 4
//6 6 4 5 1 4
//6 6 6 7 1 4
//
int n, q;
cin >> n >> q;
Segment_tree fuction;
fuction.init(n);
while (q--) {
int ch; cin >> ch;
if (ch == 1) {
int l, r, x; cin >> l >> r >> x;
fuction.update_all(1, l, r, x);
}
else if(ch==2) {
int l, r, x; cin >> l >> r >> x;
fuction.update(1,l, r, x);
}
else {
int l, r; cin >> l >> r;
cout << fuction.query(1, l, r) << endl;
}
}
}
int main() {
T = 1;
//cin >> T;
while (T--)
solve();
}