F - Takahashi in Narrow Road
F - Takahashi in Narrow Road
Problem Statement
There is a road extending east and west, and $N$ persons are on the road. The road extends infinitely long to the east and west from a point called the origin.
The $i$-th person $(1\leq i\leq N)$ is initially at a position $X_i$ meters east from the origin.
The persons can move along the road to the east or west. Specifically, they can perform the following movement any number of times.
- Choose one person. If there is no other person at the destination, move the chosen person $1$ meter east or west.
They have $Q$ tasks in total, and the $i$-th task $(1\leq i\leq Q)$ is as follows.
- The $T_i$-th person arrives at coordinate $G_i$.
Find the minimum total number of movements required to complete all $Q$ tasks in order.
Constraints
- $1\leq N\leq2\times10^5$
- $0\leq X_1 < X_2 < \dotsb < X_N \leq10^8$
- $1\leq Q\leq2\times10^5$
- $1\leq T_i\leq N\ (1\leq i\leq Q)$
- $0\leq G_i\leq10^8\ (1\leq i\leq Q)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$Q$
$T_1$ $G_1$
$T_2$ $G_2$
$\vdots$
$T_Q$ $G_Q$
Output
Print the answer.
Sample Input 1
5
10 20 30 40 50
4
3 45
4 20
1 35
2 60Sample Output 1
239An optimal sequence of movements for the persons is as follows (the positions of the persons are not necessarily drawn to scale):
For each task, the persons move as follows.
- The 4th person moves $6$ steps east, and the 3rd person moves $15$ steps east.
- The 2nd person moves $2$ steps west, the 3rd person moves $26$ steps west, and the 4th person moves $26$ steps west.
- The 4th person moves $18$ steps east, the 3rd person moves $18$ steps east, the 2nd person moves $18$ steps east, and the 1st person moves $25$ steps east.
- The 5th person moves $13$ steps east, the 4th person moves $24$ steps east, the 3rd person moves $24$ steps east, and the 2nd person moves $24$ steps east.
The total number of movements is $21+54+79+85=239$.
You cannot complete all tasks with a total movement count of $238$ or less, so print 239.
Sample Input 2
8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578Sample Output 2
4294967297Note that some persons may need to move to the west of the origin or more than $10^8$ meters to the east of it.
Also, note that the answer may exceed $2^{32}$.
Sample Input 3
12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996Sample Output 3
89644
解题思路
官方题解看不懂，只能按自己比较复杂的思路去做，结果写代码加调试用了差不多 4 个小时。提示，本篇题解会用到支持区间赋值与区间加等差数列的线段树。区间赋值的内容可以参考：扶苏的问题。区间加等差数列的内容可以参考：E. Space Harbour。
其实只要按照题意去模拟就能得到答案，难的地方就在于，每次将一个人移到目标位置时哪些人的位置也会受到影响？如何去维护这个过程中受影响的人的位置？用 $p_t$ 表示第 $t$ 给人的位置，下面只讨论 $p_t < g$ 的情况，也就是第 $t$ 个人要往右移动到目标位置。处理向左移动情况的思想是一样的，类比一下就好了。
首先要解决第一个问题，第 $t$ 个人从 $p_t$ 移动到 $g$ 的过程中右边有多少个人也会移动。容易知道这些人的下标必定是连续的一段，我们不妨假设有 $c$ 个人（包括第 $t$ 个人），那么最后的结果就是 $\displaylines{\begin{cases} p_t \gets g \\ p_{t+1} \gets g+1 \\ \vdots \\ p_{t+i} \gets g + i - 1 \\ \vdots \\ p_{t + c - 1} \gets g + c - 1 \end{cases}}$。可以用二分找到这个 $c$，这是因为受影响的下标是连续的一段，因此具有二段性。对于二分点 $m$，check 的时候检查 $p_{t+m-1}$ 是否小于等于 $g+m-1$（等于 $g-m+1$ 的时候并不会影响答案），如果是的话呢，说明第 $t+m-1$ 个人会受到影响，否则不会受到影响。
现在我们找到一段会受到影响的连续位置了，那么这个移动过程中对答案的贡献就是
$$(g - p_t) + (g+1 - p_{t+1}) + \cdots + (g+c-1 - p_{t+c-1}) = \frac{c \cdot (g + g-c+1)}{2} - \sum\limits_{i=t}^{t+c-1}{p_{i}}$$
所以现在的问题是我们该如何快速求出 $\sum\limits_{i=t}^{t+c-1}{p_{i}}$，以及更新 $p_i$。
显然我们可以用线段树去维护序列 $p_i$，那么 $\sum\limits_{i=t}^{t+c-1}{p_{i}}$ 就是简单的区间查询。而更新就很复杂了，由于我们不可能一个一个去修改，因此首先需要将 $p_t \ldots p_{t+c-1}$ 先赋值为 $g$，然后再加上一个首相为 $0$ 公差为 $1$ 的等差数列。所以实际上我们需要维护的是 $p_i$ 的差分数组，定义差分数组 $f_i = p_i - p_{i-1}$。
与一般的支持区间加等差数列的线段树维护的东西一样，唯一不同的地方在于懒标记。除了区间加的懒标记 add 外，还需要维护区间赋值的懒标记 tag。其中当 tag 是 $\infty$ 时表示没有区间赋值的操作，不用下传。
为了简化操作这里将区间赋值和区间加等差数列统一成一个操作，表示成函数 add(int l, int r, int c, int k, int d)，意思是对区间 $[l,r]$ 内的元素先赋值为 $c$，再加上首相为 $k$ 公差为 $d$ 的等差数列，函数内容为下：
void add(int l, int r, int c, int k, int d) {
if (c != INF) {
modify(1, r + 1, r + 1, query(r + 1, r + 1) - c, 0);
modify(1, l, l, c - query(l - 1, l - 1), 0);
modify(1, l + 1, r, 0, 0);
}
else {
modify(1, l, l, c, k);
modify(1, l + 1, r, c, d);
modify(1, r + 1, r + 1, c, -(k + (r - l) * d));
}
} 这部分是对上面函数的解释。规定当 $c \ne \infty$ 表示需要进行赋值操作，由于线段树维护的是差分数组，我们要考虑赋值对差分数组的影响是怎样的。对 $p_l \sim p_r$ 进行赋值，$f_l \sim f_{r+1}$ 会受到影响。首先 $p_l$ 被修改成 $c$，自然有 $f_l \gets c - p_{l-1}$，其中 query(l,r) 得到的是 $\sum\limits_{i=l}^{r}{p_i}$，所以我们需要将 $f_l$ 赋值成 $c - p_{l-1}$，modify(int u, int l, int r, LL c, LL d) 的含义就是将区间 $[l,r]$ 内的元素先赋值为 $c$ 后再加上 $d$。然后是 $f_{l+1} \sim f_{r}$，由于 $p_{l} \sim p_{r}$ 的值都是 $c$，因此需要将 $f_{l+1} \sim f_{r}$ 都赋值为 $0$。最后是需要将 $f_{r+1}$ 赋值成 $p_{r+1} - c$。代码中的顺序会不一样是为了防止修改操作对查询的影响。
然后就是对区间 $[l,r]$ 加上等差数列了，与一般的支持区间加等差数列一样这里就不过多赘述了，包括 modify 的具体内容和懒标记的更新也与一般的支持区间赋值的线段树一样。
所以对于一个过程，二分出 $c$ 后，需要先后调用 add(t, t + c - 1, g, 0, 0) 和 add(t, t + c - 1, INF, 0, 1) 来维护受影响的人的位置。
AC 代码如下，时间复杂度为 $O(q\log^{2}{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int a[N];
struct Node {
int l, r;
LL s1, s2, tag, add;
}tr[N * 4];
void pushup(int u) {
tr[u].s1 = tr[u << 1].s1 + tr[u << 1 | 1].s1;
tr[u].s2 = tr[u << 1].s2 + tr[u << 1 | 1].s2;
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0, INF, 0};
if (l == r) {
tr[u].s1 = a[l] - a[l - 1];
tr[u].s2 = (l - 1) * tr[u].s1;
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void upd(int u, LL c, LL d) { // 将区间[l,r]内的元素赋值为c后再对每个元素加上d
// 如果c=INF意味着没有赋值操作，否则需要将区间内的元素均赋值为c
if (c != INF) {
tr[u].s1 = (tr[u].r - tr[u].l + 1ll) * c;
tr[u].s2 = (tr[u].r - tr[u].l + 1ll) * (tr[u].l + tr[u].r - 2) / 2 * c;
tr[u].tag = c;
tr[u].add = 0;
}
// 再对区间内的元素均加上d
tr[u].s1 += (tr[u].r - tr[u].l + 1) * d;
tr[u].s2 += (tr[u].r - tr[u].l + 1ll) * (tr[u].l + tr[u].r - 2) / 2 * d;
tr[u].add += d;
}
void pushdown(int u) {
upd(u << 1, tr[u].tag, tr[u].add);
upd(u << 1 | 1, tr[u].tag, tr[u].add);
tr[u].tag = INF, tr[u].add = 0;
}
void modify(int u, int l, int r, LL c, LL d) {
if (l > r) return;
if (tr[u].l >= l && tr[u].r <= r) {
upd(u, c, d);
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, c, d);
if (r >= mid + 1) modify(u << 1 | 1, l, r, c, d);
pushup(u);
}
}
LL query(int u, int l, int r) { // 查询差分数组在区间[l,r]的和，一般l=1，则query(u,1,r)的结果为第r个元素的值
if (l > r) return 0;
if (tr[u].l >= l && tr[u].r <= r) return r * tr[u].s1 - tr[u].s2;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
if (l >= mid + 1) return query(u << 1 | 1, l, r);
return query(u << 1, l, r) + query(u << 1 | 1, l, r);
}
LL query(int l, int r) { // 查询原数组在区间[l,r]的元素和
return query(1, 1, r) - query(1, 1, l - 1);
}
void add(int l, int r, int c, int k, int d) { // 将区间[l,r]内的元素赋值为c后再对该区间加上首相为k公差为d的等差数列
if (c != INF) {
modify(1, r + 1, r + 1, query(r + 1, r + 1) - c, 0);
modify(1, l, l, c - query(l - 1, l - 1), 0);
modify(1, l + 1, r, 0, 0);
}
else {
modify(1, l, l, c, k);
modify(1, l + 1, r, c, d);
modify(1, r + 1, r + 1, c, -(k + (r - l) * d));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n + 1);
cin >> m;
LL ret = 0;
while (m--) {
int x, y;
cin >> x >> y;
if (query(x, x) < y) {
int l = 1, r = n - x + 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (y + mid - 1 >= query(x + mid - 1, x + mid - 1)) l = mid;
else r = mid - 1;
}
ret += l * (y + y + l - 1ll) / 2 - query(x, x + l - 1);
add(x, x + l - 1, y, 0, 0);
add(x, x + l - 1, INF, 0, 1);
}
else {
int l = 1, r = x;
while (l < r) {
int mid = l + r + 1 >> 1;
if (y - mid + 1 <= query(x - mid + 1, x - mid + 1)) l = mid;
else r = mid - 1;
}
ret += query(x - l + 1, x) - l * (y - l + 1ll + y) / 2;
add(x - l + 1, x, y - l + 1, 0, 0);
add(x - l + 1, x, INF, 0, 1);
}
}
cout << ret;
return 0;
}
参考资料
Editorial - AtCoder Beginner Contest 371：https://atcoder.jp/contests/abc371/editorial/10931