线段树3

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <set>
#include <map>
using namespace std;
int read ()
{
	int x=0, w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-', ch=getchar();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return w?-x:x;
}
const int maxn = 550000 , INF = 2147383647; int op, n, m, x, y, k, ip[maxn];
struct worker 
{
	int l, r; //l表示左儿子，r表示右儿子。
	int now_mx, history_mx, se, cnt; //依次存储的是：该节点表示的区间的 现在的最大值， 从头到现在出现过的最大值， 现在第二大值，现在最大值的数量。
	int add_max, history_add_max, add_nomax, history_add_nomax; //最大值的目前加标记， 从头到现在出现过的最大加标记，那俩不写了， nomax就是非最大值 
	long long sum; //区间所有数的和 
} tree[maxn << 2];
void push_up (int i)
{
	int lc = i << 1, rc = (i << 1) + 1;
	tree[i].sum = tree[lc].sum + tree[rc].sum; tree[i].history_mx = max (tree[lc].history_mx, tree[rc].history_mx);
	if (tree[lc].now_mx == tree[rc].now_mx) {tree[i].now_mx = tree[lc].now_mx; tree[i].se = max (tree[lc].se, tree[rc].se); tree[i].cnt = tree[lc].cnt + tree[rc].cnt;}
	else if (tree[lc].now_mx > tree[rc].now_mx) {tree[i].now_mx = tree[lc].now_mx; tree[i].se = max (tree[lc].se, tree[rc].now_mx); tree[i].cnt = tree[lc].cnt;}
	else {tree[i].now_mx = tree[rc].now_mx; tree[i].cnt = tree[rc].cnt; tree[i].se = max (tree[lc].now_mx, tree[rc].se);}
}
void update (int i, int c, int v, int b, int z)//c:要加的区间最大值的加标记， v：要加的区间最大值的历史最大加标记， b、z非最大值的
{
	tree[i].sum += c * tree[i].cnt + (tree[i].r - tree[i].l - tree[i].cnt + 1) * b;
	tree[i].history_mx = max (tree[i].history_mx, tree[i].now_mx + v); tree[i].now_mx += c;
	tree[i].history_add_max = max (tree[i].history_add_max, tree[i].add_max + v); tree[i].add_max += c;
	tree[i].history_add_nomax = max (tree[i].history_add_nomax, tree[i].add_nomax + z); tree[i].add_nomax += b;
	if (tree[i].se != -INF) tree[i].se += b;  
} 
void push_down (int i)
{
	int lc = i << 1, rc = (i << 1) + 1, temp = max (tree[lc].now_mx, tree[rc].now_mx);
	if (temp == tree[lc].now_mx) update (lc, tree[i].add_max, tree[i].history_add_max, tree[i].add_nomax, tree[i].history_add_nomax);
	else update (lc, tree[i].add_nomax, tree[i].history_add_nomax, tree[i].add_nomax, tree[i].history_add_nomax);
	if (temp == tree[rc].now_mx) update (rc, tree[i].add_max, tree[i].history_add_max, tree[i].add_nomax, tree[i].history_add_nomax);
	else update (rc, tree[i].add_nomax, tree[i].history_add_nomax, tree[i].add_nomax, tree[i].history_add_nomax);
	tree[i].add_max = tree[i].add_nomax = tree[i].history_add_max = tree[i].history_add_nomax = 0;
}
void build (int i, int l, int r)
{
	tree[i].l = l; tree[i].r = r; tree[i].history_add_max = tree[i].history_add_nomax = tree[i].add_max = tree[i].add_nomax = 0;
	if (l == r) {tree[i].sum = tree[i].now_mx = tree[i].history_mx = ip[l]; tree[i].se = -INF; tree[i].cnt = 1; return;}
	int mid = (l + r) >> 1; build (i << 1, l, mid); build ((i << 1) + 1, mid + 1, r);
	push_up (i); return;
}
void update_add (int i, int l, int r, int c)
{
	if (tree[i].l > r || tree[i].r < l) return; 
	if (tree[i].l >= l && tree[i].r <= r) {update (i, c, c, c, c); return;}
	push_down (i); update_add (i << 1, l, r, c); update_add ((i << 1) + 1, l, r, c);
	push_up (i);
}
void minf (int i, int l, int r, int c)
{
	if (tree[i].l > r || tree[i].r < l || tree[i].now_mx <= c) return;
	if (tree[i].l >= l && tree[i].r <= r && tree[i].se < c) {update (i, c - tree[i].now_mx, c - tree[i].now_mx, 0, 0); return;}
	push_down (i); minf (i << 1, l, r, c); minf ((i << 1) + 1, l, r, c); push_up (i);
}
long long askf (int i, int l, int r)
{
	if (tree[i].l > r || tree[i].r < l) return 0;
	if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
	push_down (i); return askf (i << 1, l, r) + askf ((i << 1) + 1, l, r); 
}
int asks (int i, int l, int r)
{
	if (tree[i].l > r || tree[i].r < l) return -INF;
	if (tree[i].l >= l && tree[i].r <= r) return tree[i].now_mx;
	push_down (i); return max (asks (i << 1, l, r), asks ((i << 1) + 1, l, r));
}
int askt (int i, int l, int r)
{
	if (tree[i].l > r || tree[i].r < l) return -INF;
	if (tree[i].l >= l && tree[i].r <= r) return tree[i].history_mx;
	push_down (i); return max (askt (i << 1, l, r), askt ((i << 1) + 1, l, r));
}
int main ()
{
	n = read (); m = read (); for (int i = 1; i <= n; i++) ip[i] = read (); build (1, 1, n);
	for (int i = 1; i <= m; i++) 
	{
		op = read (); if (op == 1) {x = read (); y = read (); k = read (); update_add (1, x, y, k);}
		else if (op == 2) {x = read (); y = read (); k = read (); minf (1, x, y, k);} else if (op == 3) {x = read (); y = read (); printf ("%lld\n", askf (1, x, y));}
		else if (op == 4) {x = read (); y = read (); printf ("%d\n", asks (1, x, y));} else {x = read (); y = read (); printf ("%d\n", askt (1, x, y));}
	} 
	return 0;
}
/*
快读：
int x=0, w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-', ch=getchar();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return w?-x:x; 
*/