Statement
在数轴上给出 $m$ 个点和 $n$ 个询问，每个询问给出一个线段，初始放在 $[l_i,~r_i]$ 上，你需要移动该线段使得该线段能够依次包含所有的 $m$ 个点，问线段移动总距离的最小值。
$1 \le n,m \le 2 \times 10^5,~0 \le l_i,r_i \le 10^9$
Solution
由于 $l_i \le p \le l_i + len$ 与 $p - len + 1 \le l_i \le p$ 相同，因此在固定询问线段长度 $len$ 的情况下，可以将原问题中的询问线段变为位置在 $l_i$ 上的单点，$m$ 个点变为 $[p - len + 1,~p]$ 的线段，问题即转换为求移动该点使其依次经过每个区间的最短总距离。
结论 1：在一种移动方案中，若 $i - 1$ 时刻向 $i$ 时刻移动的方向与 $i$ 时刻向 $i + 1$ 时刻移动的方向相同，则 $i$ 时刻的限制可以无视。
证明：令 $i$ 时刻点所在位置为 $p_i$，以向右移动为例则若条件满足则说明 $p_{i - 1} < p_i < p_{i + 1}$。固定 $p_{i - 1}$ 和 $p_{i + 1}$ 时所有在该两点间的移动方案总会经过 $p_i$，在经过 $p_i$ 时满足 $i$ 时刻限制即可。
结论 2：若两个相邻限制线段 $[l_i,~r_i]$，$[l_{i + 1},~r_{i + 1}]$ 有交，则这两条线段的限制条件与一条 $[\max(l_i,~l_{i + 1}),~\min(r_i,~r_{i + 1})]$ 线段相同。
证明：$p_i$ 向 $p_{i + 1}$ 移动的过程中必定会经过他们交线段上的至少一个点，因此满足两条线段限制条件的方案必定满足交线段的限制条件。所有满足交线段限制条件的方案显然满足 $i$ 时刻和 $i + 1$ 时刻的限制，因此满足交线段限制条件的方案必定满足原来的两条线段的限制条件。
当我们固定询问区间长度 $len$ 时，通过结论 2 的约束，我们可以使得最终限制条件中任意两条相邻线段均不交。因此我们能够确定每一条线段（除了最后一条），该线段与下一条线段之间的移动方向。
结论 3：对于线段 $i$，若其到线段 $i + 1$ 的移动方向为左，则线段 $i$ 的限制条件与 $[l_i,~l_i]$ 相同。
证明显然，根据贪心，离下一条线段最近的点必然不劣。
根据结论 3，我们可以把所有线段限制缩为点，问题转化为：询问一点与 $m$ 个给定点依次相交的移动路径和。我们令第 $i$ 个限制为 $lim_i$。
根据结论 1，我们发现若出现 $lim_{i - 1} < lim_i < lim_{i + 1}$ 的情况，则 $lim_i$ 将不会起约束作用。我们按上述限制删除无用限制后，发现限制总是满足： $lim_{i - 1} < lim_i > lim_{i + 1}$ 或 $lim_{i - 1} > lim_i < lim_{i + 1}$。此时询问 $q$ 的答案即为 $|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} |$。
在固定 $len$ 的情况下我们已经能够求解原问题了，考虑在不固定 $len$ 时我们应该怎么做。我们考虑将所有询问离线后按照 $len$ 排序，从小到达枚举 $len$ 的同时维护限制条件下对应的答案。
我们可以将所有 $lim$ 分为左右两半，满足 $lim_{i - 1} > lim_i < lim_{i + 1}$ 的为左点，满足 $lim_{i - 1} < lim_i > lim_{i + 1}$ 的为右点。最终移动路径上的点一定为左右点相邻。所有的左点为原区间的右端点，所有的右点为原区间的左端点。由于原区间为 $[p - len + 1,~p]$，在 $len$ 增大时左端点会向左移动，即所有右点在 $len$ 增大 $1$ 时会向左移动 $1$。因此在询问的 $len$ 增大时我们只要给全局所有的右点通过懒标记整体向左移即可。
但是由于右点向左移动最终会与左点相交，相交后根据结论 2 我们需要删除相交的两个点中的一个，删除一个点后会出现两个同类点相邻的情况，令未删除的点为 $x$。当 $x$ 为第一个限制或是最后一个限制时令 $x$ 从左点变为右点或是从右点变为左点，$x$ 不为第一个或最后一个时删除 $x$ 因为其值在 $x - 1$ 与 $x + 1$ 之间。上述操作完后即可重新回到正常状态。
令相邻两限制间的距离为他们初始时刻的距离，使用 $set$ 维护所有相邻两限制间的距离，处理时间 $tim$ 时将所有距离不超过 $tim$ 的限制按照上述操作处理即可。由于每个时刻相邻两限制间的距离都会减一，因此最终答案即为 $|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} | - (m - 1) \times tim$。全局维护相邻限制距离和即可。
需要注意的是当只剩下一个限制时，由于不存在所谓“下一步移动方向”，随时间推移该点会逐渐展开为线段。
时间复杂度 $O(n \log n)$，常数较大。
Code
/**
* @file 4249.cpp
* @author Macesuted (i@macesuted.moe)
* @date 2022-03-25
*
* @copyright Copyright (c) 2022
* @brief
* My Tutorial: https://macesuted.moe/article/bzoj4249
*
*/
#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int SIZE = 1 << 20;
char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
template <typename T>
T read(void) {
T x = 0, f = +1;
char c = getch();
while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
return x * f;
}
template <typename T>
void write(T x) {
if (!x) putch('0');
if (x < 0) putch('-'), x = -x;
int top = 0;
while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
while (top) putch(stack[--top]);
return;
}
string getstr(const string& suf = "") {
string s = suf;
while (isspace(buftop())) getch();
while (Il != Ir) {
char* p = Il;
while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
s.append(p, Il);
if (Il < Ir) break;
fill();
}
return s;
}
void putstr(string str, int begin = 0, int end = -1) {
if (end == -1) end = str.size();
for (int i = begin; i < end; i++) putch(str[i]);
return;
}
struct Flusher_ {
~Flusher_() { flush(); }
} io_flusher_;
} // namespace IO
using IO::getch;
using IO::getstr;
using IO::putch;
using IO::putstr;
using IO::read;
using IO::write;
bool mem1;
#define maxn 200005
typedef pair<int, int> pii;
set<pii> S, Sd;
map<int, vector<pii>> ques;
int a[maxn];
long long ans[maxn], answer = 0;
template <typename T>
T dec(T a) {
return --a;
}
template <typename T>
T inc(T a) {
return ++a;
}
void insert(set<pii>::iterator p) {
return answer += abs(p->second - inc(p)->second), Sd.emplace(abs(p->second - inc(p)->second), p->first), void();
}
void erase(set<pii>::iterator p) {
return answer -= abs(p->second - inc(p)->second), Sd.erase({abs(p->second - inc(p)->second), p->first}), void();
}
void check(pii x, int tim) {
auto p = S.find(x);
if (p == S.begin() && p == dec(S.end())) return;
if (p == S.begin()) {
if (p->second == inc(p)->second) return S.erase(p), void();
if (inc(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first;
return insert(p);
}
if (p == dec(S.end())) {
if (p->second == dec(p)->second) return S.erase(p), void();
if (dec(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first;
return insert(dec(p));
}
return insert(--S.erase(p));
}
void solve(void) {
int n = read<int>(), m = read<int>();
for (int i = 1; i <= n; i++) {
int l = read<int>(), r = read<int>();
ques[r - l].emplace_back(l, i);
}
for (int i = 1; i <= m; i++) S.emplace(i, a[i] = read<int>());
for (auto i = ++S.begin(); inc(i) != S.end(); i++)
if ((dec(i)->second < i->second) == (i->second < inc(i)->second) || dec(i)->second == i->second ||
i->second == inc(i)->second)
i = --S.erase(i);
for (auto i = S.begin(); inc(i) != S.end(); i++)
Sd.emplace(abs(i->second - inc(i)->second), i->first), answer += abs(i->second - inc(i)->second);
int last = 0;
while (!Sd.empty()) {
int tim = Sd.begin()->first, ip = Sd.begin()->second;
Sd.erase(Sd.begin());
if (tim != last)
for (auto i = ques.begin(); i != ques.end() && i->first < tim; i = ques.erase(i)) {
int t = S.begin()->second;
if (S.begin()->second > inc(S.begin())->second) t -= i->first;
for (auto j : i->second) ans[j.second] = answer + abs(t - j.first) - 1LL * ((int)S.size() - 1) * i->first;
}
last = tim;
auto p = S.lower_bound({ip, 0}), q = inc(p);
erase(p);
if (p->second > q->second) {
if (p != S.begin()) erase(dec(p));
q = S.erase(p);
if (q != dec(S.end())) erase(q);
check(*q, tim);
} else {
if (q != dec(S.end())) erase(q);
p = --S.erase(q);
if (p != S.begin()) erase(dec(p));
check(*p, tim);
}
}
for (auto i : ques)
for (auto j : i.second)
if (S.begin()->second - (i.first - last) <= j.first && j.first <= S.begin()->second)
ans[j.second] = 0;
else
ans[j.second] = min(abs(S.begin()->second - j.first), abs(S.begin()->second - (i.first - last) - j.first));
for (int i = 1; i <= n; i++) write(ans[i]), putch('\n');
return;
}
bool mem2;
int main() {
ios::sync_with_stdio(false);
#ifdef MACESUTED
cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif
int _ = 1;
while (_--) solve();
#ifdef MACESUTED
cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
return 0;
}
Comments | NOTHING