IOI '18 - Meetings (60pts)

#include "meetings.h"
#include <stack>
#include <algorithm>

using namespace std;

const long long INF = 1e18;
const int N = 1e5 + 1, LG = 17 + 1;
long long pre[N], suf[N];
long long mn[LG][N]; // sparse table of mins over pre[x] + suf[x] in range
long long queryMN(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return min(mn[i][l], mn[i][r-p2+1]);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size(), N = H.size();
  vector<long long> C(Q);

  if (*max_element(H.begin(), H.end()) <= 20) {
    // Convert from zero-based to one-based
    H.insert(H.begin(), 0);
    for (int &x : L) ++x;
    for (int &x : R) ++x;

    // Precalculate next and previous of each value from each position
    vector<int> nxt[21], prv[21];
    for (int i = 0; i <= 20; ++i) {
      prv[i] = vector<int>(1+N+1, 0);
      nxt[i] = vector<int>(1+N+1, N+1);
    }
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= 20; ++j) prv[j][i] = prv[j][i-1];
      prv[H[i]][i] = i;
    }
    for (int i = N; i >= 1; --i) {
      for (int j = 1; j <= 20; ++j) nxt[j][i] = nxt[j][i+1];
      nxt[H[i]][i] = i;
    }

    // Precalculate number with each maximum on each prefix and suffix
    vector<int> cntMaxPrefix[21]{}, cntMaxSuffix[21]{};
    for (int i = 1; i <= 20; ++i) {
      cntMaxPrefix[i].resize(1+N+1);
      cntMaxSuffix[i].resize(1+N+1);
    }
    for (int i = 1; i <= N; ++i) {
      cntMaxPrefix[H[i]][i] = 1;
      for (int j = 1; j <= H[i]; ++j) cntMaxPrefix[H[i]][i] += cntMaxPrefix[j][i-1];
      for (int j = H[i]+1; j <= 20; ++j) cntMaxPrefix[j][i] = cntMaxPrefix[j][i-1];
    }
    for (int i = N; i >= 1; --i) {
      cntMaxSuffix[H[i]][i] = 1;
      for (int j = 1; j <= H[i]; ++j) cntMaxSuffix[H[i]][i] += cntMaxSuffix[j][i+1];
      for (int j = H[i]+1; j <= 20; ++j) cntMaxSuffix[j][i] = cntMaxSuffix[j][i+1];
    }

    // Precalculate costs on prefix and suffix
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= 20; ++j) {
        pre[i] += cntMaxPrefix[j][i] * j;
        suf[i] += cntMaxSuffix[j][i] * j;
      }
      suf[i] -= H[i]; // prefix includes this value itself, suffix does not
      mn[0][i] = pre[i] + suf[i];
    }

    // Create sparse table for minimums over range
    for (int j = 1, p2 = 1; j < LG; ++j, p2 <<= 1) {
      for (int i = 1; i <= N; ++i) {
        if (i+p2 > N) mn[j][i] = mn[j-1][i];
        else mn[j][i] = min(mn[j-1][i], mn[j-1][i+p2]);
      }
    }

    // Answer each query
    for (int q = 0; q < Q; ++q) {
      int l = L[q], r = R[q];
      // Take next of each value from left and previous of each value from right
      int soFar = r+1;
      vector<pair<int, int>> starts;
      for (int j = 20; j >= 1; --j) {
        if (nxt[j][l] >= soFar) continue;
        soFar = nxt[j][l];
        starts.emplace_back(nxt[j][l], j);
      }
      reverse(starts.begin(), starts.end());

      soFar = l-1;
      vector<pair<int, int>> ends;
      for (int j = 20; j >= 1; --j) {
        if (prv[j][r] <= soFar) continue;
        soFar = prv[j][r];
        ends.emplace_back(prv[j][r], j);
      }

      vector<pair<int, int>> endsRemade;
      for (int start = l, i = 0; i < (int)ends.size(); ++i) {
        endsRemade.emplace_back(start, ends[i].second);
        start = ends[i].first+1;
      }
      ends = endsRemade;

      vector<pair<int, int>> merged;
      for (int i = 0; i < (int)starts.size(); ++i) merged.emplace_back(starts[i].first, starts[i].second);
      for (int i = 0; i < (int)ends.size(); ++i) merged.emplace_back(ends[i].first, -ends[i].second);
      sort(merged.begin(), merged.end());


      C[q] = INF;
      for (int i = 0, curL = 0, curR = 0; i < (int)merged.size(); ++i) {
        if (merged[i].second > 0) { // Start
          curL = merged[i].second;
        } else { // End
          curR = -merged[i].second;
        }
        if (i+1 < (int)merged.size() && merged[i+1].first == merged[i].first) continue;
        int rangeL = merged[i].first, rangeR = r;
        if (i+1 < (int)merged.size()) rangeR = merged[i+1].first-1;

        // now calculate best answer in this range
        long long best = queryMN(rangeL, rangeR); // min over pre + suf
        // subtract before l and after r
        for (int j = 1; j <= 20; ++j) {
          best -= cntMaxPrefix[j][l-1] * max(j, curL);
          best -= cntMaxSuffix[j][r+1] * max(j, curR);
        }
        C[q] = min(C[q], best);
      }
    }
  } else {
    for (int q = 0; q < Q; ++q) {
      int l = L[q], r = R[q];
      vector<long long> ans(r-l+1);
      stack<int> st;

      // Find answer contributions from left
      st.push(l-1);
      long long sum = 0;
      for (int i = l; i <= r; ++i) {
        while (st.top() >= l && H[st.top()] <= H[i]) {
          int x = st.top();
          st.pop();
          sum += (long long)(x-st.top())*(H[i]-H[x]);
        }
        st.push(i);
        sum += H[i];
        ans[i-l] += sum;
      }
      while (!st.empty()) st.pop();

      // Find answer contributions from right
      st.push(r+1);
      sum = 0;
      for (int i = r; i >= l; --i) {
        while (st.top() <= r && H[st.top()] <= H[i]) {
          int x = st.top();
          st.pop();
          sum += (long long)(st.top()-x)*(H[i]-H[x]);
        }
        st.push(i);
        sum += H[i];
        ans[i-l] += sum;
      }
      while (!st.empty()) st.pop();

      // Choose best answer
      long long minCost = INF;
      for (int i = l; i <= r; ++i) {
        ans[i-l] -= H[i]; // counted from both sides
        minCost = min(minCost, ans[i-l]);
      }
      C[q] = minCost;
    }
  }
  return C;
}