NGC5457's Site

两个等号

作者：

NGC5457

在

,

$0.0\div 0.0=?$

我们建一个凸包。

struct block {
	line g[S], *f; int t, n, m;
	inl void build () {
		// k's of lines in [f, f + n) should be non-increasing.
		m = t = 0;
		for (int i = 0; i < n; ++i) {
			const auto &p = f[n - i - 1];
			if (p.b == -INF) continue;
			while (m > 1 && (p.k == g[m-1].k ? p.b > g[m-1].b : inter (g[m-1], g[m-2]) >= inter (p, g[m-1]))) --m;
			g[m++] = p;
		}
	}
	inl ll operator () (ll x) {
		// x's input should be non-decreasing.
		while (t + 1 < m && g[t] (x) <= g[t + 1] (x)) ++t;
		return t < m ? g [t] (x) : -INF;
	}
};

本题中保证了 $[f,f+n)$ 区间中的直线斜率不增，因此构建下凸包可直接倒序插入单调栈。

但很遗憾，截距 $b$ 不是互不相同的。这将导致可能插入两条完全相同的直线——p.b > g[m-1].b。于是后方弹出时inter (g[m-1], g[m-2])返回nan，建出的凸包是错的。

所以应该改成p.b >= g[m-1].b。

new[], delete[]

我们将树作长链剖分。这棵树的节点在 $[0,2n)$ 范围内，我们还钦定 $2n$ 是虚拟根节点。存储时我们令 $x$ 的指针 $f(x)$ 指向重儿子 $y$ 的指针减一，也即 $f(x)=f(y)-1$。在链的末端 $z$ 用 operator new[] 申请大小是 $l+1$ 的数组，并令 $f(z)$ 是该数组的首位置指针 $+l$。因此，直接对于每条链的链顶节点 $x$ 施 delete[] f[x]，就能释放这条链占用的空间。

for (int x = 0; x < n<<1; ++x)
	for (int v = head[x]; ~v; v = nxt[v])
		delete[] f[v];
delete[] f[n<<1];

我们写了 $<$ 而非 $\leq$，没有删除 $2n$ 的所有轻儿子的数组。不幸，这个过程会被调用约 $500$ 次，而 $n$ 在 $10^5$ 级别。我们成功地占用了多达 $4\text{ GB}$ 的空间，并因此少了 $20\text{ pts}$。

改进的长剖写法

使用静态数组空间而非堆分配每个数组。例如 int arr[N<<1], *pt = arr，其中 $N$ 是 $n$ 的最大值；并将每个 new int [n] 替换成 pt; pt += n。

更多文章