深圳蒲公英计划 C M N1+N+M是什么

来源：蜘蛛抓取(WebSpider) 时间：2018-10-17 09:04 标签： 计划 C M N

详见李煜东《算法竞赛进阶指南》P172

容斥原理与多重集组合数

警戒：以后类似于没看到强制在線这种傻逼错误千万不要犯啊

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关

而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个

注意，你的算法必须是在线的

苐一行两个整数 n,m 表示有n株蒲公英，m 次询问

接下来一行n个空格分隔的整数 a_iai? ，表示蒲公英的种类

再接下来m 行每行两个整数 l_0,r_0l0?,r0? 我们令仩次询问的结果为 x（如果这是第一次询问， 则 x=0）

最终的询问区间为[l,r]。

输出m 行每行一个整数，表示每次询问的结果

   从之前用分块代替樹状数组求区间和的例子我们可以知道，分块是把一个区间分解成若干个小的区间先通过预处理求出这些小区间的一些值，通过空间换時间达成时空平衡

 代替树状数组的思路很简单，我们把n个数分成T个区间然后对每个区间求出区间和，并且开一个数组add存储整个区间需要加的值。如果我们需要对整个区间进行修改那么把区间所包含的完整的块儿，直接在add数组里加上一个值对不完整的块儿，我们直接暴利枚举在a数组的基础上加上所要加的值。假如说我们的块儿的长度为根号n，那么一次区间加上一个数的操作复杂度就是O（sqrt（n）），当然查询的时候也是O（sqrt（n））了

但是这道题我们求得是区间众数，区间众数是不可以相加减的我们考虑，如果我们已经知道了一個块儿的众数（这个块儿的大小先不说）并且知道了这个块儿所代表的区间内的所有数出现的次数，那么当我们查询lr之间的众数时，這个众数无非两种情况一个块儿内的数，一个是块儿外的小范围的数我们做的就是，每一个块儿带一个数组存储出现的数的次数然後暴利枚举小范围，加到块儿的数组里面然后求出众数，之后再回复原状为了维护我们的信息，假如说我们把n分成t个块儿我们不仅維护这t个块儿，还要维护这些块儿组成的大块儿

   那么我们预处理的复杂度是n*t*t，每次询问的复杂度是n/t所有的询问就是m*n/t。我们让这两个复雜度相等发现此时t≈n的立方根。整个算法是可以A掉题的

   然后最傻逼的就是，我这道题上午就写出了板子一道板子题，花了一天的时間因为我没看到题目输出要求，这个是强制在线题也就是答案与上一个有关系！ 




                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 计划 C M N 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐