UVa1472/LA4980 Hanging Hats

题目链接

  本题是2010年icpc欧洲区域赛中欧赛区的H题

题意

  魔法师有 n 顶帽子需要依次悬挂在墙上。每顶帽子在挂好后都会变成一个底在地面上的等腰三角形。帽子分为窄帽子和宽帽子两种。窄帽子底面宽度等于帽尖（即悬挂点）的高度，而宽帽子的底面宽度等于帽尖高度的两倍。如果一顶帽子的帽尖包含在另一顶帽子里（内部或者边界上），它就是不可见的，反之就是可见的。你的任务是计算出悬挂每顶帽子后，可见帽子的数量。注意，如果悬挂点和已有帽子的帽尖重合，或者位于某个已有帽子的内部或者边界上，那么这顶帽子是挂不上的。
  如下图所示，帽尖上的数字代表挂的顺序（1 是最先挂的，7 是最后挂的），帽子 2 和 6 是窄帽子，其他是宽帽子。帽子 3 和 4 挂不上，而帽子 7 挂上之后，帽子1、2 和 7 是可见的。

输入格式

  输入第一行为数据组数 T（T≤30）。每组数据第一行为帽子的个数 n（1≤n≤100 000），以下 n 行每行包含两个整数 xi，yi（xi 是悬挂点的横坐标，yi 是高度）和一个字母 W 或者 N。

输出格式

  对于每顶帽子，输出悬挂后可见帽子的个数。如果挂不上这顶帽子，输出 FAIL。

分析

  对于宽帽子 $x_i,y_i$，如果帽子 $x_j,y_j$ 的帽尖在其内，则$$\{\begin{array}{c}{y}_j\le y_i\\ x_j\ge x_i-(y_i-y_j)\\ x_j\le x_i+(y_i-y_j)\end{array}$$即$$\{\begin{array}{c}{y}_j\le y_i\\ y_j-x_j\le y_i-x_i\\ y_j+x_j\le y_i+x_i\end{array}$$可以发现只需要后两个不等式，因为它俩能推出第一个不等式。

  同样，对于窄帽子 $x_i,y_i$，如果帽子 $x_j,y_j$ 的帽尖在其内，则$$\{\begin{array}{c}{y}_j-2x_j\le y_i-2x_i\\ y_j+2x_j\le y_i+2x_i\end{array}$$
  因此可以对各个帽尖的坐标做这两种变换，将问题转化为区间问题（单点修改以及区间查询）。将每个帽尖坐标做两次变换构成两棵二维区间树（一棵是宽帽子形式、一棵是窄帽子）的离散点，区间树的每个结点维护两个数：宽帽子树的宽帽子总数（或者窄帽子树的窄帽子总数）$s$、可见帽子数 $v$。

  挂宽帽子 $x_i,y_i$ 时，查询宽帽子树区间 $\{\begin{array}{c}\left[y_i-x_i,\infty \right)\\ \left[y_i+x_i,\infty \right)\end{array}$ 内宽帽子总数 $s$ 是否大于 0：$s>0$ 则无法悬挂；$s=0$ 则修改宽帽子树区间 $\{\begin{array}{c}\left(-\infty ,y_i-x_i\right]\\ \left(-\infty ,y_i+x_i\right]\end{array}$内可见帽子数 $v=0$ 再给点 $(y_i-x_i,y_i+x_i)$ 进行修改 $s+1,v+1$，同时修改窄帽子树区间 $\{\begin{array}{c}\left(-\infty ,y_i-2x_i\right]\\ \left(-\infty ,y_i+2x_i\right]\end{array}$内可见帽子数 $v=0$ 再给点 $(y_i-2x_i,y_i+2x_i)$ 进行修改 $v+1$。
  挂窄帽子 $x_i,y_i$ 时，查询窄帽子树区间 $\{\begin{array}{c}\left[y_i-x_i,\infty \right)\\ \left[y_i+x_i,\infty \right)\end{array}$ 内窄帽子总数 $s$ 是否大于 0 再类似处理即可。

  可惜题目数据规模很大，用二维线段树动态开点的话，修改宽帽子树区间 $\{\begin{array}{c}\left(-\infty ,y_i-x_i\right]\\ \left(-\infty ,y_i+x_i\right]\end{array}$内可见帽子数 $v=0$ 以及修改窄帽子树区间 $\{\begin{array}{c}\left(-\infty ,y_i-2x_i\right]\\ \left(-\infty ,y_i+2x_i\right]\end{array}$内可见帽子数 $v=0$ 这里由于要找到每个可见的帽子再进行点修改，时间开销有点夸张，提交会超时。

  上 k-D Tree 的话，整体时间开销小一些，提交仍然超时。考虑到对每顶帽子，进行坐标转换后其实是要查询以某点为左下角的矩形区间然后在查询结果为 0 时修改以此点为右上角的矩形区间内每一个点。可以参照 k-D Tree 的思路将区间树构造成四叉树的形式：每个子区间树首先选择一个点 $p_i$ （取中位数处的点），然后区间内其他点 $p_j$ 按照在点 $p_i$ 的左下$\{\begin{array}{c}{x}_j<x_i\\ y_j<y_i\end{array}$、左上$\{\begin{array}{c}{x}_j<x_i\\ y_j\ge y_i\end{array}$、右下$\{\begin{array}{c}{x}_j\ge x_i\\ y_j<y_i\end{array}$、右上$\{\begin{array}{c}{x}_j\ge x_i\\ y_j\ge y_i\end{array}$四个象限划分成四个子树。由于四个子树内点的坐标大小按象限划分明确，这将给查询操作提供便利，时间开销得到优化，这一版提交AC了。

  官方题解说最优思路是采用优先查找树（Priority Search Tree），整体时间复杂度才$O(n\log n)$，后面实践一把再补上。

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;#define N 100010
long long x[N], y[N], *px, *py; int a[N], rm[N], n, c; bool w[N];bool cmpx(int i, int j) {return px[i] < px[j];
}bool cmpy(int i, int j) {return py[i] < py[j];
}struct {long long x[N], y[N]; int l1[N], l2[N], r1[N], r2[N], f[N], s[N], v[N], p[N], q[N], t;void build(int& o, int l, int r) {if (!o) o = ++t, l1[o] = l2[o] = r1[o] = r2[o] = f[o] = s[o] = v[o] = 0;if (l+1 < r) {sort(a+l, a+r, cmpx);int m = lower_bound(a+l, a+r, a[(l+r)>>1], cmpx) - a;sort(a+l, a+m, cmpy);int c = lower_bound(a+l, a+m, a[m], cmpy) - a;if (l < c) build(l1[o], l, c);if (c < m) build(l2[o], c, m);if (m+1 < r) {sort(a+m+1, a+r, cmpy);c = lower_bound(a+m+1, a+r, a[m], cmpy) - a;if (m+1 < c) build(r1[o], m+1, c);if (c < r) build(r2[o], c, r);}p[q[a[m]] = o] = a[m]; f[l1[o]] = f[l2[o]] = f[r1[o]] = f[r2[o]] = o;} else p[q[a[l]] = o] = a[l];}void build() {l1[0] = l2[0] = r1[0] = r2[0] = s[0] = v[0] = t = c = 0; px = x; py = y; build(c, 0, n);}bool query(int o, int i) {if (s[o] == 0) return false;if (x[i] <= x[p[o]]) {if (y[i] > y[p[o]]) return query(r2[o], i) || query(l2[o], i);return s[o] - s[l1[o]] - s[l2[o]] - s[r1[o]] > 0 || query(r1[o], i) || query(l2[o], i) || query(l1[o], i);} else if (y[i] > y[p[o]]) return query(r2[o], i);return query(r2[o], i) || query(r1[o], i);}void rem(int o) {if (v[o] - v[l1[o]] - v[l2[o]] - v[r1[o]] - v[r2[o]] > 0) rm[c++] = p[o];if (v[l1[o]] > 0) rem(l1[o]);if (v[l2[o]] > 0) rem(l2[o]);if (v[r1[o]] > 0) rem(r1[o]);if (v[r2[o]] > 0) rem(r2[o]);}void qrm(int o, int i) {if (v[o] == 0) return;if (x[i] >= x[p[o]]) {if (y[i] >= y[p[o]]) {if (v[o] - v[l1[o]] - v[l2[o]] - v[r1[o]] - v[r2[o]] > 0) rm[c++] = p[o];rem(l1[o]); qrm(l2[o], i); qrm(r1[o], i); qrm(r2[o], i);} else qrm(l1[o], i), qrm(r1[o], i);} else if (y[i] >= y[p[o]]) qrm(l1[o], i), qrm(l2[o], i);else qrm(l1[o], i);}void add(int i, int d) {if (d) c = 0, qrm(1, i);for (int o = q[i]; o; o = f[o]) ++v[o], s[o] += d;}void remove(int i) {for (int o = q[i]; o; o = f[o]) --v[o];}
} t1, t2;void solve() {cin >> n;for (int i=0; i<n; ++i) {char c; cin >> x[i] >> y[i] >> c; w[i] = c == 'W'; a[i] = i;t1.x[i] = y[i]-x[i]; t1.y[i] = y[i]+x[i]; t2.x[i] = y[i]-2*x[i]; t2.y[i] = y[i]+2*x[i];}t1.build(); t2.build();for (int i=0; i<n; ++i)if (t1.query(1, i) || t2.query(1, i)) {cout << "FAIL" << endl;} else {t1.add(i, w[i]); t2.add(i, !w[i]);while (c--) t1.remove(rm[c]), t2.remove(rm[c]);cout << t1.v[1] << endl;}
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) solve();return 0;
}