ARC066_F Contest with Drinks Hard

うくなので2

atcoder.jp

解法

まずドリンクがない場合はDPをCHTを使っていつもの高速化することで解くことが可能.

ドリンクがある場合を考える. あるドリンクについて, それを必ず使う場合と必ず使わない場合の最大値がわかればよい.

必ず使わない場合は簡単で, prefix と suffix 方向からDPしてそこを抜いた場合の和が答え.

必ず使う場合はその答えを , ドリンクを飲んだときのその問題を解く時間を とすると となる. をそれぞれの について知りたい.

分割統治をします(えぇ...)

ある問題の区間 があって, 中心を とする. 区間 内の問題 について, 問題 を必ず解くときの区間に問題 を含むか含まないかで場合分けをする.

問題 を含まないときは で分割して同じ問題を解けば良い.

問題 を含むときを考える. を仮定する(逆側も同様なので). と と一緒に問題を解くときは, より右側 を満たす をその区間の右端としたときについてのスコアの最大が最大スコアである.

より左側のどこか からのprefixのDPと右側 のsuffixのDPとその区間 のスコアとの総和の最大値を求めたい感じになり, CHTを使えば分かる(重心分解と同じ考え方?).

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const int64 infll = (1LL << 61) - 1;

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T >
struct LiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    inline T get(T x) const { return a * x + b; }

    inline bool over(const Line &b, const T &x) const {
      return get(x) > b.get(x);
    }
  };

  vector< T > xs;
  vector< Line > seg;
  int sz;

  LiChaoTree(const vector< T > &x, T INF) : xs(x) {
    sz = 1;
    while(sz < xs.size()) sz <<= 1;
    while(xs.size() < sz) xs.push_back(xs.back() + 1);
    seg.assign(2 * sz - 1, Line(0, INF));
  }

  void update(Line &x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
    if(malta) swap(seg[k], x);
    if(l + 1 >= r) return;
    else if(latte != malta) update(x, 2 * k + 1, l, mid);
    else update(x, 2 * k + 2, mid, r);
  }

  void update(T a, T b) { // ax+b
    Line l(a, b);
    update(l, 0, 0, sz);
  }

  T query(int k) { // xs[k]
    const T x = xs[k];
    k += sz - 1;
    T ret = seg[k].get(x);
    while(k > 0) {
      k = (k - 1) >> 1;
      ret = max(ret, seg[k].get(x));
    }
    return ret;
  }
};

vector< int64 > solve(vector< int64 > &V) {
  int N = (int) V.size();
  vector< int64 > S(N + 1);
  for(int i = 0; i < N; i++) S[i + 1] = S[i] + V[i];
  for(int i = 0; i <= N; i++) S[i] *= 2;
  vector< int64 > dp(N + 1);
  vector< int64 > v(N);
  iota(begin(v), end(v), 1);
  LiChaoTree< int64 > cht(v, -infll);
  cht.update(0, 0);
  for(int i = 1; i <= N; i++) {
    chmax(dp[i], dp[i - 1]);
    chmax(dp[i], 1LL * i * (i + 1) - S[i] + cht.query(i - 1));
    cht.update(-2 * i, dp[i] + 1LL * i * (i - 1) + S[i]);
  }
  return dp;
}


int64 N, M;
vector< int64 > prefix, suffix;
vector< int64 > S, tap;

void rec(int l, int r) {
  if(l >= r) return;

  int m = (l + r) / 2;

  {
    vector< int64 > v;
    for(int i = r; i > m; i--) v.emplace_back(i);
    sort(begin(v), end(v));
    LiChaoTree< int64 > cht(v, -infll);
    for(int i = l; i <= m; i++) {
      cht.update(-2 * i, prefix[i] + 1LL * i * (i - 1) + S[i]);
    }
    int64 mx = -infll;
    for(int i = r; i > m; i--) {
      chmax(mx, cht.query(lower_bound(begin(v), end(v), i) - begin(v)) + 1LL * i * (i + 1) - S[i] + suffix[i]);
      chmax(tap[i - 1], mx);
    }
  }


  {
    vector< int64 > v;
    for(int i = l; i <= m; i++) v.emplace_back(-i);
    reverse(begin(v), end(v));
    LiChaoTree< int64 > cht(v, -infll);
    for(int i = m + 1; i <= r; i++) {
      cht.update(2 * i, 1LL * i * (i + 1) - S[i] + suffix[i]);
    }
    int64 mx = -infll;
    for(int i = l; i <= m; i++) {
      chmax(mx, cht.query(lower_bound(begin(v), end(v), -i) - begin(v)) + 1LL * i * (i - 1) + S[i] + prefix[i]);
      chmax(tap[i], mx);
    }
  }

  rec(l, m);
  rec(m + 1, r);
}


int main() {
  cin >> N;
  vector< int64 > T(N);
  cin >> T;
  cin >> M;

  prefix = solve(T);
  reverse(begin(T), end(T));
  suffix = solve(T);
  reverse(begin(T), end(T));
  reverse(begin(suffix), end(suffix));
  S.resize(N + 1);
  for(int i = 0; i < N; i++) S[i + 1] = S[i] + T[i];
  for(int i = 0; i <= N; i++) S[i] *= 2;
  tap.assign(N, -infll);
  rec(0, N);
  while(M--) {
    int64 P, X;
    cin >> P >> X;
    --P;
    X *= 2;
    cout << max(prefix[P] + suffix[P + 1], tap[P] + T[P] * 2 - X) / 2 << endl;
  }
}