Codeforces 455E - Function

Problem Statement:
http://codeforces.com/contest/455/problem/E

Summary:
Given a function f(i, j) = min (f(i-1, j), f(i-1, j-1)) + a[j], where f(1, j) = a[j], and m queries (m <= 10^5) in the form (i, j), compute f(i, j) of each queries.



Solution:
This problem employs similar technique as in problem http://codeforces.com/contest/678/problem/F, as one of the contestants pointed out. The interesting part is that at first glance the problem feels more like a DP problem than a convex hull problem.

Play with the recursive function a little bit, and you will see that the function actually tries to find the minimum over all possible a[j]*c[j] + a[j-1]*c[j-1] + ... + a[j-i+1] * c[j-i+1] where each c[k] >= 1, and sum of c[k] = i. Drawing a tree out of the recursive function will show you this relationship clearly.

The key observation is that, if we fix the segment [k, j], such that we must use elements a[k], a[k+1], ..., a[j] and try to minimise a[k] * c[k] + ... + a[j] * c[j],  the strategy is naturally to find a[m] the smallest element in a[k..j] and set c[m] the highest possible values, while the rest of c[i] is set to 1, for all i in [k, j] excluding m. If we already computed a prefix sum of a[1..n], we can compute the minimum sum in segment [k...j] as sum[j] - sum[k] + a[m] * (i - (j - k)).

Furthermore, if the smallest element c[m] is not c[k], then we know that the minimum value obtained in segment [m...j] is smaller than that of [k...j]. Hence we can reformulate f(i, j) as follows:
f(i, j) = min{ sum[j] - sum[k] + a[k] * (i - (j-k)) } for all k in [j-i+1, j].
Since sum[j] does not depend on k, we can take it out of the min{}, and by regrouping the elements with term k together we get
f(i, j) = sum[j] + min{ a[k] * (i-j) + a[k]*k - sum[k] } over k.
By setting G(k, X) = m*X + c where m = a[k] and c = a[k]*k - sum[k], we can represent f(i, j) as finding the minimum intersection between lines G(k, X) for all k in [j-i+1, j] and X = (i-j). Now this is similar to problem 678F!

By applying the convex-hull construction over linear functions, we can solve the above problem. Construction of the convex-hull is simply done by first sorting the lines in terms of decreasing gradient m (and decreasing c to break ties), and iterating over the lines by maintaining a stack of lines S. For each new line L to consider, we see if the intersection between L and S.top() is ahead of (or larger than) the intersection between top two lines on S. If so, we can add L to S. Otherwise pop S once and repeat. In the end S will contain the desired convex hull. Then we can binary search the convex hull for each value of X in O(lg S) to compute the minimum of intersection between x = X and all the original lines.

The problem is slightly more complicated in the sense that for each query (i, j), we must only consider the lines in [j-i+1, j]. Turns out, by marrying segment tree with the above convex hull construction, we can build a segment tree of convex hulls in O(N lg N) time, and we can answer the queries in O(lg N) * O(lg N) time (since for each query, we must traverse the segment tree in O(lg N) time to find the desired segments, and on each segment we perform a binary search over the convex hull in O(lg N) time). The construction of the segment tree can be done in O(N lg N) time by sorting the lines once before segment tree construction, and performing a "bucketing" over lines currently considered in segment [L, R] by grouping the lines into segment [L, M] and [M+1, R] while maintaining the relative ordering of elements in each bucket (similar to the idea of radix sort / bucketing sorted elements such that the elements in each bucket is still sorted).

Implementation:

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int64_t MAX_INF = 1LL<<61;
class Line {
public:
  Line(int64_t m, int64_t c, int id) : m_(m), c_(c), id_(id) {}
  bool IsParallel(const Line& other) {
    return other.m_ == m_;
  }
  bool IsIncreasing(const Line& line_1, const Line& line_2) {
    return (line_1.c_-c_)*(line_1.m_-line_2.m_) <
           (line_2.c_-line_1.c_)*(m_-line_1.m_);
  }
  int64_t At(int64_t x) {
    return x*m_ + c_;
  }
  int64_t m_;
  int64_t c_;
  int id_;
};
bool IsOverIntersection(int64_t x, const Line& line_1, const Line& line_2) {
  return line_2.c_-line_1.c_ < (line_1.m_-line_2.m_)*x;
}
class ConvexHull {
public:
  void Construct(const vector<Line>& lines) {
    for (int i=0;i<lines.size();++i){
      while (!hull_.empty()) {
        if (hull_.back().IsParallel(lines[i])) {
          hull_.pop_back();
          continue;
        }
        if (hull_.size() > 1) {
          Line& line_1 = hull_[hull_.size()-2];
          Line& line_2 = hull_.back();
          if (!line_1.IsIncreasing(line_2, lines[i])) {
            hull_.pop_back();
            continue;
          }
        }
        break;
      }
      hull_.push_back(lines[i]);
    }
  }
  int64_t BinarySearch(int64_t x) {
    int lo=0, hi=hull_.size()-1, mid;
    while (lo <= hi) {
      mid = (lo+hi)/2;
      if (mid+1 < hull_.size()) {
        if (IsOverIntersection(x, hull_[mid], hull_[mid+1])) {
          lo = mid+1;
        } else {
          hi = mid-1;
        }
      } else break;
    }
    return hull_[lo].At(x);
  }
  vector<Line> hull_;
};
class SegmentTree {
public:
  struct Node {
    int L; int R; int p;
  };
  void Init(const vector<Line>& lines) {
    // 'lines' is sorted in (m, c) order.
    n_ = lines.size();
    tree.clear();
    tree.resize(4*n_);
    Build(lines, 1, n_, 1);
  }
  void Build(const vector<Line>& lines, int L, int R, int p) {
    if (L>R) return;
    tree[p].Construct(lines);
    if (L==R) return;
    int M = (L+R)/2;
    vector<Line> left_lines, right_lines;
    for (int i=0;i<lines.size();++i){
      if (lines[i].id_ <= M) {
        left_lines.push_back(lines[i]);
      } else {
        right_lines.push_back(lines[i]);
      }
    }
    Build(left_lines, L, M, 2*p);
    Build(right_lines, M+1, R, 2*p+1);
  }
  int64_t Rmq(int S, int T, int64_t x) {
    int64_t ret = MAX_INF;
    queue<Node> nodes;
    nodes.push({1, n_, 1});
    while (!nodes.empty()) {
      Node t = nodes.front();
      nodes.pop();
      if (T < t.L || t.R < S) {
        continue;
      }
      if (S <= t.L && t.R <= T) {
        ret = min(ret, tree[t.p].BinarySearch(x));
        continue;
      }
      int M = (t.L+t.R)/2;
      nodes.push({t.L, M, 2*t.p});
      nodes.push({M+1, t.R, 2*t.p+1});
    }
    return ret;
  }
  int n_;
  vector<ConvexHull> tree;
};
int n, m;
int a[100010];
int64_t sum[100010];
int main(){
  scanf("%d",&n);
  vector<Line> lines;
  for(int i=1;i<=n;++i){
    scanf("%d",&a[i]);
    sum[i] = a[i];
    if (i>1) sum[i] += sum[i-1];
    lines.push_back({a[i], 1LL*a[i]*i-sum[i], i});
  }
  sort(lines.begin(), lines.end(),
      [](const Line& line_1, const Line& line_2) {
        if (line_1.m_ == line_2.m_) return line_1.c_ > line_2.c_;
        return line_1.m_ > line_2.m_;
      });
  SegmentTree tree;
  tree.Init(lines);
  scanf("%d",&m);
  for (int q=0;q<m;++q){
    int i,j;
    scanf("%d%d",&i, &j);
    cout << sum[j] + tree.Rmq(min(max(0,j-i+1), n), j, i-j) << endl;;
  }
  return 0;
}