BZOJ 2648: SJY摆棋子 (动态kd-tree,插入,曼哈顿距离,输入挂)

Description

这天,SJY显得无聊。在家自己玩。在一个棋盘上,有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子,输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output


1
2
其实就是BZOJ2716 的双倍经验题
写出来是因为,这道题要加输入挂才可以过orz

 

poj 1964 City Game(单调栈,输入挂)

poj 1964

题意:n*m的maze,由’R’和‘F’组成,现在要求找到面积最大的矩形,使得矩形中所有格子都是’F’。

思路:单调栈…一开始神tm tle….复杂度没问题啊。。。

结果看到有人说这题由于数据量比较大。。。scanf会超时。。。所以要用输入挂。。。。。getchar什么的。。。

poj竟然也卡读入。。。人性呢。。。。

改了输出以后再交wa了。

发现想错了,我是写了从(i,j)到两个方向能到的最大距离。。但是这样写有些点上的情况是没有考虑到的。。比如如果(i+1,j+1)上的点是’R’,实际上是不可以构成l*r的矩形的(l>=2&r>=2)。。。但是我这样做无法体现。

改了下,变成:

仍然对于每行做一次单调栈,预处理出点(i,j)能往右的最远距离a[i][j]。

然后观察一下。。。如果我把每一列分别看成x轴,那a[i][j]不就是矩形的高度了吗。。。

那我要求的不又变成了最大矩形面积了吗。。。

于是接下来对于每一列,做上下两个方向的单调栈得到(i,j)上下能延伸到的最远距离。

(i,j)点所在的矩形面积就是 (r[i][j]-l[i][j]+1)*a[i][j];

再交,A了