Submission #1046626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046626		juicy	Fish 2 (JOI22_fish2)	C++17	100 / 100	1974 ms	9576 KiB

fish2

// https://oj.uz/submission/937840
// https://codeforces.com/blog/entry/101003?#comment-898608
// https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest4/fish2-review.pdf

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, inf = 1e9 + 7;

int n, q;
int a[N], ma[4 * N],  lz[4 * N];
array<int, 2> s[4 * N];

array<int, 2> operator + (const array<int, 2> &lt, const array<int, 2> &rt) {
  array<int, 2> res{};
  res[0] = min(lt[0], rt[0]);
  if (res[0] == lt[0]) {
    res[1] += lt[1];
  }
  if (res[0] == rt[0]) {
    res[1] += rt[1];
  }
  return res;
}

namespace ft {
  long long ft[N];

  void upd(int i, int x) {
    for (; i <= n; i += i & -i) {
      ft[i] += x;
    }
  }

  long long qry(int i) {
    long long res = 0;
    for (; i; i -= i & -i) {
      res += ft[i];
    }
    return res;
  }

  long long qry(int l, int r) {
    return qry(r) - qry(l - 1);
  }
}

void upd(int i, int x, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    ma[id] = x;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, id * 2, l, md);
  } else {
    upd(i, x, id * 2 + 1, md + 1, r);
  }
  ma[id] = max(ma[id * 2], ma[id * 2 + 1]);
}

int walklt(int i, long long k, int id = 1, int l = 1, int r = n) {
  if (l >= i || ma[id] <= k) {
    return 0;
  }
  if (l == r) {
    return l;
  }
  int md = (l + r) / 2;
  auto res = walklt(i, k, id * 2 + 1, md + 1, r);
  return res == 0 ? walklt(i, k, id * 2, l, md) : res;
}

int walkrt(int i, long long k, int id = 1, int l = 1, int r = n) {
  if (r <= i || ma[id] <= k) {
    return n + 1;
  }
  if (l == r) {
    return l;
  }
  int md = (l + r) / 2;
  auto res = walkrt(i, k, id * 2, l, md);
  return res == n + 1 ? walkrt(i, k, id * 2 + 1, md + 1, r) : res;
}

void app(int id, int x) {
  s[id][0] += x;
  lz[id] += x;
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {0, 1};
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  s[id] = s[id * 2] + s[id * 2 + 1];
}

void add(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (u <= md) {
    add(u, v, x, id * 2, l, md);
  }
  if (md < v) {
    add(u, v, x, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}

array<int, 2> get(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return s[id];
  }
  psh(id);
  int md = (l + r) / 2;
  if (v <= md) {
    return get(u, v, id * 2, l, md);
  }
  if (md < u) {
    return get(u, v, id * 2 + 1, md + 1, r);
  }
  return get(u, v, id * 2, l, md) + get(u, v, id * 2 + 1, md + 1, r); 
}

bool check(int l, int r, long long &sum) {
  sum = ft::qry(l + 1, r - 1);
  return sum < min(a[l], a[r]);
}

vector<array<int, 2>> getcands(int p) {
  if (p == 0 || p == n + 1) {
    return {};
  }
  int l = p, r = p;
  long long cur = a[p];
  vector<array<int, 2>> cands;
  while (1) {
    int s = walklt(l, cur), e = walkrt(r, cur);
    if (s == 0 && e == n + 1) {
      break;
    }
    if (check(s, e, cur)) {
      cands.push_back({s + 1, e - 1});
    }
    if (a[s] <= a[e]) {
      l = s;
    } else {
      r = e;
    }
  }
  return cands; 
}

void up(int i, int x) {
  auto cands = getcands(i);
  auto lt = getcands(i - 1);
  auto rt = getcands(i + 1);
  for (auto [l, r] : cands) {
    add(l, r, x);
  }
  for (auto [l, r] : lt) {
    if (r == i - 1) {
      add(l, r, x);
    }
  }
  for (auto [l, r] : rt) {
    if (l == i + 1) {
      add(l, r, x);
    }
  }
}

void chg(int i, int x) {
  up(i, -1);
  ft::upd(i, x - a[i]);
  a[i] = x;
  upd(i, x);
  up(i, 1);
}

int findlt(int l, int r) {
  int res = l, p = l;
  long long cur = a[l];
  while (1) {
    p = walkrt(p, cur);
    if (p > r) {
      break;
    }
    cur = ft::qry(l, p - 1);
    if (cur < a[p]) {
      res = p;
    }
  }
  return res;
}

int findrt(int l, int r) {
  int res = r, p = r;
  long long cur = a[r];
  while (1) {
    p = walklt(p, cur);
    if (p < l) {
      break;
    }
    cur = ft::qry(p + 1, r);
    if (cur < a[p]) {
      res = p;
    }
  }
  return res;
}

int qry(int l, int r) {
  int s = findlt(l, r), e = findrt(l, r);
  if (s > e) {
    return 0;
  }
  return get(s, e)[1];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  bld();
  a[0] = a[n + 1] = inf;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x;
    chg(i, x);
  }
  cin >> q;
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int x, y; cin >> x >> y;
      chg(x, y);
    } else {
      int s, e; cin >> s >> e;
      cout << qry(s, e) << "\n";
    }
  }
  return 0;
}

// an interesting observation that I haven't taken advantage of
// A >= sum(x - 1) - sum(l - 1)
// -> A - sum(x - 1) >= -sum(l - 1) (can be solved with lazy segtree)

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17