Maximum subarray sum with update

// I can't tell you what it really is,
// I can only tell you what it feels like.
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define rep(i,a,n) for (int i = a; i <= n; ++i)
#define all(v)  v.begin(), v.end()
#define pb push_back
#define E cout << '\n'

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int a[N];

struct node {
  int mxPreSum, mxSuffSum, totalSum, maxSubSum;
  node() {
    mxSuffSum = mxPreSum = 0;
    totalSum = 0, maxSubSum = 0;
  }
  node(int a,int b,int c,int d) {
    mxPreSum = a, mxSuffSum = b;
    totalSum = c, maxSubSum = d;
  }

}tree[N<<2];

inline node merge(node lc, node rc) {
    node now;
    now.mxPreSum = max(lc.mxPreSum, lc.totalSum+rc.mxPreSum);
    now.mxSuffSum = max(rc.mxSuffSum, rc.totalSum+lc.mxSuffSum);
    now.totalSum = lc.totalSum+rc.totalSum;
    now.maxSubSum = max({lc.maxSubSum,rc.maxSubSum,lc.mxSuffSum+rc.mxPreSum});
    return now;
  }

void build(int l, int r, int x) {
  if (l == r) {
    tree[x] = node(a[l],a[l],a[l],a[l]);
    return;
  }
  int mid=l+r>>1LL, lc=mid+mid, rc=lc|1;
  build(l,mid,lc);
  build(mid+1,r,rc);
  tree[x]=merge(tree[lc],tree[rc]);
}

void update(int l, int r, int pos, int val, int x) {
  if (pos < l || pos > r)
    return;
  if (l == r && pos == l) {
    tree[x] = node(val,val,val,val);
    return;
  }
  int mid=l+r>>1LL, lc=mid+mid, rc=lc|1;
  update(l,mid,pos,val,lc);
  update(mid+1,r,pos,val,rc);
  tree[x] = merge(tree[lc], tree[rc]);
}

inline void solve() {
   int n, k, ans = 1e8;
   cin >> n >> k;
   rep(i,1,n) {
    cin >> a[i];
   }
   int lo,hi,mid;
   build(1,n,1);
   rep(i,1,n) {
    lo = -1e8, hi = 1e8;
    while (lo <= hi) {
      mid = lo + hi>>1LL;
      update(1,n,i,mid,1);
      if (tree[1].maxSubSum < k)
        lo = mid+1;
      else
        hi = mid-1;
    }
    update(1,n,i,a[i],1);
    ans = min(ans, hi+1);
   }
   cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  //cin >> t; while(t--)
  solve();
  return 0;
}
Statistics
Difficulty: Medium

Time Complexity:
N(logN)log(2e8)

Required Knowledge: Segment Trees, Binary Search

Publish Date: Oct 05 2019