cf671e/soj809 贪心/二分探索/神仙

· · 个人记录

题目链接：

https://codeforces.ml/contest/671/problem/E

本题的思路不是我想出来的。。但是思路的发明者lk在最后出现了一些漏洞，并不能通过所有的测试点。所以我在他的基础上进行修正，以及证明复杂度是O(nlogn)的。

以下会先稍加修改基本完全复制他（lk）的博客。

https://qaq-am.com/CF671E/

题解

首先考虑没有k限制的情况（或者说加完之后）如何判断l,r是否可以办比赛。

将题意中的g_i用a_i表示，w_i用b_i表示。

设f_i=f_{i-1}+(a_{i-1}-b_{i-1}),g_i=g_{i-1}+b_{i-1}-a_i。

那么l,r可以办比赛当且仅当

$

那么考虑有k限制的情况。

如果a_i+=x，那么对于i\lt j,f_j=f_j+x,对于i\le j,g_j=g_j-x。

从n到1枚举l，设单调栈为f_l\gt f_{x_1}\gt f_{x_2}\gt f_{x_3}\ldots(l\lt x_1\lt x_2\lt x_3\ldots)。

那么为了l到r单向的比赛满足条件，肯定是a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}对于i升序一个一个执行直到l能到r，其中x_0=l

接下来考虑r到l的单向的比赛。

设h_i为做完a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}后的g_i，此处的h_i在线段树上维护，方法是后缀加。

显然k剩下的增加都要给a_r，那么r能单向到l当且仅当g_r-k\leq h_i,l\le i\lt r。

如果对于i\le l定义h_i=\infty，那么就是

g_r-k\leq h_i,i\lt r$ 条件 $(1)

可以在单调栈二分出r的上界，然后在线段树上二分得到最大可行r。

考虑我在线段树上二分查询的过程

int qry(int l, int r, int p, int id, ll x) {
  if (r - l == 1) return l;
  pd(id);
  int mid = (l + r) >> 1; ll to = min(x, dat[2 * id + 1]);
  if (mid <= p && to >= mn[2 * id + 2] - k) {
    int ans = qry(mid, r, p, 2 * id + 2, to);
    if (ans >= 0) return ans;
  }
  if (mn[2 * id + 1] - k <= x) return qry(l, mid, p, 2 * id + 1, x);
  return -1;
}

表示我当前在线段树上访问的区间是[l,r)，id是当前节点编号，p表示从左往右单向考虑时二分出的r的最大值，x表示\min\limits _{1\leq i < l} h_i，该区间的mn_{id}=\min\limits _{l\leq i < r} g_i,dat_{id}=\min\limits _{l\leq i < r} h_i。进入这个区间时，必须满足mn_{id}-k\leq x，否则不会进入。

结论：当mn_{id}-k\leq x成立的时候，并且这个区间的g最小值所在点y满足y\leq p时，这个区间一定成立，[l,y]一定是一个合法解。

证明：我们加油的地方所在的区间一定在[l,y]，所以最后一定引起h_y=g_y-k。y这个点所在的区间本来就是g最小的点，而且他h还减的最多，它一定满足条件(1)：g_r-k\leq h_i,i\lt r。

我们对mid和p的关系进行分类讨论（此时我们保证p\geq l）。

若mid>p，右侧区间一定不会访问，递归到一个长度小一半的左区间，递归次数显然小于mid \leq p并且向右侧递归。没有解回溯。

若mid \geq p，先考虑往右走又没有合法解。此时，左侧区间一定不再受到p的限制，可以O(1)判断左侧是否有合法解。都没有解回溯。

因此我们的单次询问的操作是

$2.$如果操作$1$没有找到合法解，回溯。如果是从右端点来的，每次$O(1)$判断左端点是否有合法解。如果有，直接进入操作$3$，不再继续回溯。复杂度$O(logn)$。 $3.$在该区间能右则右，不能右则左，因为已经保证该区间一定有合法解了。复杂度$O(logn)$。 $

因此单次询问复杂度就是O(logn)。总复杂度O(nlogn)。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define iiii pair<int, pii>
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define getchar() (*input_pos++)
const int TT = 22000050;
char input_buffer[TT], output_buffer[TT];
char *input_pos = input_buffer, *output_pos = output_buffer;
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
inline void write(int x) {
  if (!x) return;
  write(x / 10);
  (*output_pos++) = x % 10 + '0';
}
using namespace std;
//ruogu_alter
const int N = 1e6 + 5;
const ll inf = 2e18;
int n, k, w[N], d[N], res[N];
ll a[N], b[N], dat[N << 2], tag[N << 2], mn[N << 2];
vector<int> st;
//
inline void add(int k, ll x) {
  dat[k] += x; 
  tag[k] += x;
}
inline void pd(int k) {
  if (tag[k]) {
    add(2 * k + 1, tag[k]);
    add(2 * k + 2, tag[k]);
    tag[k] = 0;
  }
}
void upd(int l, int r, int k, int p) {
  if (r - l == 1) {
    mn[k] = dat[k] = b[p];
    return;
  }
  int mid = (l + r) >> 1;
  if (p < mid) upd(l, mid, 2 * k + 1, p);
  else upd(mid, r, 2 * k + 2, p);
  dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
  mn[k] = min(mn[2 * k + 1], mn[2 * k + 2]);
}
void modify(int l, int r, int x, int y, int k, ll v) {
  if (l >= y || x >= r) return;
  if (x <= l && r <= y) {
    add(k, v);
    return;
  }
  pd(k);
  int mid = (l + r) >> 1;
  modify(l, mid, x, y, 2 * k + 1, v);
  modify(mid, r, x, y, 2 * k + 2, v);
  dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
}
int qry(int l, int r, int p, int id, ll x) {
  if (r - l == 1) return l;
  pd(id);
  int mid = (l + r) >> 1; ll to = min(x, dat[2 * id + 1]);
  if (mid <= p && to >= mn[2 * id + 2] - k) {
    int ans = qry(mid, r, p, 2 * id + 2, to);
    if (ans >= 0) return ans;
  }
  if (mn[2 * id + 1] - k <= x) return qry(l, mid, p, 2 * id + 1, x);
  return -1;
}
int main() {
  rep(i, N << 2) mn[i] = -inf, dat[i] = inf;
  fread(input_buffer, 1, TT, stdin);
  n = getint(); k = getint();
  rep(i, n - 1) d[i] = getint();
  rep(i, n) w[i] = getint();
  for (int i = 1; i < n; i++) a[i] = a[i - 1] + w[i - 1] - d[i - 1];
  b[0] = -w[0];
  for (int i = 1; i < n; i++) b[i] = b[i - 1] - w[i] + d[i - 1];
  st.emplace_back(n); a[n] = -inf;
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    upd(0, n, 0, i);
    while (st.size() && a[st.back()] >= a[i]) {
      if (st.size() > 2) modify(0, n, st[st.size() - 2] - 1, n, 0, a[st.back()] - a[st[st.size() - 2]]);
      st.pop_back();
    }
    int lb = 0, rb = st.size();
    while (rb - lb > 1) {
      int mid = (lb + rb) >> 1;
      if (a[st[mid]] + k < a[i]) lb = mid;
      else rb = mid;
    }
    if (st.size() > 1) modify(0, n, st[st.size() - 1] - 1, n, 0, a[st[st.size() - 1]] - a[i]);
    st.emplace_back(i);
    res[i] = qry(0, n, st[lb] - 1, 0, inf);
  }
  rep(i, n) {
    write(res[i] + 1);
    *output_pos++ = ' ';
  }
  fwrite(output_buffer, 1, output_pos - output_buffer, stdout);
  return 0;
}