OI补完计划——Day5离线思想Day5

Day5

{终于补齐了，今天的模拟赛还是各种悲剧。第一题少考虑了一种情况，20，第二题手懒了，没打邻接链表，用邻接矩阵来写SAP，1000个点，再次T掉一个点。第三题是离线加并查集或漂浮法，没想到离线。。。朴素模拟也因为评测机版本问题C掉了，这直接导致了我今天要好好总结一下离线算法了}

先看一下离线RMQ吧，这是一个很好的算法，它的编程复杂度（极低，见过并查集吧）和时间复杂度（O(N*α(N))）和空间复杂度(O(N))都超乎想象啊。思想是这样的考虑将所有的询问一次读入，将他们用链表存下（以右端点为关键字）。然后依次处理，我们考虑RMQ的问题，要求区间最值。那么我们可以从另一种角度来考虑，不断向序列中加入点，然后处理以刚加入点为结尾的询问。加入序列中除下了如下情况：

1   3    40   5    2     13     5   4    2

那么我们观察一下分别以某点开始到当前点的最大值：

40 40  40  13  13   13     5     4   2

我们发现最大值是单调递减的，我们便可以发现序列中的某些值是不会影响到当前节点的区间最值的，这样考虑一下我们可以使用单调栈来存储可能的最值，然后对于询问用二分法找到答案。然后如何使算法进一步优化呢，我们可以考虑单调栈在做什么，不断地删点，而不同区间起点的答案在删点过程中，被删掉的点的答案是和栈中点的值是相同的，之完完全全就是一个并查集嘛。删点就是将栈中点和要插入点合并，询问就是查找一个点所在的集合。然后就各种爽了。。。

以上是经典算法，我们来用离线思想实战解决几道问题。

BZOJ1015（JSOI2008星球大战）

http://61.187.179.132/JudgeOnline/problem.php?id=1015

这道题可以看出是求连通分量的个数，但是会有删点的情况，这将使问题变得复杂难解。如果是加点，那么这题显然可以用并查集来做，那么我们反过来考虑这题呢？如果我们先读入所有要删的点，那么从后往前来就是问题大大的简化了，变成每次添加一个点在询问连通分量的个数。

BZOJ2300（HAOI2011防线修建）

http://61.187.179.132/JudgeOnline/problem.php?id=2300

这题的思想和上题类似，凸包的删点是很难维护（甚至不存在高效算法）的，而加点则可以用平衡树来维护（虽然还是很难写）。但是最起码是一个有效算法，可以完美的解决这道题。但实际上本题数据十分水，每次删掉的不是凸包上的点自然不用管，删掉凸包上的点重新求一边凸包都是可行的。

BZOJ2738（矩阵乘法（梁盾））

http://61.187.179.132/JudgeOnline/problem.php?id=2738

先吐一下槽，本题和矩阵乘法没有半毛钱关系。。。。

一看题就想到了二维线段树套平衡树，或者存在二维划分树？但是就算这种东西写出来并调对了，也会是各种MLE，TLE吧。。。而这道题竟然没有像其他国家集训队的互测题一样强制在线，这就已经暴露了他的算法了。。。。离线。。。。

我们当然要想将矩阵中的所有点排序，但如一个一个点的加入并判断某个询问是否到达k会很悲剧的没时间复杂度到达了O(N^2*Q)。我们就要用一点离线的小技巧了。

我们先插入一点其他的，我们知道块链这种数据结构，它中和了链表和数组的优点，使查询和插入均到达了一个平衡O(sqrt(N))。而我们刚刚的算法就是找到某个询问答案的时间为O(1)（插入到第K个就得到了答案）。而插入的次数却到达了O(N^2)。我们要做的就是平衡他们使总的时间复杂度降低。我们要做的就是将点分块插入，然后统一判断，对到达K值的询问，暴力在刚插入块中找到答案，这样就可以很好地解决这道题了。但以多大的长度（设为size）为数据分块同样是影响问题时间复杂度的重点。我们分析一下本算法的最坏时间复杂度是O(N^2/size*Q+Q*size)。利用均值不等式可以得到当size=N时，时间复杂度会达到最低。但考虑到不同操作的常数问题，算法实现时可多次测试得到最优的划分方案。

再来就放一下今天的第三题吧。。。

【问题描述】

    Fj设计了一个绘画程序，这个绘画程序就是在N(行)*N（列）的方格里，给某些区域各自染上不同的颜色。颜色一共有K种，标号分别是1..K.默认颜色为白色(标号为1)。

    N*N的方格里的最左上的那个格子的编号为(0, 0)。某个格子的编号为(x,y)，这里x是所在格子的行标，y是所在列的列标。

    Fj的绘画程序有三种不同的命令

1）   PAINT 命令：PAINT c x1 y1 x2 y2  给(x1,y1)到 (x2,y2)这个矩形染上C的颜色，不过这种染色不是在整个区域全部染上颜色C，而是在x1,y1染上染上颜色c，其余交错染色，如下图所示，这是一个染上红色的矩形。（注意：白色是底色，并不是染上白色，也就是说白色区域并没有染色。）

 

2）   SAVE命令：SAVE       将当前棋盘的颜色存储起来。

3）   LOAD命令：LOAD x      将棋盘的颜色变为第x次存储的状态。

最初棋盘是纯白色(颜色代码是1),给出M条命令，每条命令肯定是以上三种命令中的一种，问M条命令后，棋盘的状态。

【输入】

第一行三个整数N (1 ≤ N ≤ 1000), K (2 ≤ K ≤ 100 000), 和 M(1 ≤ M ≤ 100 000)意义如题目所示。

 接下来M行，为M条命令。

【输出】

N行*N列的矩阵，每行中整数用单个空格隔开，表示棋盘的颜色状态。

drawing.in

3 4 7

PAINT 2 0 0 1 1

SAVE

PAINT 3 1 1 2 2

SAVE

PAINT 4 0 2 0 2

LOAD 2

PAINT 4 2 0 2 0

drawing.out

2 1 1

1 3 1

4 1 3

【数据范围】

   30% 数据保证 N<=100  M<=4000

做本题前我曾经扫过一眼陈立杰的可持久化的数据结构，因此思维被限制在其中不能自拔。。。

但实际上本题还是没有强制在线，因此离线是王道啊。。。

我们一次读入所有的指令倒序执行LOAD操作也就是不断向上跳到SAVE处，那么显然中间的操作是无意义的，如此不断重复直到，不再出现SAVE和LOAD操作，这样就会跳过许多的无用操作同时是问题简化殆尽，这样无论是漂浮法还是并查集优化染色都可以完美地解决问题了。

【欢迎大家指出文中的不足，我们再作进一步的讨论，如有错误我会及时修改】

【Snow Dancer原创，转载请注明，谢谢】