hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4819

题意:

给你一个n*n的矩阵, 每个点是一个数字, Q个操作,每次选择一个子矩阵, 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。

 

思路:

显然是一个二维线段树…..

然而菜鸡如我,并没有写过二维线段树啊?

那怎么办呢

一首《凉凉》送给自己

 

 

然而我们还有四叉树2333

2A,写错一个地方。第一次写四叉树,orz

 

然后又写了一个二维线段树的版本,借鉴了kuangbin的写法,改成了自己习惯的代码风格。

果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ

第三个是四叉树的做法,第二个是kuangbin 的 树套树版本的二维线段树

第一个是我改写kuangbin代码之后的代码。

可以看出,四叉树虽然好写好理解一点,但是时间上不太优秀啊….

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz