题解 P4169 【[Violet]天使玩偶/SJY摆棋子】
Log_x
2018-02-15 09:54:31
## Solution
- 丢一发 CDQ分治 的解法。
- 先考虑回忆出来的点都在询问的点左下方时：（$A$为询问的点）$$Dis(A, B) = |x_A - x_B| + |y_A - y_B| = (x_A + y_A) - (x_B + y_B)$$
- 则当 $x_B + y_B$ 取到最大值时，$Dis(A,B)$ 有最小值。
- 因此问题被转化为：对于一个询问 $(x, y)$，找到满足时间戳在其前且 $x_i \le x, y_i \le y$ 的点中 $x_i + y_i$ 的最大值。
- 这实际上就是三维偏序，用 CDQ分治 解决。
- 对于其它方位的点，只要把坐标统一进行变换即转变为和上面一样的问题。
- 时间复杂度 $O(n \log^2 n)$。
- 然后交上去发现狂T不止，于是在写代码的时候还要注意一些细节：
- 只有对于右区间的询问，我们才把点加入到树状数组中，不是询问就不加，这里学习了下[dalao的姿势](http://blog.csdn.net/qq_21110267/article/details/44701469)。
- 每次 CDQ分治 前，先把那些肯定不在所有询问点左下方的点剔除。
- 每次都按时间戳重新排序很浪费时间，可把一开始的数组备份下来直接复制过去。
- ~~把 lowbit(i) 用数组存下来竟然挂了~~
- 目前应该是洛谷用 CDQ分治 跑最快的。
## Code
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
namespace inout
{
const int S = 1 << 20;
char frd[S], *ihed = frd + S;
const char *ital = ihed;
inline char inChar()
{
if (ihed == ital)
fread(frd, 1, S, stdin), ihed = frd;
return *ihed++;
}
inline int get()
{
char ch; int res = 0; bool flag = false;
while (!isdigit(ch = inChar()) && ch != '-');
(ch == '-' ? flag = true : res = ch ^ 48);
while (isdigit(ch = inChar()))
res = res * 10 + ch - 48;
return flag ? -res : res;
}
};
using namespace inout;
const int Maxn = 0x3f3f3f3f;
const int L = 1e6 + 5;
int n, m, lx, ly, rx, ry;
int c[L], Ans[L];
inline void CkMax(int &x, int y) {if (x < y) x = y;}
inline void CkMin(int &x, int y) {if (x > y) x = y;}
inline void Clear(int x)
{
for (; x <= ly; x += x & -x)
if (c[x]) c[x] = 0;
else break;
}
inline int Query(int x)
{
int res = 0;
for (; x; x ^= x & -x)
CkMax(res, c[x]);
return res;
}
inline void Modify(int x, int y)
{
for (; x <= ly; x += x & -x)
CkMax(c[x], y);
}
struct Ask
{
int x, y, t; bool f;
Ask() {}
Ask(const int &X, const int &Y, const int &T, const bool &F):
x(X), y(Y), t(T), f(F) {}
inline bool operator < (const Ask &a) const
{
return x <= a.x;
}
}q[L], p[L], a[L];
inline void CDQsolve(int l, int r)
{
if (l == r) return ;
int mid = l + r >> 1;
CDQsolve(l, mid); CDQsolve(mid + 1, r);
int j = l;
for (int i = mid + 1; i <= r; ++i)
if (!p[i].f)
{
for (; j <= mid && p[j].x <= p[i].x; ++j)
if (p[j].f) Modify(p[j].y, p[j].x + p[j].y);
int tmp = Query(p[i].y);
if (tmp) CkMin(Ans[p[i].t], p[i].x + p[i].y - tmp);
}
for (int i = l; i < j; ++i)
if (p[i].f) Clear(p[i].y);
merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, q + l);
for (int i = l; i <= r; ++i) p[i] = q[i];
}
inline void Delete()
{
rx = ry = m = 0;
for (int i = 1; i <= n; ++i)
if (!p[i].f) CkMax(rx, p[i].x), CkMax(ry, p[i].y);
for (int i = 1; i <= n; ++i)
if (p[i].x <= rx && p[i].y <= ry) q[++m] = p[i];
for (int i = 1; i <= m; ++i) p[i] = q[i];
}
int main()
{
n = get(); m = get(); int k, x, y;
for (int i = 1; i <= n; ++i)
{
x = get() + 1; y = get() + 1;
p[i] = Ask(x, y, i, true);
CkMax(lx, x); CkMax(ly, y);
}
while (m--)
{
k = get(); x = get() + 1; y = get() + 1;
++n; p[n] = Ask(x, y, n, k & 1);
CkMax(lx, x); CkMax(ly, y);
}
for (int i = 1; i <= n; ++i) a[i] = p[i];
memset(Ans, Maxn, sizeof(Ans)); ++lx; ++ly;
Delete(); CDQsolve(1, m);
for (int i = 1; i <= n; ++i)
p[i] = a[i], p[i].x = lx - p[i].x;
Delete(); CDQsolve(1, m);
for (int i = 1; i <= n; ++i)
p[i] = a[i], p[i].y = ly - p[i].y;
Delete(); CDQsolve(1, m);
for (int i = 1; i <= n; ++i)
p[i] = a[i], p[i].x = lx - p[i].x, p[i].y = ly - p[i].y;
Delete(); CDQsolve(1, m);
for (int i = 1; i <= n; ++i)
if (!a[i].f) printf("%d\n", Ans[i]);
return 0;
}
```