2021.10.07pm

2024-02-06 11:48:40

2021.10.07PM

B是最简单的，反而没做（wu）

~~可能水，一定菜~~

据说是啥切比雪夫距离，但考试的时候咱也不会啊，就只能乱搞了。
首先，可以发现两点之间距离定义为 \(max(\left| x_i-x_j \right|,\left| y_i-y_j \right|)\)
由于这个地方有个 \(max\) 非常难搞，而且里面又是一个绝对值。
首先考虑把 \(max\) 拆开
通过对类棋盘的题的联系，我抓住了这两条直线，而这也是至关重要的地方。
这两条直线把它分成了四个象限，而每个象限由于斜率影响，能直接比较出 \(\Delta y\) 和 \(\Delta x\) 。
我们进行按照常规坐标系命名象限。
对于第一象限有 \(x+y>N,x-y>M\) ，第二象限有 \(x+y>N,x-y<M\),三四象限类似。
而第一三象限，显然有 \(\Delta y < \Delta x\) ，而二四象限有 \(\Delta x < \Delta y\)。
同时，第一象限中 \((x+y+x-y)>M+N=2*x\) ，第三象限 \((x+y+x-y)<M+N=2*x\)，第二象限中 \((x+y-(x-y))>M+N=2*y\)，第四象限中 \((x+y-(x-y))<M+N=2*y\)。(~~其实看图很容易得出来~~)
那么对于每个点分别计算每一块的大小就行,为了更快计算,显然排序+前缀和乱搞就行。由于我考试的时候因为树状数组学魔障了套了个树状数组扫描线，其实没有必要，直接离线二分查找就行·····
由于写得实在是太丑而且三颗树状数组调了半小时改了计算方式，所以就不贴具体实现了······
~~有搞随机数整过去的~~

这道题做法花样多得很，这里讲一个\(O(n\log n)\) 的算法。
首先，我们预处理处每个人要上天堂需要的高度。（脚底下要踩多高。~~人上人~~），并进行升序排列。(显然需要帮助最多的只能先离开)
然后处理出后缀和，以判断每个人是否能上天堂。
从 \(1\) 到 \(n\) 依次判断能不能上天堂，能上就先塞进去。而对于目前上不了天堂的，由于我们只关心上天堂人数，而不关心谁上去，所以如果拉一个人下来这个人可以上天堂就把这个人送进天堂，而出于贪心，我们会把最高的人拉下来（维护一个堆），垫在最底下；同时最高的人都不能推该人上天堂，那只能把该人垫在最底下。

这道题属于是把两道题混一起了。前半部分是Buy Tickets（POJ），后半部分是最长上升子序列优化。
前半部分由于最后一个的位置是确定的，而倒数第二个位子也是要求满足前面有a[i]个空位，从后往前状态是明确的，所以从n到1依次加人，维护空位用树状数组+二分（非常可恶的是 \(vector\) 也能过）。这里放一道板题。[SHOI2013]发牌
后半部分我记得有一些高级的优化，但是咱不会，现想只会用线段树维护区间最大值。但是！！！！这里找的前缀区间最大值。所以，可以用树状数组 。\(树状数组是前缀的KING\) 。我们只需要把维护前缀和改成维护前缀最大值，还是用\(lowbit\) 实现。
给大家看下效率对比：
第一名是某不知名巨佬，第二名是两个树状数组，第三名是树状数组+线段树。从时间和空间和码量来说，\(树状数组YYDS\)

\(\cal {Made} \ {by} \ {YuGe}\)