HDU4819 Mosaic

题目大意

给出一个n*n的矩阵,给出m个询问,每个询问形如x,y,z,表示询问以x,y为中心点的z*z子矩阵的最大值MAX和最小值MIN,输出(MIN+MAX)/2。并将x,y修改为(MIN+MAX)/2(向下取整)。

Solution

支持修改一个数,并询问一个区间中的最大、最小值,可以想到用线段树维护。以前写过把一个二维矩阵分成四块的二维线段树,因为各种原因,它的复杂度很大。所以只能用树套树维护。外层的线段树中,每个节点都维护一棵内层的线段树,就可以做到询问区间。但在外层的线段树上似乎只能单点修改。

代码 

 

2 条评论
  1. Thank you so much for providing individuals with an exceptionally nice opportunity to read in detail from here. It’s usually very sweet and as well , packed with a lot of fun for me and my office mates to visit your site nearly 3 times per week to find out the latest stuff you will have. And lastly, I am usually contented considering the perfect solutions served by you. Certain two facts in this article are unquestionably the most effective we’ve had.

  2. I not to mention my buddies appeared to be reviewing the excellent tactics on your site and before long I got a horrible feeling I never thanked the web blog owner for those techniques. Most of the ladies are already certainly warmed to learn all of them and now have extremely been using them. Thank you for actually being considerably considerate as well as for deciding on such excellent guides most people are really desperate to be aware of. Our sincere apologies for not saying thanks to you sooner.

发表一条评论