题解 P3827 【[NOI2017]分身术】
声明：
1.这是一篇云题解。这个方法看起来是可做的，但它是如此地麻烦以至于我不想实践。
2.写这篇题解的原因是这道题一直没人写题解。
首先分析题目。
我们有一个n个点的点集，接下来有m次查询。
每次查询要求出其中n-k个点组成的点集的凸包面积。
每次不被取的k个点由上一次的运算结果取模得到，要求解法在线。
观察数据，前20分用裸的凸包就能直接做。
后面的数据n很大而k很小。
不难想到一个性质：
如果我们称点集的凸包为第一层凸包，点集减去第一层凸包后剩下来的部分的凸包为第二层凸包，点集减去前i层凸包后剩下来部分的凸包为第i+1层凸包的话。
那么，点集减去k个点之后剩下来的部分的凸包上的点应当由前k+1层凸包上的点组成。
（证明应当是容易的，但我们也可以简单地脑补一下：移除一个点最多也只会让我们进入更深一层的凸包）
以下是解法：
首先，预处理出前k+1层凸包。直接做k次凸包是nklogn的。
我们似乎有办法做得效率更高（在下一层当中利用上一层的运算结果）但是没必要。
在预处理之后随便选择一个位于k+1层凸包内部的点O作为我们的原点。
然后，对于每次询问：
我们先按照这k个点的所在凸包层排个序，同一层凸包上的点则按照它到O点的连线和x轴的夹角排序。
这一步是nklogk。
于是，我们丢掉了一些不在前k个凸包层上的点，并且，我们可以方便地找到在同一个凸包层上连续排列的点。
接着，我们按照凸包层从外到里的顺序依次处理每一层的删点。
对于当前正在处理的凸包层上每一段要删的点，我们需要查找下一个凸包层上会因此暴露出的点，并求出面积的变化量。
查找可以通过二分来做，至于面积的变化量，见下图。
我们损失了O-A5-A1-A2-A3这一块，并得到了O-A5-B1-B2-A3这一块。
只要预处理凸包上每条边和O组成的三角形的面积，并预处理前缀和，面积变化量可以O(1)得到。
在第一层处理完后，对于下一层继续做类似的处理。
但是，从第二层开始，有一个额外需要处理的地方：
还是以我们这张图为例。如果我们要删的点是A1，A2，B1和B4，在删去第一层的点后，暴露出B1和B2，但在删去B1之后，同一层的B4被暴露并被删去了。
（好吧，在图上A5，B4和B2看起来就在一条线上，但我们就当B4在稍微外面一点的位置，我懒得重画了）
我们的处理方式还是查找到最终暴露的位置并求出面积差。
之后对下一层做类似的处理。
暴露点这事情最多发生k次，每次我们要做logn的二分查找。
这里的复杂度是mklogn。
以上内容合起来差不多是(n+m)klogn，三亿，3秒时限，看着勉强能过。
如果超时，说明预处理部分“我们似乎有办法做得效率更高但是没必要”是错的。