CF671E Organizing a Race

2021 年 1 月 5 日
筆記
演算法-二分, 演算法-數據結構, 演算法-貪心, 題目來源-Codeforces

CF671E Organizing a Race

題目大意

K 國有 \(n\) 座城市和 \(n-1\) 條道路將它們相連。第 \(i\) 條道路連接了編號為 \(i\) 和 \(i + 1\) 的兩座城市，道路長度為 \(w_i\)。

在 K 國駕駛時，每當到達城市 \(i\)，你的車會立即得到能使它行駛 \(g_i\) 個單位長度的油。

你現在要舉辦一場賽車比賽。比賽在 \(l,r\) 兩座城市間進行。比賽分為兩個獨立的階段。第一階段，車從 \(l\) 駛向 \(r\)，第二階段，車從 \(r\) 回到 \(l\)。每個階段內部，不能走回頭路（也就是在第一階段只能向右走，第二階段只能向左走）。定義一場 \(l,r\) 之間的比賽的美麗度為 \(r – l + 1\)。你可以認為車的油箱是無窮大的，所以參賽者在途中會領取所有可獲得的油。

在每個階段的開始，油箱都是空的（也就是第一階段剩餘的油，不會留到第二階段）。開始後的一瞬間，車會立刻得到起點處的油（在第一階段是 \(g_l\)，在第二階段是 \(g_r\)）。

如果在途中車沒油了，則比賽無法進行。因此不是所有的 \(l,r\) 之間都能舉行比賽。

你有 \(k\) 次機會。每次你可以選擇一個城市 \(i\)，並令 \(g_i\) 提升 \(1\)。可以對一個城市重複操作，並多次獲得提升。問，經過操作後，你能舉辦的美麗度最大的比賽，美麗度是多少？

數據範圍：\(2\leq n\leq 10^5\)，\(1\leq w_i\leq 10^9\)，\(0\leq k,g_i\leq 10^9\)。

本題題解

初步轉化：前綴和

考慮 \(l,r\) 之間能舉辦比賽，需要滿足什麼條件。對兩個階段分別看，不難列出條件：

\[\begin{cases}
\forall i\in[l, r): \sum_{j = l}^{i}g_j \geq \sum_{j = l}^{i}w_j\\
\forall i\in[l,r): \sum_{j = i + 1}^{r} g_j\geq \sum_{j = i}^{r – 1} w_{j}
\end{cases}
\]

做前綴和。設 \(G_i = \sum_{j = 1}^{i}g_j\)，\(W_i=\sum_{j = 1}^{i}w_j\)。則條件也可以寫成：

\[\forall i \in[l,r):\begin{cases}
G_i – G_{l – 1} \geq W_{i} – W_{l – 1}\\
G_r – G_{i}\geq W_{r – 1} – W_{i – 1}
\end{cases}
\]

移項，把關於 \(i\) 的放在一邊，關於 \(l\) 或 \(r\) 的放在另一邊：

\[\forall i \in[l,r):\begin{cases}
G_i – W_{i} \geq G_{l – 1} – W_{l – 1}\\
G_{i} – W_{i – 1}\leq G_r – W_{r – 1}
\end{cases}
\]

設 \(a_i= G_i – W_i\)，\(b_i = G_i – W_{i – 1}\)。特別地，\(a_{0} = 0\)。則條件也可以寫成：

\[\forall i \in[l,r): \begin{cases}
a_i \geq a_{l – 1}\\
b_i \leq b_r
\end{cases}
\]

考慮一次操作（\(g_i\texttt{++}\)）對 \(a\), \(b\) 的影響。發現相當於對所有 \(j\geq i\)，令 \(a_j\texttt{++}\)，\(b_j\texttt{++}\)。

至此我們把問題轉化為了關於兩個序列 \(a\), \(b\) 的，更簡明的問題。

考慮枚舉 \(l\) 或 \(r\)，再按一定順序枚舉另一個，我們很容易寫出一個 \(\mathcal{O}(n^2)\) 的暴力。

進一步轉化：單調棧，貪心

首先 \(l = r\) 一定是可行的。故以下只討論 \(l < r\) 的情況。

先不考慮 \(b\) 的限制。如果只有 \(a_i\geq a_{l-1}\) 這一個要求，我們會如何操作呢？顯然，全部都在 \(l\) 處操作是最優的，所需的操作次數是 \(\max\{0, a_{l – 1} – \min_{i \in[l,r)}\{a_i\}\}\)。

但當有了 \(b\) 的限制，全部在 \(l\) 處操作就不一定可行了。因為可能存在一個 \(b_p > b_r\) (\(p\in[l,r)\))，全在 \(l\) 操作時，\(b_p\) 會和 \(b_r\) 一起變大，則 \(b_p\) 永遠大於 \(b_r\)，不滿足 \(b\) 的限制。

為了讓 \(b\) 合法，我們必須使 \(b_r\) 比 \(b_p\) 被多加了 \(b_p – b_r\) 次。也就是說，至少要有 \(b_p – b_r\) 次操作，是在 \(p\) 右邊的位置進行的。

我們從 \(r\) 向左，依次找到：第一個大於 \(b_r\) 的位置 \(p_1\)；第一個大於 \(b_{p_1}\) 的位置 \(p_2\)；……。也就是序列 \(b_{1\dots r}\) 的後綴最大值所在的位置，從右向左記為 \(p_1,p_2,\dots,p_m\)。另記 \(p_0 = r, p_{m + 1} = 0\)。如果從小到大枚舉 \(r\)，則這些位置可以用一個單調棧維護出來。現在，對每個 \(p_i\) (\(1\leq i\leq m, p_i \geq l\))，必須有至少 \(b_{p_i} – b_r\) 次操作是在 \(p_i\) 後面進行的。根據一開始的貪心原則（儘可能使 \(a\) 合法），我們一定會在盡量靠前的位置使用這些操作，也就是對所有 \(i\)，在 \(p_i + 1\) 的位置，使用 \(b_{p_i} – b_{p_{i – 1}}\) 次操作。

前面說過，我們從小到大枚舉 \(r\)，並用單調棧維護出 \(p\) 序列。現在假設已知了 \(l\)，那我們就知道了所有 \(p_i\geq l\) 的 \(p_i\)，進而能夠確定，為了使 \(b\) 合法，所必須做的這些操作（對所有 \(p_i\geq l\)，在 \(p_i + 1\) 的位置，使用 \(b_{p_i} – b_{p_{i – 1}}\) 次操作）。操作完成後，\(a\) 序列的數值會有所更新，記更新後的序列為 \(a’\)，即：\(a’_j = a_j + \sum_{l\leq p_i < j}(b_{p_i} – b_{p_{i – 1}})\)。現在 \(b\) 的限制已經滿足，接下來要通過最少的操作使 \(a\) 合法，也就是最開始的貪心：在 \(l\) 處再進行 \(\max\{0, a_{l – 1} – \min_{j \in[l,r)}\{a’_j\}\}\) 次操作即可。

發現當 \(l\) 存在於某個區間 \((p_{i + 1}, p_i]\) 時，使 \(b\) 合法所需的操作次數（記為 \(x\)）是一樣的，得到的 \(a’\) 序列也是一樣的（只考慮 \(a’_{l\dots r – 1}\) 這段區間，其他位置不管）。所以可以枚舉 \(l\) 所在的區間。在保證 \(x\leq k\) 的前提下，剩餘操作次數 \(\max\{0, a_{l – 1} – \min_{j \in[l,r)}\{a’_j\}\}\) 這個式子里的 \(\max\) 可以去掉（因為 \(x +\max\{0,y\}\leq k\) 和 \(x + y\leq k\)，在 \(x\leq k\) 時是一樣的）。於是我們可以用數據結構維護 \(a’\) 序列，並支援求 \(a_{l – 1} – \min_{j \in[l,r)}\{a’_j\}\leq k – x\) 的最小的 \(l\)（不知道具體實現方法沒關係，後面會講）。

但是當 \(b\) 序列近似單調遞減時，\(p\) 序列的長度是 \(\mathcal{O}(n)\) 的，上述做法的時間複雜度可能退化為 \(\mathcal{O}(n^2\log n)\)，還不如暴力。但這可以通過一個巧妙的觀察來避免。

巧妙觀察，省去枚舉

設區間 \((p_{i + 1}, p_i]\) 所需的操作次數為 \(x_i\)，即 \(x_i = \sum_{1\leq j\leq i}(b_{p_j} – b_{p_{j – 1}})\)。完成這 \(x_i\) 次操作後，我們會把剩餘的 \(k – x_i\) 次操作，全部作用於位置 \(l\) 上。也就是說，每個 \(a’_j\) (\(l\leq j < r\)) 還會再增加 \(k – x_i\)。那把這 \(k – x_i\) 次操作作用於 \(l\)，和把這些操作作用於任意位置 \(1\leq t < l\)，對 \(a’_{l\dots r-1}\) 來說，效果是一模一樣的。因此，如果我們找出了滿足 \(x_i\leq k\) 的最大的 \(i\)，那麼可以假裝進行了這 \(x_i\) 次操作。這不會影響 \(l > p_i\) 時的正確性。

在單調棧加入、彈出元素時，可以順便維護出 \(x_i\) 序列。因此可以很方便地二分出 \(x_i\leq k\) 的最大的 \(i\)。同時也就確定了對應的 \(a’\) 序列（具體如何維護後面會講）。問題轉化為求哪些 \(l\) 能在 \(k – x_i\) 次操作內，使 \(a\) 合法。具體來說是要找到 \(a_{l – 1} – \min_{j \in[l,r)}\{a’_j\}\leq k – x_i\) 的最小的 \(l\)。

數據結構維護：一類有技巧的線段樹

用線段樹來維護序列 \(c_i = a_{i – 1} – \min_{j \geq i}\{a’_j\}\)。其中 \(a_{i – 1}\) 是從一開始就確定不變的值。對 \(a’\) 我們會在整個過程中不斷修改。注意，我們要查詢的其實是：\(a_{l – 1} – \min_{j \in[l,r)}\{a’_j\}\)，但這可以通過把 \(j \geq r\) 的 \(a’_j\) 全部維護為 \(\infty\) 來轉化為 \(c_l\)。

考慮具體要支援哪些操作：

對 \(a’\) 進行區間加。在單調棧加入、彈出元素，以及確定了 \(i\) 後，對 \(a’\) 的所有修改都可以歸結為區間加（減法就是加負數）。
查詢：在線段樹上二分出 \(c_l\leq v\) 的最小的 \(l\)，其中 \(v = k – x_i\) 是一個定值。這相當於要維護出 \(c\) 序列的區間最小值。

對區間 \([l,r]\) 做區間加時，還會影響到 \(i < l\) 的 \(c_i\) 的值，所以並不是很容易直接維護。於是這裡就需要用到一類有技巧的線段樹，讀者可以去粉兔的部落格學習一下。

在本題里，線段樹的每個節點上，維護四個資訊。設這個節點對應的區間為 \([l,r]\)。

\(\text{mn1}\)：區間內 \(a’\) 的最小值。即 \(\text{mn1}(l,r) = \min_{l\leq i\leq r}\{a’_i\}\)。
\(\text{tag}\)：對 \(a’\) 進行區間加的懶標記。這和普通線段樹是一樣的。
\(\text{mn}2\)：區間內 \(a_{i – 1}\) 的最小值。即 \(\text{mn2}(l,r) = \min_{l\leq i\leq r}\{a_{i – 1}\}\)。
\(\text{lans}\)：這就是這類線段樹特有的東西了。葉子節點是沒有 \(\text{lans}\) 的。對非葉子節點，它的 \(\text{lans}\) 表示只考慮區間 \([l,r]\) 里的數（而不是整個序列 \(1\dots n\)）時，它左兒子區間的 \(c_i\) 的最小值。形式化地，設該節點兩個兒子區間分別為：\([l,\text{mid}]\) 和 \([\text{mid} + 1, r]\)，則 \(\text{lans}(l,r) = \min_{l\leq i\leq \text{mid}}\{a_{i – 1} – \min_{i\leq j\leq r}\{a’_j\}\}\)。這個「只考慮區間 \([l,r]\) 里的數」，最關鍵就體現在，裡面 \(a’_j\) 並不是取 \(j\in[i, n]\) 的 \(\min\)，而是 \(j\in[i,r]\)。

考慮如何 \(\text{push up}\)，也就是用兒子區間的資訊，更新父親區間。\(\text{mn1}\), \(\text{mn2}\) 的更新是簡單的，對兩個兒子取較小者即可。關鍵是 \(\text{lans}\)。現在假設已經知道了當前節點子樹里，除它以外所有節點的 \(\text{lans}\)。

考慮定義一個函數 \(\text{calc}(u, v)\)。其中 \(u\) 是線段樹上一個節點，\(v\) 可以是任意數值。\(\text{calc}(u, v)\) 返回的是：假設後綴最小值為 \(v\) 時，點 \(u\) 所代表的區間里，\(c_i\) 的最小值。則 \(\text{lans}(u)\) 就等於 \(\text{calc}(\text{LeftSon}_u, \text{mn1}(\text{RightSon}_u))\)。

考慮如何實現 \(\text{calc}\) 函數。這裡給出偽程式碼：

\[\begin{array}{l}
\textbf{def: } \mathrm{calc}(u, v) \\
\qquad \textbf{if } (u \text{ is a leaf node}) \\
\qquad \qquad \textbf{return } {\color{green}{\text{mn2}(u) – \min\{\text{mn1}(u), v\}}} \\
\qquad \textbf{else} \\
\qquad \qquad \textbf{if } (\text{mn1}(\text{RightSon}_u) > v) \\
\qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{\text{calc}(\text{LeftSon}_u, v)}}, {\color{red}{\text{mn2}(\text{RightSon}_u) – v}} \}\\
\qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{\text{lans}(u)}}, {\color{red}{\text{calc}(\text{RightSon}_u, v)}} \} \\
\qquad \qquad \textbf{endif.} \\
\qquad \textbf{endif.} \\
\textbf{enddef.}
\end{array}
\]

程式碼的含義是：

當 \(u\) 是葉子節點的情況顯然。
否則，若 \(\text{mn1}(\text{RightSon}_u) > v\)，則對右區間的所有位置來說，它們後面的最小值都是 \(v\)，所以右區間 \(c_i\) 的最小值就是 \(\text{mn2}(\text{RightSon}_u) – v\)。
否則，\(\text{mn1}(\text{RightSon}_u) \leq v\)，此時 \(v\) 不影響左區間的答案。

因為每次只向兩兒子中的一個遞歸，所以執行一次 \(\text{calc}\) 函數的時間複雜度為 \(\mathcal{O}(\log n)\)。因為每次 \(\text{push up}\) 時都要 \(\text{calc}\)，所以一次區間加的時間複雜度為 \(\mathcal{O}(\log^2 n)\)。

線段樹上二分也與普通的線段樹上二分是類似的。只不過判斷向哪邊遞歸時需要調用 \(\text{calc}\) 函數。所以時間複雜度也是 \(\mathcal{O}(\log^2 n)\)。

至此，我們以 \(\mathcal{O}(n\log^2 n)\) 的總時間複雜度解決了本題。

參考程式碼

// problem: CF671E
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 1e5;
const int INF = 1e9;
const ll LL_INF = 1e16;

int n, g[MAXN + 5], w[MAXN + 5];
ll K, a[MAXN + 5], b[MAXN + 5];

int sta[MAXN + 5], top;
ll val[MAXN + 5], presum_val[MAXN + 5];

struct SegmentTree {
	ll mn[MAXN * 4 + 5], tag[MAXN * 4 + 5];
	ll mn2[MAXN * 4 + 5];
	ll lans[MAXN * 4 + 5];
	
	void push_down(int p) {
		if (tag[p] != 0) {
			mn[p << 1] += tag[p];
			tag[p << 1] += tag[p];
			lans[p << 1] -= tag[p];
			mn[p << 1 | 1] += tag[p];
			tag[p << 1 | 1] += tag[p];
			lans[p << 1 | 1] -= tag[p];
			tag[p] = 0;
		}
	}
	ll calc(int p, int l, int r, ll right_min) {
		if (l == r) {
			return mn2[p] - min(right_min, mn[p]);
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (right_min >= mn[p << 1 | 1]) {
			return min(lans[p], calc(p << 1 | 1, mid + 1, r, right_min));
		} else {
			return min(calc(p << 1, l, mid, right_min), mn2[p << 1 | 1] - right_min);
		}
	}
	void push_up(int p, int l, int mid) {
		mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
		lans[p] = calc(p << 1, l, mid, mn[p << 1 | 1]);
	}
	void build(int p, int l, int r) {
		if (l == r) {
			mn[p] = a[l];
			mn2[p] = a[l - 1];
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		
		mn2[p] = min(mn2[p << 1], mn2[p << 1 | 1]);
		push_up(p, l, mid);
	}
	void range_add(int p, int l, int r, int ql, int qr, ll v) {
		if (ql <= l && qr >= r) {
			mn[p] += v;
			tag[p] += v;
			lans[p] -= v;
			return;
		}
		
		push_down(p);
		
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			range_add(p << 1, l, mid, ql, qr, v);
		}
		if (qr > mid) {
			range_add(p << 1 | 1, mid + 1, r, ql, qr, v);
		}
		
		push_up(p, l, mid);
	}
	int _find(int p, int l, int r, ll right_min, ll v) {
		if (l == r) {
			return l;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (calc(p << 1, l, mid, min(right_min, mn[p << 1 | 1])) <= v) {
			return _find(p << 1, l, mid, min(right_min, mn[p << 1 | 1]), v);
		} else {
			return _find(p << 1 | 1, mid + 1, r, right_min, v);
		}
	}
	int find(int p, int l, int r, ll right_min, int ql, int qr, ll v) {
		if (ql <= l && qr >= r) {
			if (calc(p, l, r, right_min) <= v) {
				return _find(p, l, r, right_min, v);
			} else {
				return INF;
			}
		}
		
		push_down(p);
		int mid = (l + r) >> 1;
		int res = INF;
		if (ql <= mid) {
			res = find(p << 1, l, mid, min(right_min, mn[p << 1 | 1]), ql, qr, v);
			if (res != INF)
				return res;
		}
		if (qr > mid) {
			res = find(p << 1 | 1, mid + 1, r, right_min, ql, qr, v);
		}
		return res;
	}
	SegmentTree() {}
};

SegmentTree T;

int calc(int p, int r) {
	if (sta[p - 1] + 1 > r - 1) {
		return 0;
	}
	
	ll sum = presum_val[top - 1] - presum_val[p - 1];
	
	T.range_add(1, 1, n, r, n, LL_INF); // 強制不考慮 >= r 的部分
	T.range_add(1, 1, n, sta[p - 1] + 1, r - 1, -presum_val[p - 1]);
	
	int res = T.find(1, 1, n, LL_INF, sta[p - 1] + 1, r - 1, K - sum);
	
	T.range_add(1, 1, n, r, n, -LL_INF); // 恢復原狀
	T.range_add(1, 1, n, sta[p - 1] + 1, r - 1, presum_val[p - 1]);
	return r - res + 1;
}
int main() {
	cin >> n >> K;
	for (int i = 1; i < n; ++i) {
		cin >> w[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> g[i];
	}
	
	for (int i = 1; i < n; ++i) {
		a[i] = a[i - 1] + g[i] - w[i];
		//cerr << a[i] << " \n"[i == n - 1];
	}
	for (int i = 1; i <= n; ++i) {
		b[i] = b[i - 1] + g[i] - w[i - 1];
		//cerr << b[i] << " \n"[i == n];
	}
	
	T.build(1, 1, n);
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		while (top && b[sta[top]] <= b[i]) {
			if (top > 1) {
				T.range_add(1, 1, n, sta[top - 1] + 1, sta[top], -presum_val[top - 1]);
			}
			--top;
		}
		sta[++top] = i;
		if (top > 1) {
			val[top - 1] = b[sta[top - 1]] - b[i];
			presum_val[top - 1] = presum_val[top - 2] + val[top - 1];
			
			T.range_add(1, 1, n, sta[top - 1] + 1, i, presum_val[top - 1]);
		}
		
		/*
		for (int j = 1; j <= i; ++j) f[j] = a[j];
		ll sum = 0;
		for (int j = top; j >= 1; --j) {
			// l in (sta[j - 1], sta[j]]
			
			for (int k = sta[j] + 1; k <= i; ++k) {
				f[k] += b[sta[j]] - b[sta[j + 1]];
			}
			if (j < top) {
				sum += b[sta[j]] - b[sta[j + 1]];
			}
			
			ll mn = LL_INF;
			for (int k = sta[j] + 1; k < i; ++k)
				ckmin(mn, f[k]);
			for (int l = sta[j] - (j == top); l > sta[j - 1]; --l) {
				ckmin(mn, f[l]);
				ll cost = sum + max(0LL, a[l - 1] - mn);
				if (cost <= K) {
					ckmax(ans, i - l + 1);
				}
			}
		}
		*/
		
		int l = 1, r = top;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (presum_val[top - 1] - presum_val[mid - 1] <= K) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		
		ckmax(ans, calc(l, i));
	}
	cout << ans << endl;
	return 0;
}