题解：CF2185E The Robotic Rush

似乎没看到有人发哈希表做法。

该题有可能卡哈希表常数。

显然每个机器人仅可能被它左边或右边离它最近的尖刺杀死，如果这样的尖刺的确存在的话。将数轴从左向右摆放（即右边是正方向），通过将尖刺排序并进行二分查找，可以在 $O(\log m)$ 的时间里知道第$i$个机器人左边和右边最近的尖刺在哪，也就是这个机器人能够活着移动的范围 $(l_i,r_i)\ (l_i<0<r_i)$（题目数据保证了不会有 $0$）。特别地，对于两端的机器人，可能 $l_i=-\infty$ 或者 $r_i=+\infty$。

根据题意，所有机器人是同步移动的。所以我们考虑，在某一次的移动以后，从最初的状态到现在总的位移 $offset$ 是怎样的？这个位移在一次次移动的过程中，其“痕迹”（所有到达过的点形成的不可重集合）必为包含原点的连续线段。对于这条线段上某一点$x$，初次到达此点时，以此点为活动范围边界的机器人会死，即如果 $l_i=x$ 或 $r_i=x$，则 $i$ 在 $offset$ 初次达到 $x$ 时被杀死。

因此考虑维护 $offset$ 的“痕迹”的边界，即历次 $offset$ 的最小值 $min$ 和最大值 $max$（初始时均为$0$）。每次需要更新 $min$ 或 $max$ 时（即 $offset<min$ 或 $offset>max$），杀死以这个 $offset$ 为活动边界的机器人。因为一个机器人有左右两个边界，其边界可能两次被遇到，但一个机器人只能死一次，所以我们要维护每个机器人的生存状态，杀的时候跳过已经死了的。

为了对于一个 $offset$ 快速查找以它为边界的机器人群，我们可以用一个哈希表来维护这个映射。杀机器人时，因为要排除已经杀过的，所以我们必须遍历以该 $offset$ 为边界的机器人群；但由于一个机器人最多被访问两次（左边界和右边界各一次），杀机器人的总时间复杂度为 $O(n)$。

inline void solve() {
	size_t l, m, n;
	std::cin >> n >> m >> l;
	assert(n && m && l);
	std::vector<int32_t> robots(n), spikes(m);
	std::unordered_map<int32_t, std::vector<size_t>> dying_bots_at_offsets;
	dying_bots_at_offsets.reserve(n << 1); // VERY IMPORTANT!
	for (auto &robot : robots) std::cin >> robot;
	for (auto &spike : spikes) std::cin >> spike;

	std::sort(spikes.begin(), spikes.end());
	for (size_t i = 0; i < n; ++i) {
		size_t p = std::lower_bound(spikes.begin(), spikes.end(), robots[i]) - spikes.begin();
		if (p) {
			dying_bots_at_offsets[spikes[p - 1] - robots[i]].emplace_back(i);
		}
		if (p != m) {
			assert(spikes[p] != robots[i]);
			dying_bots_at_offsets[spikes[p] - robots[i]].emplace_back(i);
		}
	}

	std::vector<bool> is_dead(n);
	auto killAtOffset = [&](int32_t offset) -> size_t {
		auto iter = dying_bots_at_offsets.find(offset);
		if (iter == dying_bots_at_offsets.end()) return 0;

		auto dying_bots = std::move(iter->second);
		dying_bots_at_offsets.erase(iter); // optional

		size_t killed = 0;
		for (auto bot : dying_bots) {
			if (is_dead[bot]) continue;
			is_dead[bot] = true;
			++killed;
		}
		return killed;
	};

	int32_t offset = 0, min = 0, max = 0;
	size_t alive_num = n;
	for (size_t i = 0; i < l; ++i) {
		char oper;
		std::cin >> oper;
		if (oper == 'L') {
			--offset;
		} else if (oper == 'R') {
			++offset;
		} else {
			assert(false);
		}

		if (offset < min) {
			min = offset;
			alive_num -= killAtOffset(offset);
		} else if (offset > max) {
			max = offset;
			alive_num -= killAtOffset(offset);
		}

		std::cout << alive_num << ' ';
	}
	std::cout << '\n';
}

时间复杂度：排序 $O(m\log m)$，确定左右边界 $O(n\log m)$，杀机器人 $O(n)$，处理 $l$ 条移动$O(l)$，因此总的复杂度为 $O((n+m)\log n+l)$。

您可能注意到了：第7行我对哈希表执行了reserve(n << 1)，因为不加这行会TLE。

不同哈希表的通过情况

• 直接使用std::unordered_map：Time limit exceeded on test 14。
• 使用std::unordered_map并reserve(n)：Time limit exceeded on test 14。我一开始误以为哈希表大小上界为$n$。
• 使用std::unordered_map并reserve(n << 1)：Accepted。实际上哈希表大小的上界应为$2n$，因为最坏情况下每个机器人都会贡献$2$个边界值。
• 使用__gnu_pbds::gp_hash_table：Time limit exceeded on test 27。
• 使用__gnu_pbds::gp_hash_table并resize(n)：Time limit exceeded on test 27。
• 使用__gnu_pbds::gp_hash_table并resize(n << 1)：Accepted。
• 使用__gnu_pbds::cc_hash_table：Accepted。
• 使用__gnu_pbds::cc_hash_table并resize(n)：Accepted。
• 使用__gnu_pbds::cc_hash_table并resize(n << 1)：Accepted。

我尚不能对此给出一个足够合理的理论解释Orz。