网格照明：给定具有灯坐标阵列的NxN网格。每个灯都为x轴上的每个方块，y轴上的每个方块以及位于对角线上的每个方块提供照明（想象国际象棋中的女王）。给定一组查询坐标，确定该点是否被点亮。问题在于，在检查查询时，与该查询相邻或关闭的所有灯都将关闭。变量/数组的范围大约为：10 ^ 3 <N <10 ^ 9,10 ^ 3 <灯<10 ^ 9,10 ^ 3 <查询<10 ^ 9
好像我可以得到一个而不是两个。我试图将其降低到对数时间，但我似乎无法找到解决方案。我可以减少空间复杂度，但事实并非那么快，指数。我应该把注意力放在哪里，速度还是空间？另外，如果您对如何解决此问题有任何意见，请进行评论。
对于一辆汽车来说，快速行驶或者在一点点燃料上走得更远？这取决于具体情况。
这是一个提案。
首先，请注意，您可以使用第一个点作为nw-se和ne-sw的“原点”，对输入所喜欢的所有对角线进行编号。通过这一点的对角线都编号为零。 nw-se对角线在例如东北方向上增加每像素，并且向西南方向减小（负）。类似地，ne-sw在例如ne-sw中增加。西北方向和东南方向减少（负）。
给定原点，可以很容易地编写从（x，y）坐标到相应对角线数的常量时间函数。
现在每组灯坐标自然与4个数字相关联：(x, y, nw-se diag #, sw-ne dag #)。您不需要显式存储它们。相反，您需要4个地图xMap，yMap，nwSeMap和swNeMap，例如，xMap [x]生成所有灯坐标列表，其中x坐标为x，nwSeMap [nwSeDiagonalNumber（x，y）]生成所有列表对角线上的灯和其他地图类似。
给定一个查询点，查找相应的4个列表。从这些中可以很容易地处理相邻的方块。如果任何列表长于3，则删除相邻的正方形不能使其为空，因此查询点将亮起。如果它只有3或更少，那么它是一个恒定的时间操作，看它们是否相邻。
此解决方案要求输入点以4个列表表示。由于它们需要在一个列表中表示，因此您可以认为该算法仅需要相对于输入的恒定空间因子。 （即与mergesort相同的成本。）
对于4个哈希表查找，每个查询点的运行时间预计是恒定的。
没有太多麻烦，这个算法可以拆分，因此如果灯柱的数量很大，它可以减少地图。
但是在一台大机器上运行它可能就足够了。有了十亿个灯泡和精心的数据结构选择，在C等无盒式结构语言中实现每个灯泡24个字节并不难。所以~32Gb RAM机器应该可以正常工作。使用多个线程构建映射需要一些同步，但只执行一次。查询可以是只读的：不需要同步。一台不错的10核机器应该在不到一分钟的时间内完成10亿次查询。
有一个非常简单的答案是有效的
这工作正常，但尝试10000 X 10000网格时大小限制失败