Kinetic SegTree: Range increment, query maxsum range

#include <cstdio>

#include <algorithm>
#include <functional>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Line {
  int k;
  ll b;

  Line() : k(0), b(0) {}

  Line(ll b) : k(0), b(b) {}

  Line(int k, ll b) : k(k), b(b) {}

  ll operator()(int x) const { return k * (ll)x + b; }

  Line operator+(const Line& rhs) const { return Line(k + rhs.k, b + rhs.b); }
  Line operator-() const { return Line(-k, -b); }
  Line operator-(const Line& rhs) const { return *this + (-rhs); }

  Line inc(ll x) const { return Line(k, b + k * (ll)x); }
};

struct Node {
  ll sum, x;
  Line lmax, rmax, tmax;
  int l, r;
  ll cert;
  Node *ls, *rs;

  int len() const { return r - l + 1; }

  ll gsum() const { return sum + x * len(); }

  ll gcert() const { return cert - x; }

  Line gsumLine() const { return Line(len(), sum).inc(x); }

#define DEFGET(V) Line g##V() const { return V.inc(x); }

  DEFGET(lmax)
  DEFGET(rmax)
  DEFGET(tmax)
};

struct Tmp {
  ll sum, lmax, rmax, tmax;

  Tmp(ll sum, ll lmax, ll rmax, ll tmax) : sum(sum), lmax(lmax), rmax(rmax), tmax(tmax) {}

  friend Tmp unite(const Tmp& lhs, const Tmp& rhs) {
    return Tmp(lhs.sum + rhs.sum,
               max(lhs.lmax, lhs.sum + rhs.lmax),
               max(rhs.rmax, rhs.sum + lhs.rmax),
               max({lhs.tmax, rhs.tmax, lhs.rmax + rhs.lmax}));
  }
};

const ll INF = 1LL << 60;

ll compete(const Line& delt, ll x) {
  if (delt(x) > 0) {
    if (delt.k < 0) {
      ll chp = delt.b / -delt.k + 1;
      if (chp <= INF)
        return chp;
    }
  } else if (delt(x) < 0) {
    if (delt.k > 0) {
      ll chp = (-delt.b) / delt.k + 1;
      if (chp <= INF)
        return chp;
    }
  } else if (delt.k)
    return x + 1;
  return INF;
}

void chkmin(ll& x, ll y) {
  if (x > y) x = y;
}

Line max(const Line& lhs, const Line& rhs, ll x) { return lhs(x) < rhs(x) ? rhs : lhs; }

struct KineticTournament {
  Node* segTree;

  Node* build(int l, int r);

  KineticTournament(int n) : segTree(build(1, n)) {}

  void updateLeaf(Node* o) {
    if (o->sum + o->x > 0) {
      o->lmax = o->rmax = o->tmax = Line(1, o->sum);
      o->cert = INF;
    } else {
      o->lmax = o->rmax = o->tmax = Line(0, 0);
      o->cert = compete(Line(-1, -o->sum), o->x);
    }
  }

  void update(Node* o) {
    o->sum = o->ls->gsum() + o->rs->gsum();
    o->lmax = max(o->ls->glmax(), o->ls->gsumLine() + o->rs->glmax(), o->x);
    o->rmax = max(o->rs->grmax(), o->rs->gsumLine() + o->ls->grmax(), o->x);
    o->tmax = max(max(o->ls->gtmax(), o->rs->gtmax(), o->x), o->ls->grmax() + o->rs->glmax(), o->x);
    o->cert = min({compete(o->lmax - o->ls->glmax(), o->x), compete(o->lmax - o->ls->gsumLine() - o->rs->glmax(), o->x),
                   compete(o->rmax - o->rs->grmax(), o->x), compete(o->rmax - o->rs->gsumLine() - o->ls->grmax(), o->x),
                   compete(o->tmax - o->ls->gtmax(), o->x), compete(o->tmax - o->rs->gtmax(), o->x),
                   compete(o->tmax - o->ls->grmax() - o->rs->glmax(), o->x), o->ls->gcert(), o->rs->gcert()});
  }

  void pushDown(Node* o) {
    if (o->x) {
      o->ls->x += o->x;
      o->rs->x += o->x;
      o->x = 0;
    }
  }

  void changeTraj(Node* o) {
    if (o->cert > o->x) return;
    if (o->l == o->r)
      return updateLeaf(o);
    pushDown(o);
    changeTraj(o->ls);
    changeTraj(o->rs);
    update(o);
  }

  void increase(Node* o, int l, int r, int x) {
    if (o->l == l && o->r == r) {
      o->x += x;
      return changeTraj(o);
    }
    pushDown(o);
    if (r <= o->ls->r)
      increase(o->ls, l, r, x);
    else if (l >= o->rs->l)
      increase(o->rs, l, r, x);
    else {
      increase(o->ls, l, o->ls->r, x);
      increase(o->rs, o->rs->l, r, x);
    }
    update(o);
  }

  void increase(int l, int r, int x) {
    increase(segTree, l, r, x);
  }

  Tmp qry(Node* o, int l, int r) {
    if (o->l == l && o->r == r)
      return Tmp(o->gsum(), o->lmax(o->x), o->rmax(o->x), o->tmax(o->x));
    pushDown(o);
    Tmp ret(0, 0, 0, 0);
    if (r <= o->ls->r)
      ret = qry(o->ls, l, r);
    else if (l >= o->rs->l)
        ret = qry(o->rs, l, r);
    else
      ret = unite(qry(o->ls, l, o->ls->r), qry(o->rs, o->rs->l, r));
    update(o);
    return ret;
  }

  ll qry(int l, int r) {
    return qry(segTree, l, r).tmax;
  }
};

const int N = 100010;

int n, m;
int a[N];

Node* KineticTournament::build(int l, int r) {
  static Node pool[N * 2], *top = pool;
  Node* p = top++;
  p->l = l;
  p->r = r;
  if (l == r) {
    p->sum = a[l];
    updateLeaf(p);
    return p;
  }
  int mid = (l + r) >> 1;
  p->ls = build(l, mid);
  p->rs = build(mid + 1, r);
  update(p);
  return p;
}

int main() {
//  freopen("test.in", "r", stdin);
//  freopen("test.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  KineticTournament kt(n);
  while (m--) {
    int opt, l, r;
    scanf("%d%d%d", &opt, &l, &r);
    if (opt == 1) {
      int x;
      scanf("%d", &x);
      if (x)
        kt.increase(l, r, x);
    } else
      printf("%lld\n", kt.qry(l, r));
  }
  return 0;
}