Maintaining Range Minimum and Historical Maximum

When a segment tree needs to support range addition, range minimum assignment, range sum, range maximum, and range historical maximum, a standard approach involves tracking the maximum value, strict second maximum value, and the count of maximum values within each node. Operations affecting the minimum are only applied directly to segments where the second maximum is less than the target value, which is less than the current maximum. Otherwise, the recursion continues downwards. Through potential analysis, the complexity remains O((n+m)log n) without range additions, and O(mlog^2 n) when range additions are included.

The lazy propagation mechanism requires four distinct tags:

• inc_max: Increment applied to current maximum values.
• inc_other: Increment applied to current non-maximum values.
• hist_inc_max: Historical maximum increment applied to maximum values.
• hist_inc_other: Historical maximum increment applied to non-maximum values.

A critical rule during propagation is to update the historical values before modifying the current values.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 2e9;
const int MAXN = 500005;

int arr[MAXN];

struct Node {
    ll total_sum;
    int seg_len, cur_max, max_count, sec_max, hist_max;
    int inc_max, inc_other, hist_inc_max, hist_inc_other;
} tree[MAXN * 4];

void apply_tags(int idx, int d_max, int d_other, int hd_max, int hd_other) {
    tree[idx].total_sum += 1LL * d_max * tree[idx].max_count + 1LL * d_other * (tree[idx].seg_len - tree[idx].max_count);
    tree[idx].hist_max = max(tree[idx].hist_max, tree[idx].cur_max + hd_max);
    tree[idx].cur_max += d_max;
    if (tree[idx].sec_max != -INF) tree[idx].sec_max += d_other;
    tree[idx].hist_inc_max = max(tree[idx].hist_inc_max, tree[idx].inc_max + hd_max);
    tree[idx].hist_inc_other = max(tree[idx].hist_inc_other, tree[idx].inc_other + hd_other);
    tree[idx].inc_max += d_max;
    tree[idx].inc_other += d_other;
}

void push_down(int idx) {
    int left_max = tree[idx * 2].cur_max, right_max = tree[idx * 2 + 1].cur_max;
    int global_max = max(left_max, right_max);
    
    if (left_max == global_max) apply_tags(idx * 2, tree[idx].inc_max, tree[idx].inc_other, tree[idx].hist_inc_max, tree[idx].hist_inc_other);
    else apply_tags(idx * 2, tree[idx].inc_other, tree[idx].inc_other, tree[idx].hist_inc_other, tree[idx].hist_inc_other);
    
    if (right_max == global_max) apply_tags(idx * 2 + 1, tree[idx].inc_max, tree[idx].inc_other, tree[idx].hist_inc_max, tree[idx].hist_inc_other);
    else apply_tags(idx * 2 + 1, tree[idx].inc_other, tree[idx].inc_other, tree[idx].hist_inc_other, tree[idx].hist_inc_other);
    
    tree[idx].inc_max = tree[idx].inc_other = tree[idx].hist_inc_max = tree[idx].hist_inc_other = 0;
}

Range Addition, Assignment, and Historical Maximum

To handle range maximum, historical maximum, range addition, and range assignment (overwrites), the lazy tags expand to track current addition, current assignment, and their historical peaks. Specifically, four tags are maintained: add_val (addition), set_val (assignment), hist_add (peak addition), and hist_set (peak assignment). When pushing down, the historical state must capture the maximum possible value reached at any point.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

struct Node {
    int cur_max, hist_max;
    int add_val, set_val, hist_add, hist_set;
    bool is_set;
} seg[MAXN * 4];

void apply_add(int idx, int add, int hist_add) {
    seg[idx].hist_max = max(seg[idx].hist_max, seg[idx].cur_max + hist_add);
    seg[idx].cur_max += add;
    if (seg[idx].is_set) {
        seg[idx].hist_set = max(seg[idx].hist_set, seg[idx].set_val + hist_add);
        seg[idx].set_val += add;
    } else {
        seg[idx].hist_add = max(seg[idx].hist_add, seg[idx].add_val + hist_add);
        seg[idx].add_val += add;
    }
}

void apply_set(int idx, int set, int hist_set) {
    seg[idx].set_val = seg[idx].cur_max = set;
    seg[idx].hist_max = max(seg[idx].hist_max, hist_set);
    if (seg[idx].is_set) {
        seg[idx].hist_set = max(seg[idx].hist_set, hist_set);
    } else {
        seg[idx].is_set = true;
        seg[idx].hist_set = hist_set;
    }
}

void push_down(int idx) {
    apply_add(idx * 2, seg[idx].add_val, seg[idx].hist_add);
    apply_add(idx * 2 + 1, seg[idx].add_val, seg[idx].hist_add);
    seg[idx].add_val = seg[idx].hist_add = 0;
    
    if (seg[idx].is_set) {
        apply_set(idx * 2, seg[idx].set_val, seg[idx].hist_set);
        apply_set(idx * 2 + 1, seg[idx].set_val, seg[idx].hist_set);
        seg[idx].is_set = false;
        seg[idx].set_val = seg[idx].hist_set = 0;
    }
}

Maximum Subarray Sum with Unique Elements

When querying the maximum subarray sum where each distinct value is counted only once, an offline sweep-line approach proves effective. Queries are sorted by their right boundary. As the right boundary extends, the segment tree maintains the prefix sums of elements within specific intervals, while also tracking the historical maximum prefix sum to handle cases where the optimal left boundary is not the current right boundary.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100005;

struct Node {
    ll cur_sum, hist_max, add_tag, hist_add_tag;
} st[MAXN * 4];

void push_down(int idx) {
    st[idx*2].hist_max = max(st[idx*2].hist_max, st[idx*2].cur_sum + st[idx].hist_add_tag);
    st[idx*2+1].hist_max = max(st[idx*2+1].hist_max, st[idx*2+1].cur_sum + st[idx].hist_add_tag);
    st[idx*2].hist_add_tag = max(st[idx*2].hist_add_tag, st[idx*2].add_tag + st[idx].hist_add_tag);
    st[idx*2+1].hist_add_tag = max(st[idx*2+1].hist_add_tag, st[idx*2+1].add_tag + st[idx].hist_add_tag);
    st[idx*2].cur_sum += st[idx].add_tag;
    st[idx*2+1].cur_sum += st[idx].add_tag;
    st[idx*2].add_tag += st[idx].add_tag;
    st[idx*2+1].add_tag += st[idx].add_tag;
    st[idx].add_tag = st[idx].hist_add_tag = 0;
}

Historical Dot Product Sum of Dual Arrays

For evaluating the sum of products of maximums across subsegments of two arrays, a combination of monotonic stacks and a segment tree with complex tagging is used. The segment tree tracks the sum of products (S), sum of the first array (Sa), sum of the second array (Sb), and the historical sum of products (Ans). The tags include increments for the arrays (DeltaA, DeltaB), update operation count (Upd), sum of historical DeltaA (Ha), sum of historical DeltaB (Hb), and sum of historical DeltaA * DeltaB (H).

The propagation logic for the historical sum is derived as:

Ans_child = Ans_child + S_child * Upd_par + Hb_par * Sa_child + Ha_par * Sb_child + H_par * Len_child

The auxiliary tags update as follows:

Ha_child = Ha_child + DeltaA_child * Upd_par + Ha_par

Hb_child = Hb_child + DeltaB_child * Upd_par + Hb_par

H_child = H_child + DeltaA_child * DeltaB_child * Upd_par + DeltaA_child * Hb_par + DeltaB_child * Ha_par + H_par

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int MAXN = 250005;

struct Tag {
    ull da, db, u, ha, hb, h;
};

struct Node {
    ull s, sa, sb, ans, len;
    Tag tag;
} seg[MAXN * 4];

void apply(int idx, Tag t) {
    seg[idx].ans += seg[idx].s * t.u + seg[idx].sa * t.hb + seg[idx].sb * t.ha + t.h * seg[idx].len;
    seg[idx].tag.h += seg[idx].tag.da * seg[idx].tag.db * t.u + seg[idx].tag.da * t.hb + seg[idx].tag.db * t.ha + t.h;
    seg[idx].tag.ha += seg[idx].tag.da * t.u + t.ha;
    seg[idx].tag.hb += seg[idx].tag.db * t.u + t.hb;
    seg[idx].s += seg[idx].sa * t.db + seg[idx].sb * t.da + t.da * t.db * seg[idx].len;
    seg[idx].sa += t.da * seg[idx].len;
    seg[idx].sb += t.db * seg[idx].len;
    seg[idx].tag.u += t.u;
    seg[idx].tag.da += t.da;
    seg[idx].tag.db += t.db;
}

void push_down(int idx) {
    apply(idx * 2, seg[idx].tag);
    apply(idx * 2 + 1, seg[idx].tag);
    seg[idx].tag = {0, 0, 0, 0, 0, 0};
}