[HackerEarth] Tom and Jerry

Problem  : Tom and Jerry
Category : Data Structure
Algorithm: Maximum Subarray sum using Lazy Segment Tree
Contest  : HackerEarth July Easy 2023

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 2E5 + 5;
const int INF = -1E17;
 
struct Node {
    bool lazy;
    int lazyValue;
    int maxSubarrySum;
    int subarrySum;
    int maxPrefix;
    int maxSuffix;
 
    Node(bool lazy = 0, int lazyValue = 0, int maxSubarrySum = INF, int subarrySum = INF, int maxPrefix = INF, int maxSuffix = INF)
        : lazy(lazy), lazyValue(lazyValue), maxSubarrySum(maxSubarrySum), subarrySum(subarrySum), maxPrefix(maxPrefix), maxSuffix(maxSuffix) {}
 
    void assignLeaf(int val) {
        lazy = 0;
        lazyValue = 0;
        maxSubarrySum = val;
        maxPrefix = val;
        subarrySum = val;
        maxSuffix = val;
    }
 
    void marge(const Node &lchildNode, const Node &rchildNode) {
        maxSubarrySum = max({
                                lchildNode.maxSubarrySum,
                                rchildNode.maxSubarrySum,
                                lchildNode.maxSuffix + rchildNode.maxPrefix
                            });
        subarrySum = lchildNode.subarrySum + rchildNode.subarrySum;
        maxPrefix = max({
                            lchildNode.maxPrefix,
                            lchildNode.subarrySum + rchildNode.maxPrefix
                        });
        maxSuffix = max({
                            lchildNode.maxSuffix + rchildNode.subarrySum,
                            rchildNode.maxSuffix
                        });
    }
 
    int getMax() {
        return max({
                        maxSubarrySum,
                        subarrySum,
                        maxPrefix,
                        maxSuffix
                   });
    }
};
 
Node Tree[maxn * 4];
int n;
int q;
int arr[maxn];
 
#define lchild  node * 2
#define rchild  node * 2 + 1
#define mid     (a + b) / 2
 
void push(int node, int a, int b) {
    if (Tree[node].lazy == 0) {
        return;
    }
    Node &curNode = Tree[node];
    curNode.maxSubarrySum = (b - a + 1) * curNode.lazyValue;
    curNode.subarrySum = (b - a + 1) * curNode.lazyValue;
    curNode.maxPrefix = (b - a + 1) * curNode.lazyValue;
    curNode.maxSuffix = (b - a + 1) * curNode.lazyValue;
    if (curNode.lazyValue < 0) {
        curNode.maxSubarrySum = curNode.lazyValue;
        curNode.maxPrefix = curNode.lazyValue;
        curNode.maxSuffix = curNode.lazyValue;
    }
    if (a < b) {
        Tree[lchild].lazy = Tree[rchild].lazy = 1;
        Tree[lchild].lazyValue = Tree[rchild].lazyValue = curNode.lazyValue;
    }
    curNode.lazy = 0;
    curNode.lazyValue = 0;
}
 
 
void build(int node, int a, int b) {
    if (a == b) {
        Tree[node].assignLeaf(arr[a]);
        return;
    }
    build(lchild, a, mid);
    build(rchild, mid + 1, b);
    Tree[node].marge(Tree[lchild], Tree[rchild]);
}
 
void update(int node, int a, int b, int i, int j, int val) {
    push(node, a, b);
    if (a > b or a > j or b < i) {
        return;
    }
    if (a >= i and b <= j) {
        Tree[node].lazy = 1;
        Tree[node].lazyValue = val;
        push(node, a, b);
        return;
    }
    update(lchild, a, mid, i, j, val);
    update(rchild, mid + 1, b, i, j, val);
    Tree[node].marge(Tree[lchild], Tree[rchild]);
}
 
Node query(int node, int a, int b, int i, int j) {
    push(node, a, b);
    if (a > b or a > j or b < i) {
        return Node();
    }
    if (a >= i and b <= j) {
        return Tree[node];
    }
    Node p = query(lchild, a, mid, i, j);
    Node q = query(rchild, mid + 1, b, i, j);
    Node res;
    res.marge(p, q);
    return res;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    while (tc--) {
        for (int i = 0; i < maxn * 4; i++) {
            Tree[i] = Node();
        }
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        build(1, 1, n);
        cin >> q;
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                int l, r, val;
                cin >> l >> r >> val;
                update(1, 1, n, l, r, val);
            } else {
                int l, r;
                cin >> l >> r;
                Node res = query(1, 1, n, l, r);
                cout << res.getMax() << endl;
            }
        }
    }

}