ds/monotone/prefix_add_append_get_max.hpp

• View this file on GitHub
• Last update: 2024-11-14 21:00:22+09:00
• Include: #include "ds/monotone/prefix_add_append_get_max.hpp"
• Link: https://qoj.ac/contest/1472/problem/7905

Depends on

• ds/unionfind/unionfind.hpp

Code

#include "ds/unionfind/unionfind.hpp"

// prefix add / 末尾追加 / 全体 max
// https://qoj.ac/contest/1472/problem/7905
struct Prefix_Add_Append_Get_Max {
  int n;
  UnionFind uf;
  vc<pair<int, int>> range;
  vi dat;
  ll max;
  Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}

  void append(int i, ll x) {
    assert(i == len(dat) && i < n);
    range[i] = {i, i + 1};
    if (i == 0) {
      max = x;
      dat.eb(x);
      return;
    }
    if (x > max) {
      dat.eb(x - max);
      max = x;
      return;
    }
    dat.eb(0);
    merge(i);
    return;
  }

  void merge(int i) {
    int a = uf[i - 1], b = uf[i];
    assert(a != b);
    uf.merge(a, b);
    int c = uf[a];
    range[c].fi = range[a].fi, range[c].se = range[b].se;
  }

  // [0,i), +x
  void prefix_add(int i, ll x) {
    if (i == 0) return;
    assert(i <= len(dat) && x >= 0);
    dat[0] += x, max += x;
    while (x > 0) {
      auto [l, r] = range[uf[i]];
      int p = (l == i ? l : r);
      if (p == len(dat)) return;
      ll y = dat[p];
      ll z = min(x, y);
      dat[p] -= z, x -= z, max -= z;
      if (dat[p] == 0) {
        merge(p);
        continue;
      }
    }
  }

  ll get_max() { return max; }
};

#line 2 "ds/unionfind/unionfind.hpp"

struct UnionFind {
  int n, n_comp;
  vc<int> dat; // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) { return dat[x]; }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }

  vc<int> get_all() {
    vc<int> A(n);
    FOR(i, n) A[i] = (*this)[i];
    return A;
  }
};
#line 2 "ds/monotone/prefix_add_append_get_max.hpp"

// prefix add / 末尾追加 / 全体 max
// https://qoj.ac/contest/1472/problem/7905
struct Prefix_Add_Append_Get_Max {
  int n;
  UnionFind uf;
  vc<pair<int, int>> range;
  vi dat;
  ll max;
  Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}

  void append(int i, ll x) {
    assert(i == len(dat) && i < n);
    range[i] = {i, i + 1};
    if (i == 0) {
      max = x;
      dat.eb(x);
      return;
    }
    if (x > max) {
      dat.eb(x - max);
      max = x;
      return;
    }
    dat.eb(0);
    merge(i);
    return;
  }

  void merge(int i) {
    int a = uf[i - 1], b = uf[i];
    assert(a != b);
    uf.merge(a, b);
    int c = uf[a];
    range[c].fi = range[a].fi, range[c].se = range[b].se;
  }

  // [0,i), +x
  void prefix_add(int i, ll x) {
    if (i == 0) return;
    assert(i <= len(dat) && x >= 0);
    dat[0] += x, max += x;
    while (x > 0) {
      auto [l, r] = range[uf[i]];
      int p = (l == i ? l : r);
      if (p == len(dat)) return;
      ll y = dat[p];
      ll z = min(x, y);
      dat[p] -= z, x -= z, max -= z;
      if (dat[p] == 0) {
        merge(p);
        continue;
      }
    }
  }

  ll get_max() { return max; }
};

Back to top page