【推广】猫树

UnyieldingTrilobite · 2023-06-30 16:20:51 · 个人记录

去年二月搞的东西，后来发现有 bug（贡献重复计算）就被我藏了，今天和在机房友的交流中想起了这个东西，来翻修一下。特征是短。

感觉没必要写注释锕，那就整个 GSS 1 代码吧。

对边界的处理偏谨慎，否则应该会更好写一点。但总之现在这个东西已经相当好写了。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 9, L = 20;
struct msub {
  int mpr, msf, msb, sum;
  friend msub operator+(const msub& l, const msub& r) {
    msub ret;
    ret.mpr = max(l.mpr, l.sum + r.mpr);
    ret.msf = max(l.msf + r.sum, r.msf);
    ret.msb = max({l.msb, l.msf + r.mpr, r.msb});
    ret.sum = l.sum + r.sum;
    return ret;
  }
  msub() {}
  explicit msub(int x) { mpr = msf = msb = sum = x; }
} val[N], ct[L][N];
int n, m;
void build() {
  for (int h = 0, s = 1; s <= n; ++h, s <<= 1)
    for (int i = s; i <= n; i += s << 1) {
      ct[h][i - 1] = val[i - 1];
      for (int j = i - 1; j > i - s; --j) ct[h][j - 1] = val[j - 1] + ct[h][j];
      if (i == n) break;
      ct[h][i] = val[i];
      for (int j = i + 1; j < i + s && j < n; ++j)
        ct[h][j] = ct[h][j - 1] + val[j];
    }
}
msub query(int l, int r) {
  if (l == r) return val[l];
  int h = __builtin_ia32_bsrsi(l ^ r);
  return ct[h][l] + ct[h][r];
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 0, a; i < n; ++i) cin >> a, val[i] = msub(a);
  build();
  for (cin >> m; m; --m) {
    int l, r;
    cin >> l >> r;
    cout << query(l - 1, r - 1).msb << '\n';
  }
  return cout << flush, 0;
}