luogu4125[WC2012]记忆中的水杉树 线段树 拓扑排序 扫描线 set

luogu4125[WC2012]记忆中的水杉树 线段树 拓扑排序 扫描线 set

luogu4125[WC2012]记忆中的水杉树 线段树 拓扑排序 扫描线 set

题目传送门

分析

题目大意：给定平面上若干条互不相交的线段。现在要把这些线段沿着上下左右四个方向移出这个平面。给定一种移动的方案，求这个方案最早在第几步会导致线段相碰，并给出一种合法的方案使得移动过程中不存在任意两条线段相碰。

做法：
先做第二问。不难发现存在一种只往一个方向移动方案。一种暴力的思路是 O ( n 2 ) O(n^2) O(n2)判断两条线段在某个方向上谁先移动谁后移动，建图跑拓扑。

考虑用扫描线+set优化这个建图的过程。考虑往上移动，当前扫描线为 x = x 0 x=x_0 x=x0​。我们可以将与 x = x 0 x=x_0 x=x0​相交的线段按交点从下到上排序。然后顺次连成一条链。

由于线段不相交，所以线段之间的相对顺序不会随着扫描线的移动而改变。所以只需要用 s e t set set维护当前线段的插入，删除和相对顺序即可。

对于第一问，考虑一条线段 l l l的不合法的情况。

我们沿着 x x x轴， y y y轴分别做一遍扫描线，求出拓扑序。

假设它在其移动的方向上的左右边界分别为 s t , e d st,ed st,ed，仅仅考虑后面的线段对前面的线段的影响，那么实际上会冲突就意味着存在某个在其后面的线段，在其移动的方向上的拓扑序小于或者大于 l l l。大于小于要根据移动的方向来定。

倒着做，离散化之后用线段树维护某个区间的拓扑序最值即可。

复杂度 O ( n l o g ) O(nlog) O(nlog)

代码

#include<bits/stdc++.h>
const int N = 2e5 + 10, M = N << 2;
int ri() {char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
}
int pr[N], d[N], q[N], nx[M], to[M], Mn, Mx, tot, tp, n;
int p[N], op[N], lx[N], rx[N], ox[N], ly[N], ry[N], oy[N], x_n, y_n;
void add(int u, int v) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp; ++d[v];}
struct Segment_Tree {#define ls p << 1#define rs p << 1 | 1int tmn[M], tmx[M], mn[M], mx[M];void cmin(int &a, int b) {if(b && (!a || a > b))a = b;}void cmax(int &a, int b) {a = std::max(a, b);}void Tag(int p, int v) {cmin(tmn[p], v); cmax(tmx[p], v);}void Add(int a, int b) {cmin(Mn, a); cmax(Mx, b);}void Work(int p, int L, int R, int st, int ed, int v) {Add(tmn[p], tmx[p]);if(L == st && ed == R)return Add(mn[p], mx[p]), Tag(p, v);int m = L + R >> 1; cmin(mn[p], v); cmax(mx[p], v);if(st <= m)Work(ls, L, m, st, std::min(ed, m), v);if(ed > m)Work(rs, m + 1, R, std::max(st, m + 1), ed, v);}
}T1, T2;
int nw;
struct Point {int x, y;}a[N], b[N];
struct Line {int i; double k, b;bool operator < (const Line &a) const {return k * nw + b < a.k * nw + a.b;}bool operator == (const Line &b) {return i == b.i;}
};
std::vector<Line>in[N], out[N];
void Work(int *l, int *r, int *o, int &tot) {#define F(x) std::lower_bound(c + 1, c + tot + 1, x) - c;#define pb push_backstatic int c[M]; std::set<Line>s;std::set<Line>::iterator it;tot = tp = 0;for(int i = 1;i <= n; ++i)c[++tot] = a[i].x + 1, c[++tot] = b[i].x;std::sort(c + 1, c + tot + 1);tot = std::unique(c + 1, c + tot + 1) - c - 1;for(int i = 1;i <= n; ++i) {l[i] = F(a[i].x + 1); r[i] = F(b[i].x);Line u; u.i = i; pr[i] = d[i] = 0;u.k = (a[i].y - b[i].y) / (double) (a[i].x - b[i].x);u.b = a[i].y - a[i].x * u.k;in[l[i]].pb(u); out[r[i]].pb(u);}for(int i = 1;i <= tot; ++i) {nw = c[i];for(Line u : in[i]) {it = s.insert(u).first;if(next(it) != s.end())add(u.i, next(it)->i);if(it != s.begin())add(prev(it)->i, u.i);}for(Line u : out[i]) s.erase(u);in[i].clear(); out[i].clear();}int L = 1, R = 0;for(int i = 1;i <= n; ++i)if(!d[i])q[++R] = i, o[i] = R;for(int u = q[L]; L <= R; u = q[++L])for(int i = pr[u]; i; i = nx[i])if(!--d[to[i]])q[++R] = to[i], o[to[i]] = R;
}
int main() {n = ri();for(int i = 1;i <= n; ++i) {a[i].x = ri(); a[i].y = ri();b[i].x = ri(); b[i].y = ri();if(a[i].x > b[i].x)std::swap(a[i], b[i]);}Work(lx, rx, ox, x_n);for(int i = 1;i <= n; ++i) {std::swap(a[i].x, a[i].y);std::swap(b[i].x, b[i].y);if(a[i].x > b[i].x)std::swap(a[i], b[i]);}Work(ly, ry, oy, y_n);for(int i = 1;i <= n; ++i)p[i] = ri(), op[i] = ri();int ans = 0;for(int i = n;i; --i) {int u = p[i];if(op[i] & 1) {Mx = 0; Mn = n; T1.Work(1, 1, x_n, lx[u], rx[u], ox[u]);if(op[i] == 1 && Mx > ox[u] || op[i] == 3 && Mn < ox[u])ans = i;T2.Work(1, 1, y_n, ly[u], ry[u], oy[u]);}else {Mx = 0; Mn = n; T2.Work(1, 1, y_n, ly[u], ry[u], oy[u]);if(op[i] == 2 && Mx > oy[u] || op[i] == 0 && Mn < oy[u])ans = i;T1.Work(1, 1, x_n, lx[u], rx[u], ox[u]);}}printf("%dn", ans);for(int i = 1;i <= n; ++i)printf("%d 0n", q[i]);return 0;
}