JZOJ4559 【NOI2016模拟6.23】水平线上的肮脏交易和卑鄙勾当 转换模型后CDQ分治

题目大意

现在有一个坐标轴，现在有$N$个交易。对于一个交易有发生的时间$t_i$和发生的位置$s_i$，交易发生是瞬间的。初始时你在$0$处，$t=0$，每一时你可以选择左移一个单位或右移一个单位。问经过时间$T$后，一定要回到原点的情况下，交易的最小间隔是多少。

$N \leq 10^5$
$-10^6 \leq s_i \leq 10^6$

解题思路

我们考虑交易$j$满足什么条件时能在事件$i$后发生，即：$t_j - t_i \geq |s_i-s_j|$，我们化简一下可知等价于满足

$$\begin{matrix}& t_j - t_i \geq s_i-s_j& \\ & t_j - t_i \geq s_j-s_i& \end{matrix}$$
移一下项得：
$$\begin{matrix}& t_j +s_j \geq s_i+t_i& \\ & t_j - s_j \geq t_i-s_i& \end{matrix}$$

那么对于每个交易$j$我们只需要维护$t_j +s_j$和$t_j - s_j$。然后要满足两个条件，可以对第一个条件用CDQ分治，第二个条件排序，计算时就用前半部分更新后半部分，用线段树维护最优质。复杂度就是$O(Nlog^2N)$。设$F_j$表示到达交易$j$的最小间隔，那么$F_j = min(F_j,min(F_i,t_j - t_i))$，分类讨论一下：

$$\begin{matrix}& F_j =min(F_j,F_i)~~~~~~~~~~ (F_i+t_i \leq t_j)\\ & F_j = min(F_j,t_j-t_i)~~~~(F_i+t_j>t_j)& \end{matrix}$$
把第 $i$个交易在线段树中的下标为$F_i+t_j$，对于 $t_i$维护最大值，对于 $F_i$维护最小值。更新 $j$时查询$[1,t_j]$中 $F_i$的最小值，查询 $(t_j,Max]$的最大值来更新 $F_j$就可以了。对于答案我们只需要再增加一个 $s_{N+1}=0,t_{N+1}=T$的交易，然后最后查询 $F_{N+1}$就可以了。

程序

//YxuanwKeith
#include 
#include 
#include using namespace std;const int MAXN = 4e6 + 5, MAXM = 1e5 + 5;
const int Inf = 1e9 + 7;struct Node {int x, y, t;Node (int a, int b, int c) {x = a, y = b, t = c;}Node () {}
};struct Tree {int l, r, MaxT, MinF;
} Tr[MAXN * 4];Node D[MAXM], G[MAXM];
int N, T, Lim, End, Root, tot, F[MAXM];bool CmpX(Node A, Node B) {return A.x < B.x || A.x == B.x && A.y > B.y;
}bool CmpY(Node A, Node B) {return A.y > B.y || A.y == B.y && A.x < B.x;
}void Clear(int Now) {Tr[Now].l = Tr[Now].r = 0;Tr[Now].MaxT = -Inf, Tr[Now].MinF = Inf;
}void Modify(int &Now, int l, int r, int Side, int p, int t) {if (!Now) {Now = ++ tot;Clear(tot);}Tr[Now].MinF = min(Tr[Now].MinF, F[p]);Tr[Now].MaxT = max(Tr[Now].MaxT, t);if (l == r) return;int Mid = (l + r) >> 1;if (Side <= Mid) Modify(Tr[Now].l, l, Mid, Side, p, t); elseModify(Tr[Now].r, Mid + 1, r, Side, p, t);
}int QueryMinF(int Now, int l, int r, int lx, int rx) {if (rx < l || lx > r || !Now) return Inf;if (l >= lx && r <= rx) return Tr[Now].MinF;int Mid = (l + r) >> 1;return min(QueryMinF(Tr[Now].l, l, Mid, lx, rx), QueryMinF(Tr[Now].r, Mid + 1, r, lx, rx));
}int QueryMaxT(int Now, int l, int r, int lx, int rx) {if (rx < l || lx > r || !Now) return -Inf;if (l >= lx && r <= rx) return Tr[Now].MaxT;int Mid = (l + r) >> 1;return max(QueryMaxT(Tr[Now].l, l, Mid, lx, rx), QueryMaxT(Tr[Now].r, Mid + 1, r, lx, rx));
}void Solve(int l, int r) {if (l == r) return;int Mid = (l + r) >> 1;Solve(l, Mid);int num = 0;for (int i = l; i <= r; i ++) G[++ num] = Node(i, D[i].y, D[i].t);sort(G + 1, G + num + 1, CmpY);Root = tot = 1;Clear(Root);for (int i = 1; i <= num; i ++) {int x = G[i].x, y = G[i].y, t = G[i].t;if (x <= Mid) {if (F[x] + t <= Lim) Modify(Root, 0, Lim, F[x] + t, x, t);} else {int p1 = t - QueryMaxT(Root, 0, Lim, 0, t), p2 = QueryMinF(Root, 0, Lim, t, Lim);F[x] = min(F[x], min(p1, p2));}}Solve(Mid + 1, r);
}int main() {scanf("%d%d", &N, &T);Lim = T * 2 + 1;for (int i = 1; i <= N; i ++) {int t, s;scanf("%d%d", &t, &s);D[i] = Node(s + t, s - t, t);}D[++ N] = Node(T, -T, T);sort(D, D + N + 1, CmpX);memset(F, 60, sizeof F);for (int i = 0; i <= N; i ++) {if (D[i].x == T && D[i].y == -T && D[i].t == T) End = i;if (D[i].x == 0 && D[i].y == 0 && D[i].t == 0) F[i] = 0;}Solve(0, N);printf("%d\n", F[End]);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！