[template] segment tree 3

Title Link: luogu P6242

General idea of the topic

Give you an array and ask you to maintain something:
Interval addition, interval takes the minimum value, interval summation, interval maximum value, interval maximum value of historical maximum value of each position.

thinking

The difficulty of this problem is that you can't maintain the interval sum with an ordinary line segment tree.

So we need to use the tree.
It mainly maintains the first and second largest things. If it is greater than or equal to the first one, it will certainly not be updated. If it is greater than the second one, it will only update the first one. Just do it, otherwise it will be updated recursively.

Then start talking about how to maintain:

l s x , r s x ls_x,rs_x lsx, rsx: left and right sons
s u m x sum_x sumx: interval weight sum
m a x a x maxa_x maxax: maximum number of intervals
s e c x sec_x secx: the second largest number in the interval
c n t x cnt_x cntx: number of maximum number of intervals
m a x b x maxb_x maxbx: historical maximum number of intervals
a d d _ a x add\_a_x add_ax: lazy mark of the addition of interval maximum
a d d _ a 1 x add\_a1_x add_a1x: the lazy flag of the addition of the interval that is not the maximum value (because you can either recurse or make the maximum value, so you can maintain it this way)
a d d _ b x , a d d _ b 1 x add\_b_x,add\_b1_x add_bx​,add_b1x: similarly, but this is the lazy flag of historical maximum and historical non maximum.

Then you consider how to maintain:

First, upload: m a x a , m a x b maxa,maxb maxa,maxb directly take the maximum value, s u m sum sum directly adds up, s e c , c n t sec,cnt SEC and CNT can be classified and discussed if they are a little more complicated.
Next is the down pass: considering that there is the maximum value, give the down pass maximum to its maximum, otherwise its maximum is the non maximum of this (the non maximum on both sides is naturally non maximum)
As for how to give, it is a difficulty of this segment tree.

First, add all the maximum plus multiplied by the maximum number and the non maximum plus and non maximum number (the non maximum number subtracts the maximum number from all).
Then add what history needs to add, and add their own lazy tags, and then add their own anyway. For details, see this Code:

void update(int now, int k1, int k2, int k3, int k4) {//k1: maximum to be added k2: historical maximum to be added k3: non maximum to be added k4: historical non maximum to be added
	sum[now] += 1ll * k1 * cnt[now] + 1ll * k3 * (rs[now] - ls[now] + 1 - cnt[now]);
	maxb[now] = max(maxb[now], maxa[now] + k2);//Historical maximum plus historical
	add_b[now] = max(add_b[now], add_a[now] + k2);//Remember to add the lazy mark
	add_b1[now] = max(add_b1[now], add_a1[now] + k4);//Non maximum lazy tags should also be available
	maxa[now] += k1; add_a[now] += k1;
	if (sec[now] != 1e9) sec[now] += k3; add_a1[now] += k3;
}

Then other operations are easier.

code

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

int re, zf; char c;
int read() {
	re = 0; zf = 1;
	c = getchar(); while (c < '0' || c > '9') {if (c == '-') zf = -zf; c = getchar();}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return zf * re;
}

void writee(ll x) {
	if (x > 9) writee(x / 10), x %= 10;
	putchar(x + '0');
}

void write(ll x) {
	if (x < 0) putchar('-'), x = -x;
	writee(x);
	putchar('\n');
}

const int N = 500001;
int n, m, a[N], op, l, r, x;

struct XD_tree {
	ll sum[N << 2];
	int add_a[N << 2], add_b[N << 2], add_a1[N << 2], add_b1[N << 2];
	int ls[N << 2], rs[N << 2], maxa[N << 2], sec[N << 2], maxb[N << 2], cnt[N << 2];
	
	void up(int now) {
		maxa[now] = max(maxa[now << 1], maxa[now << 1 | 1]);
		maxb[now] = max(maxb[now << 1], maxb[now << 1 | 1]);
		sum[now] = sum[now << 1] + sum[now << 1 | 1];
		if (maxa[now << 1] == maxa[now << 1 | 1]) {//Small classification discussion
			sec[now] = max(sec[now << 1], sec[now << 1 | 1]);
			cnt[now] = cnt[now << 1] + cnt[now << 1 | 1];
		}
		else if (maxa[now << 1] > maxa[now << 1 | 1]) {
			sec[now] = max(sec[now << 1], maxa[now << 1 | 1]);
			cnt[now] = cnt[now << 1];
		}
		else {
			sec[now] = max(maxa[now << 1], sec[now << 1 | 1]);
			cnt[now] = cnt[now << 1 | 1];
		}
	}
	
	void update(int now, int k1, int k2, int k3, int k4) {//k1: maximum to be added k2: historical maximum to be added k3: non maximum to be added k4: historical non maximum to be added
		sum[now] += 1ll * k1 * cnt[now] + 1ll * k3 * (rs[now] - ls[now] + 1 - cnt[now]);
		maxb[now] = max(maxb[now], maxa[now] + k2);//Historical maximum plus historical
		add_b[now] = max(add_b[now], add_a[now] + k2);//Remember to add the lazy mark
		add_b1[now] = max(add_b1[now], add_a1[now] + k4);//Non maximum lazy tags should also be available
		maxa[now] += k1; add_a[now] += k1;
		if (sec[now] != 1e9) sec[now] += k3; add_a1[now] += k3;
	}
	
	void down(int now) {
		int x = max(maxa[now << 1], maxa[now << 1 | 1]);//You can't use maxa[now] here, because you add a new value when you mark it
		if (maxa[now << 1] == x) update(now << 1, add_a[now], add_b[now], add_a1[now], add_b1[now]);
			else update(now << 1, add_a1[now], add_b1[now], add_a1[now], add_b1[now]);
		if (maxa[now << 1 | 1] == x) update(now << 1 | 1, add_a[now], add_b[now], add_a1[now], add_b1[now]);
			else update(now << 1 | 1, add_a1[now], add_b1[now], add_a1[now], add_b1[now]);
		add_a[now] = add_b[now] = add_a1[now] = add_b1[now] = 0;
	}
	
	void build(int now, int l, int r) {
		ls[now] = l; rs[now] = r;
		if (l == r) {
			sum[now] = maxa[now] = maxb[now] = a[l];
			sec[now] = -1e9; cnt[now] = 1;
			return ;
		}
		int mid = (l + r) >> 1; build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	void update_add(int now) {
		if (ls[now] > r || rs[now] < l) return ;
		if (l <= ls[now] && rs[now] <= r) {
			update(now, x, x, x, x); return ;
		}
		down(now);
		update_add(now << 1); update_add(now << 1 | 1);
		up(now);
	}
	
	void update_min(int now) {
		if (ls[now] > r || rs[now] < l || x >= maxa[now]) return ;//If it is greater than the maximum, it will not be updated
		if (l <= ls[now] && rs[now] <= r && x > sec[now]) {//If it is larger than the second largest, only the maximum value will change
			update(now, x - maxa[now], x - maxa[now], 0, 0); return ;//It's equivalent to adding negative numbers to make up for it
		}
		down(now);//Otherwise, continue recursion
		update_min(now << 1); update_min(now << 1 | 1);
		up(now);
	}
	
	ll get_sum(int now) {
		if (ls[now] > r || rs[now] < l) return 0;
		if (l <= ls[now] && rs[now] <= r) return sum[now];
		down(now);
		return get_sum(now << 1) + get_sum(now << 1 | 1);
	}
	
	int get_maxa(int now) {
		if (ls[now] > r || rs[now] < l) return -1e9;
		if (l <= ls[now] && rs[now] <= r) return maxa[now];
		down(now); return max(get_maxa(now << 1), get_maxa(now << 1 | 1));
	}
	
	int get_maxb(int now) {
		if (ls[now] > r || rs[now] < l) return -1e9;
		if (l <= ls[now] && rs[now] <= r) return maxb[now];
		down(now); return max(get_maxb(now << 1), get_maxb(now << 1 | 1));
	}
}T;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	T.build(1, 1, n);
	while (m--) {
		op = read(); l = read(); r = read();
		if (op == 1) x = read(), T.update_add(1);
		if (op == 2) x = read(), T.update_min(1);
		if (op == 3) write(T.get_sum(1));
		if (op == 4) write(T.get_maxa(1)); 
		if (op == 5) write(T.get_maxb(1));
	}
	
	return 0;
}