# [template] segment tree 3

## 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 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
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;
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 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
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
}

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);
}

if (ls[now] > r || rs[now] < l) return ;
if (l <= ls[now] && rs[now] <= r) {
update(now, x, x, x, x); return ;
}
down(now);
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() {
for (int i = 1; i <= n; i++) a[i] = read();
T.build(1, 1, n);
while (m--) {