解题思路

这个题还是挺巧妙的。首先我们要明确一下题目中的操作。

第一种操作是单点更新。第二种操作是查询从 0 号结点（树根）开始且必需经过 x 号结点的路径上，数值和最大是多少。

接下来我们先根据第二种操作来把题目要求进行一些转化。既然是要求路径上数值和最大，那么可以先找到可能的路径有哪些.很容易看出可能的路径肯定是 0 到 x 或 0 到 x 的子结点。我们可以在输入完成后将 0 到任意结点的路径数值和都预处理出来，并用 DFS 序处理结点在数组中的分布以使子树结点连续。这样第二种操作就转化成了一个区间查询最大值的操作，我们可以用线段树来实现。

第二种操作分析完后，我们再回头来看第一种操作，它要求实现单点更新。在上一段我们已经通过建模得到了一个保存路径数值和的数组，一旦树上某个结点的数值更新，就意味着它和它的所有子结点到 0 的路径数值和都要更新，而他们的改变量都是一样的，因此我们计算出这个结点的改变量，就可以应用线段树区间更新来对所有受影响的点都进行同步更新。这样就实现了第一种操作的需求。

解题思路

首先将所有有怪物的坐标编号，作为 DLX 矩阵的列，然后将所有攻击区域以选定的某个顶点坐标编号，作为 DLX 矩阵的行。这样本题就转化成了求最少的行数（即攻击次数）使得所有列（即怪物）都被覆盖，而且由于题目允许同一个位置被多次攻击到，这里我们使用 DLX 的重复覆盖算法来解决这个问题。

解题思路

此题是解异性数独，代码写起来比较繁琐。

首先按照题意求连通块，转化为普通数独。然后用正常求解数独的 DLX 精确覆盖算法即可解决。

另外应注意一旦计算出多解时要及时返回，防止超时。

解题思路

单调栈的基础应用。我们以矩形高度为单位建立一个单调不降的栈，每次输入一个新的矩形高度 h 时，如果新的高度比栈顶高度低，则一直 pop，并累计 pop 出的元素的宽度，每次 pop 我们都可以看做得到一个高度为 h，宽度为累计总宽度的一个矩形（可以看做是把这段的所有矩形高度都削减为 h），用它的面积更新答案。pop 结束后将我们最终得到的新矩形入栈即可。

解题思路

题面中提到后面的人可以找前面的是朋友的人夹塞，让朋友帮忙办理业务，朋友的办理时间会累加。这个过程可以看作一个插队的过程，即把自己插到朋友的后面。由于朋友帮自己办业务是紧接着他自己刚办完的业务连续办理的，所以自己插在朋友后面和让朋友累加办理时间是等价的。

因此我们可以使用队列模拟，每次 pop 出队首，表示此人已办理完毕。接下来找一个人放到队列中作为下一个要办理的人。而下一个的人选是有要求的，即优先寻找一个到达时间不晚于自己离开时间的朋友，让他排在自己后面（插队），如果找不到则按原顺序找自己后面的第一个人，让他排在自己后面。这样不断循环并累加等待时间，直到队列为空即可。