CF477E Dreamoon and Notepad

key：分类讨论；贪心；拆贡献、放缩等思想。

Solution

简要 写一下分类讨论，防止写代码的时候脑子不清晰。参考了 这篇 题解。

首先可以发现一个关键性质：HOME 和 END 在一次询问中不能同时使用，并且 HOME 或 END 最多只会使用一次，因为只会保留二者的所有操作集合中的最后一次使用。

所以有了第一个分类依据：1.只使用上下左右移动；2.使用 HOME；3.使用 END。

第二个分类依据是纵向移动的方式：1.不改变纵向方向；2.向上绕行；3.向下绕行。

为了方便处理，对于一次 \((r_1, c_1) \to (r_2, c_2)\) 的移动，我们假定 \(r_1 \le r_2\)。否则，我们可以让序列翻转，归约到 \(r_1 \le r_2\) 的问题。

以下的讨论建立在一个非常重要的贪心策略上，那就是只会在结束行使用左右移动。证明略。

除此之外，各类讨论均涉及到一些贪心，大都比较简单，证明略。

不改变纵向方向

• 既不使用 HOME，也不使用 END

  步数：\(r_2 - r_1 + |c_2 - \min(c_1, w[r_1, r_2])|\)。此处及下文 \(w[l, r]\) 均表示 \(\min\limits_{i = l}^{r}a_i\)。

• 使用 HOME

  你在哪一行使用 HOME 都可以，但只在第 \(r_2\) 行使用右移。

  步数：\(r_2 - r_1 + c_2 + 1\)。

• 使用 END

  你并不清楚在哪一行使用 END 更优，考虑枚举在哪一行使用 END。假设为 \(r_0\)。

  则步数为：\(r_2 - r_1 + |c_2 - w[r_0, r_2]| + 1\)。枚举 \(r_0\) 不现实，由于 \(w[l, r]\) 在 \(r\) 固定时关于 \(l\) 单增，考虑强行拆绝对值。

  • \(c_2 \le w[r_0, r_2]\)：需要让二者差值尽量小，则后者尽量小，则 \(r_0\) 尽量小，可二分/倍增出最优的 \(r_0\)，更新答案。

  • \(c_2 > w[r_0, r_2]\)：需让后者尽量大，则 \(r_0\) 尽量大，可直接利用上一种情况的 \(r_0\) 减一。更新答案。注意 \(w[r_0, r_2] = a_{r_0}\)，所以没必要在 ST 表上查。以下存在这种优化的讨论将不再提及此优化。

向上绕行

向上绕行使用 HOME 一定不优。

• 既不使用 HOME，也不使用 END

  假设向上最远到第 \(r_0(r_0 \le r_1)\) 行。

  步数：\(r_1 - r_0 + r_2 - r_0 + |c_2 - \min(c_1, w[r_0, r_2])|\)。

  其中 \(w[r_0, r_2] = \min(w[r_0, r_1], w[r_1, r_2])\)，后者为定值，提出来与 \(c_1\) 合在一起，记为 \(c_0 = \min(c_1, w[r_1, r_2])\)。

  步数：\(r_1 + r_2 - 2r_0 + |c_2 - \min(c_0, w[r_0, r_1])|\)。

  若 \(c_0 \le c_2\)，则向上绕行只会使 \(\min(c_0, w[r_0, r_1])\) 减小，从而使步数变大，因此此时向上绕行一定不优。

  所以只在 \(c_0 > c_2\) 时考虑向上绕行。同时只有 \(w[r_0, r_1] < c_0\) 时，\(\min(c_0, w[r_0, r_1])\) 才会变化，向上绕行才会有意义，步数为：\(r_1 + r_2 - 2r_0 + |c_2 - w[r_0, r_1]|\)。

  • \(c_2 \le w[r_0, r_1]\)：问题变为最小化 \(w[r_0, r_1] - 2r_0\)。利用 放缩 思想，构建 \(a_x - 2x\) 的 ST 表，在满足 \(w[r_0, r_1] \ge c_2\) 的区间上查最小值即可。
  • \(c_2 > w[r_0, r_1]\)：要最小化 \(-(w[r_0, r_1] + 2r_0)\)。该式关于 \(r_0\) 单减，因此找到满足条件的最大 \(r_0\) 进行更新即可。

  由于 \(a_{r_1} \ge c_0 > c_2\)，所以 \(c_2 \le w[r_0, r_1]\) 时的二分一定有解。

• 使用 END

  贪心策略是，向上最远到第 \(r_0\) 行，并在该行使用 END，然后往回走。

  步数：\(r_1 - r_0 + r_2 - r_0 + |c_2 - w[r_0, r_2]| + 1\)。可以按第一大类中第三小类的方法分类讨论：

  • \(c_2 \le w[r_0, r_2]\)：要最小化 \(w[r_0, r_2] - 2r_0\)。这与该大类的第一类求法完全一样，二分出对应区间后在 \(a_x - 2x\) 的 ST 表上查即可。（该情况存在在 ST 表上查出来与原式不符，但可以证明这些情况向上绕行一定不优）
  • \(c_2 > w[r_0, r_2]\)：要最小化 \(-(w[r_0, r_2] + 2r_0)\)。该式关于 \(r_0\) 单减，找到满足条件的最大 \(r_0\) 即可。

  如果 \(w[r_1, r_2] < c_2\)，则 \(c_2 \le w[r_0, r_2]\) 时二分无解，但舒服的地方在于，如果是这样的，则向上绕行一定不优。

向下绕行

向下绕行使用 HOME 一定不优。

记向下最远到达 \(r_0(r_0 \ge r_2)\)。由于求法与第二大类一致，因此只是简略地写一下式子。

• 既不使用 HOME，也不使用 END

  步数 \(2r_0 - r_1 - r_2 + |c_2 - \min(c_1, w[r_1, r_0])|\)。

  \(w[r_1, r_0] = \min(w[r_1, r_2], w[r_2, r_0])\)。

  记 \(c_0 = \min(c_1, w[r_1, r_2])\)，步数：\(2r_0 - r_1 - r_2 + |c_2 - \min(c_0, w[r_2, r_0])|\)。

  只有 \(c_0 > c_2\) 且 \(c_0 > w[r_2, r_0]\) 时，该情况可能更新答案。步数为：\(2r_0 - r_1 - r_2 + |c_2 - w[r_2, r_0]|\)。

  • \(c_2 \le w[r_2, r_0]\) 时：要最小化 \(w[r_2, r_0] + 2r_0\)，构建 \(a_x + 2x\) 的 ST 表进行查询。
  • \(c_2 > w[r_2, r_0]\) 时：要最小化 \(2r_0 - w[r_2, r_0]\)，该式关于 \(r_0\) 单增，用最小的 \(r_0\) 更新即可。

• 使用 END

  步数：\(2r_0 - r_1 - r_2 + |c_2 - w[r_2, r_0]| + 1\)。

  • \(c_2 \le w[r_2, r_0]\)：要最小化 \(w[r_2, r_0] + 2r_0\)。利用 \(a_x + 2x\) 的 ST 表可得。
  • \(c_2 > w[r_2, r_0]\)：要最小化 \(2r_0 - w[r_2, r_0]\)。该式关于 \(r_0\) 单增，用最小的 \(r_0\) 更新答案即可。

实现上有一些取等之类的细节与上文不同（主要是方便二分，让二分区间内一定有解），但并无大碍。

#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define lowbit(x) x & (-x)
#define PII pair<int, int>
#define MP make_pair
#define VI vector<int>
#define VII vector<int>::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define SI set<int>
#define SII set<int>::iterator
#define QI queue<int>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
int inc(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		Sqr(x), k >>= 1;
	}
	return res;
}
void read(int &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 4e5 + 5;
const int F = 21;
const int INF = 1e9 + 7;
struct Akashi
{
	int r1, c1, r2, c2, id;
}aks1[N], aks2[N];
int n, Q, a[N], cnt1, cnt2, ans[N];
struct ST
{
	int f[N][F];
	void build()
	{
		for(int j = 1; j < F; ++j)
			for(int i = 1; i + (1 << j) - 1 <= n; ++i)
				f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
	}
	int query(int l, int r)
	{
		int j = log2(r - l + 1);
		return min(f[l][j], f[r - (1 << j) + 1][j]);
	}
}st1, st2, st3;
void build()
{
	for(int i = 1; i <= n; ++i)
	{
		st1.f[i][0] = a[i];
		st2.f[i][0] = a[i] - 2 * i;
		st3.f[i][0] = a[i] + 2 * i;
	}
	st1.build();
	st2.build();
	st3.build();
}
int solve(int r1, int c1, int r2, int c2)
{
	int res = INF, l, r, mid;
	int r0, c0 = min(c1, st1.query(r1, r2));

	// situation 1
	chkmn(res, r2 - r1 + abs(c2 - c0));
	chkmn(res, r2 - r1 + c2 + 1);
	l = r1, r = r2;
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(st1.query(mid, r2) >= c2) 
			r = mid - 1, r0 = mid;
		else l = mid + 1;
	};
	chkmn(res, r2 - r1 + st1.query(r0, r2) - c2 + 1);
	if((--r0) >= r1) chkmn(res, r2 - r1 + c2 - a[r0] + 1);

	// situation 2
	if(c0 > c2)
	{
		l = 1, r = r1;
		while(l <= r)
		{
			mid = (l + r) / 2;
			if(st1.query(mid, r1) >= c2)
				r = mid - 1, r0 = mid;
			else l = mid + 1;
		};
		chkmn(res, r1 + r2 - c2 + st2.query(r0, r1));
		if((--r0) >= 1) chkmn(res, r1 + r2 + c2 - 2 * r0 - a[r0]);
	}
	if(st1.query(r1, r2) >= c2)
	{	
		l = 1, r = r1;
		while(l <= r)
		{
			mid = (l + r) / 2;
			if(st1.query(mid, r2) >= c2)
				r = mid - 1, r0 = mid;
			else l = mid + 1;
		};
		chkmn(res, r1 + r2 - c2 + st2.query(r0, r1) + 1);
		if((--r0) >= 1) chkmn(res, r1 + r2 + c2 - 2 * r0 - a[r0] + 1);
	}

	// situation 3
	if(c0 > c2)
	{
		l = r2, r = n;
		while(l <= r)
		{
			mid = (l + r) / 2;
			if(st1.query(r2, mid) >= c2)
				l = mid + 1, r0 = mid;
			else r = mid - 1;
		};
		chkmn(res, st3.query(r2, r0) - (r1 + r2 + c2));
		if((++r0) <= n) chkmn(res, c2 - r1 - r2 + 2 * r0 - a[r0]);
	}
	l = r2, r = n;
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(st1.query(r2, mid) >= c2)
			l = mid + 1, r0 = mid;
		else r = mid - 1;
	};
	chkmn(res, st3.query(r2, r0) - (r1 + r2 + c2) + 1);
	if((++r0) <= n) chkmn(res, 2 * r0 - r1 - r2 + c2 - a[r0] + 1);
	return res;
}
int main()
{
	read(n);
	for(int i = 1; i <= n; ++i)
		read(a[i]);
	read(Q);
	for(int i = 1; i <= Q; ++i)
	{
		int r1, c1, r2, c2;
		read(r1), read(c1), read(r2), read(c2);
		if(r1 <= r2) aks1[++cnt1] = (Akashi){r1, c1, r2, c2, i};
		else aks2[++cnt2] = (Akashi){n - r1 + 1, c1, n - r2 + 1, c2, i};
	}
	build();
	for(int i = 1; i <= cnt1; ++i)
	{
		Akashi now = aks1[i];
		int res = solve(now.r1, now.c1, now.r2, now.c2);
		ans[now.id] = res;
	}
	reverse(a + 1, a + n + 1);
	build();
	for(int i = 1; i <= cnt2; ++i)
	{
		Akashi now = aks2[i];
		int res = solve(now.r1, now.c1, now.r2, now.c2);
		ans[now.id] = res;
	}
	for(int i = 1; i <= Q; ++i)
		printf("%d\n", ans[i]);
	return 0;
}

本栏目推荐文章
• CF414B - Mashmokh and ACM
• Center-based 3D Object Detection and Tracking
• MIUI EU ROM install and upgrade
• AT_arc167_e 题解
• CF1284E New Year and Castle Construction
• E - Christmas Color Grid 1
• 2023 United Kingdom and Ireland Programming Contest (UKIEPC 2023)
• HDU #6664. Andy and Maze 题解--zhengjun
• CF678F Lena and Queries题解
• 【LeetCode 】练习str_to_date函数；over(rows between CURRENT ROW AND 2 following)实现【当月和接下来2个月】滑动窗口

Dreamoon Notepad 477E 477 anddreamoon notepad 477e and 477e 477 dreamoon 476b wifi and e-gardener-and-tree 题解e-gardener-and-tree gardener 1593 dreamoon codeforces dreamoon strings 1329d codeforces dreamoon 1329e loves dreamoon报告1329e loves