求助 40分 查一天了 真不会改了qwq
#include<iostream>
using namespace std;
const int MAX = 5*1e5 + 10;
typedef long long ll;
#define lc (m<<1)
#define rc (m<<1|1)
inline void read(int &x) {
x=0;int w=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=x*w;
}
inline void push_up(int m);
inline void push_down(int m, int l, int r);
void build(int m, int l, int r);
inline void spread(int m,int l, int r, int a,int b, int a1, int b1);
void add(int m, int l, int r, int x, int y, int p);
void minn(int m, int l, int r, int x, int y, int p);
ll q_add(int m, int l, int r, int x, int y);
int maxa(int m, int l, int r, int x, int y);
int maxb(int m, int l, int r, int x, int y);
int f[MAX];
struct _tree{
int a, b, a1, b1;
int maxa, maxb, se, cnt;
ll sum;
}t[MAX<<2];
int main() {
int n, m;
read(n), read(m);
int a, b, x, y;
for(int i = 1; i <= n; ++i)
read(f[i]);
build(1, 1, n);
while(m--) {
read(a);
if(a == 1) {
read(x), read(y), read(b);
add(1, 1, n, x, y, b);
}
else if(a == 2) {
read(x), read(y), read(b);
minn(1, 1, n, x, y, b);
}
else if(a == 3) {
read(x), read(y);
printf("%lld\n", q_add(1, 1, n, x, y));
}
else if(a == 4) {
read(x), read(y);
printf("%d\n", maxa(1, 1, n, x, y));
}
else if(a == 5) {
read(x), read(y);
printf("%d\n", maxb(1, 1, n, x, y));
}
}
return 0;
}
inline void push_up(int m) {
t[m].maxa = max(t[lc].maxa, t[rc].maxa);
t[m].maxb = max(t[lc].maxb, t[rc].maxb);
if(t[lc].maxa == t[rc].maxa) {
t[m].se = max(t[lc].se, t[rc].se);
t[m].cnt = t[lc].cnt + t[rc].cnt;
}
else if(t[lc].maxa > t[rc].maxa) {
t[m].se = max(t[lc].se, t[rc].maxa);
t[m].cnt = t[lc].cnt;
}
else {
t[m].se = max(t[lc].maxa, t[rc].se);
t[m].cnt = t[rc].cnt;
}
t[m].sum = t[lc].sum + t[rc].sum;
}
void build(int m, int l, int r) {
if(l == r) {
t[m].sum = f[l];
t[m].maxa = f[l];
t[m].maxb = f[l];
t[m].cnt = 1;
t[m].se = INT32_MIN;
return ;
}
int mid = (l+r)>>1;
build(lc, l, mid);
build(rc, mid+1, r);
push_up(m);
}
inline void spread(int m,int l, int r, int a,int b, int a1, int b1) {
t[m].sum += 1LL*(a*t[m].cnt + a1*(r-l+1-t[m].cnt));
t[m].maxb = max(t[m].maxb, t[m].maxa + b);
t[m].b = max(t[m].b, t[m].a + b);
t[m].b1 = max(t[m].b1, t[m].a1 + b1);
t[m].maxa += a;
t[m].a += a;
t[m].a1 += a1;
if(t[m].se != INT32_MIN) t[m].se += a1;
}
inline void push_down(int m, int l, int r) {
int mid = (r+l)>>1;
int maxn = max(t[lc].maxa, t[rc].maxa);
if(maxn == t[lc].maxa)
spread(lc, l, mid, t[m].a, t[m].b, t[m].a1, t[m].b1);
else
spread(lc, l, mid, t[m].a1, t[m].b1, t[m].a1, t[m].b1);
if(maxn == t[rc].maxa)
spread(rc, mid+1, r, t[m].a, t[m].b, t[m].a1, t[m].b1);
else
spread(rc, mid+1, r, t[m].a1, t[m].b1, t[m].a1, t[m].b1);
t[m].a = t[m].b = t[m].a1 = t[m].b1 = 0;
}
void add(int m, int l, int r, int x, int y, int p) {
if(x <= l && r <= y) {
spread(m, l, r, p, p, p, p);
return ;
}
push_down(m, l, r);
int mid = (r+l)>>1;
if(x <= mid) add(lc, l, mid, x, y, p);
if(y > mid) add(rc, mid+1, r, x, y, p);
push_up(m);
}
void minn(int m, int l, int r, int x, int y, int p) {
if(x > r || y < l || p >= t[m].maxa) return ;
if(x <= l && r <= y && p > t[m].se) {
spread(m, l, r, p-t[m].maxa, p-t[m].maxa, 0, 0);
return ;
}
push_down(m, l, r);
int mid = (r+l)>>1;
minn(lc, l, mid, x, y, p);
minn(rc, mid+1, r, x, y, p);
push_up(m);
}
ll q_add(int m, int l, int r, int x, int y) {
if(x > r || y < l) return 0;
if(x <= l && r <= y) return t[m].sum;
push_down(m, l, r);
int mid = (l+r)>>1;
return q_add(lc, l, mid, x, y) + q_add(rc, mid+1, r, x, y);
}
int maxa(int m, int l, int r, int x, int y) {
if(x > r || y < l) return INT32_MIN;
if(x <= l && r <= y) return t[m].maxa;
push_down(m, l, r);
int mid = (r+l)>>1;
return max(maxa(lc, l, mid, x, y), maxa(rc, mid+1, r, x, y));
}
int maxb(int m, int l, int r, int x, int y) {
if(x > r || y < l) return INT32_MIN;
if(x <= l && r <= y) return t[m].maxb;
push_down(m, l, r);
int mid = (l+r)>>1;
return max(maxb(lc, l, mid, x, y), maxb(rc, mid+1, r, x, y));
}
1 5 9 10 过了 看不会来哪里是不对的...