{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。\u003c/p\u003e \n \u003cp\u003e但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。\u003c/p\u003e \n \u003cp\u003e(虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!)\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m1\"\u003e提示一:二分法是宇宙至强之法!(真的么?)\u003c/a\u003e\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示二:线段树不也是二分法么?\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m1\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示一:二分法是宇宙至强之法!(真的么?)\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e虽说小Ho身经百战,但是面对这样一个他从来没有接触过的问题也一时挠头——数据范围的N和Q都在10^6这个级别,这就意味着至少需要一个时间复杂度为O(Nlog(N))才能解决这个问题。\u003c/p\u003e \n \u003cp\u003e“如果我\u003cstrong\u003e对于每个询问都扫描对应的区间,找到最小的值,那么最坏情况和平均情况下都是O(NQ)的时间复杂度\u003c/strong\u003e,无论数据是不是随即生成的,都不是一个很好的选择。”小Ho如是想道:“这就意味着\u003cstrong\u003e我需要事先进行一些预处理,使得一些重复计算的东西不再重复计算,才能够将复杂度降低下来。\u003c/strong\u003e”\u003c/p\u003e \n \u003cp\u003e小Ho暗自点头,随即想道:“那么如果我对于这整个区间维护一个线段树,维护每棵子树中的最小值,是不是就可以完美解决这个问题了呢?”,于是对小Hi说道:“我觉得线段树可以很好的解决这个问题!。”\u003c/p\u003e \n \u003cp\u003e“没有错呢~但是相比于线段树来说,我有一个更为容易事先的算法,你想不想听?”小Hi点了点头道。\u003c/p\u003e \n \u003cp\u003e“更容易实现?就是代码量更小咯?”小Ho作为一个懒病患者自然是很乐意:“快教我!”\u003c/p\u003e \n \u003cp\u003e“其实你利用线段树也就是这样来减少复杂度的——\u003cstrong\u003e先预先计算一些区间的最小值,然后把每个询问都拆成若干个计算了最小值的区间,并且统计这些区间的最小值的最小值,从而得出答案\u003c/strong\u003e的。”小Hi先总结道:“那么其实我可以将统计的区间这样规定——统计\u003cstrong\u003e所有长度为2的非负整数次幂的区间\u003c/strong\u003e。”\u003c/p\u003e \n \u003cp\u003e“整数次幂?也就是长度为1、2、4、8之类的区间咯?”小Ho答道:“我想想……如果我统计的是这些长度的区间的话,用\u003cstrong\u003epre_calc[L, Len]表示左边界为L,长度为Len的区间中的最小值\u003c/strong\u003e——那么对于一个询问[Li, Ri],我只要找到小于这个区间长度的最大的2的非负整数次幂——T,那么\u003cstrong\u003e这个区间中的最小值就是min{pre_calc[Li, T], pre_calc[Ri-T+1, T]}\u003c/strong\u003e咯?”\u003c/p\u003e \n \u003cp\u003e“反应的很快嘛,你看这样对于每一个询问,是不是就可以只用O(1)的时间复杂度就可以作出回答了,而且就只用一条很简单的语句而已。”小Hi笑道。\u003c/p\u003e \n \u003cp\u003e“但是我还不知道怎么求这些pre_calc啊?”小Ho不禁问道。\u003c/p\u003e \n \u003cp\u003e“我先问你,对于所有的i满足1\u0026lt;\u003di\u0026lt;\u003dN, pre_calc[i, 1]是不是很好求?”小Hi反问道。\u003c/p\u003e \n \u003cp\u003e“唔……是的,pre_calc[i, 1]就是标号为i的物品的重量weight_i。”小Ho答道。\u003c/p\u003e \n \u003cp\u003e“那么对于,所有的i, j满足1\u0026lt;\u003di\u0026lt;\u003dN, 1\u0026amp;lt2^j\u0026lt;\u003dN,pre_calc[i, 2^j]\u003dmin{pre_calc[i, 2^(j-1)], pre_calc[i+2^(j-1), 2^(j-1)]}是不是成立的?”小Hi继续问道。\u003c/p\u003e \n \u003cp\u003e“额……将一个区间,分解成两个一半长度的区间,利用已经求出的值进行计算,非常的合理!”小Ho赞叹道:“甚至于只需要一个二维循环就能够计算出来了。”\u003c/p\u003e \n \u003cp\u003e“怎么样!是不是比线段树简单许多呢?”小Hi笑道。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示二:线段树不也是二分法么?\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e“那这又是为什么呢……我感觉这两种方法都是二分区间啊。”小Ho生出一个疑问。\u003c/p\u003e \n \u003cp\u003e“这是由于这道题目的性质决定的啦,这个区间上的值都是已经确定的——\u003cstrong\u003e如果在询问的过程中,这些商品的重量还会发生改变,那么自然就不是我们之前提到的算法——ST算法能够解决的了\u003c/strong\u003e。”小Hi点出了一个要点。\u003c/p\u003e \n \u003cp\u003e“原来是这样,等等我还发现这和求的是最值有关,\u003cstrong\u003e如果求的是和值的话,由于[Li, T]和[Ri-T+1, T]这两段区间可能会有重叠的情况,所以也是无法求解的\u003c/strong\u003e呢!”小Ho很快也找到了另一个问题。\u003c/p\u003e \n \u003cp\u003e“是的呢!所以你现在应该知道了把——充分利用题目的特性,就能够很好的减少你编程的复杂度~当然你还要注意到这两种算法的时间复杂度其实是不一样的哦,但是因为这里的N和Q是一个数量级,所以才不会影响到你的解题方法呢。”\u003c/p\u003e \n \u003cp\u003e“原来是这样!”小Ho点了点头:“那么我去写程序啦!”\u003c/p\u003e \n \u003cp\u003e\u003cstrong\u003eTips:在记录pre_calc[i, 2^j]的时候,不要傻乎乎的就这么存了,事实上只要用pre_calc\u0027[i, j]的格式进行存储就可以了!\u003c/strong\u003e\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e每个测试点(输入文件)有且仅有一组测试数据。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第1行为一个整数N,意义如前文所述。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。\u003c/p\u003e \n \u003cp\u003e对于100%的数据,满足N\u0026lt;\u003d10^6,Q\u0026lt;\u003d10^6, 1\u0026lt;\u003dLi\u0026lt;\u003dRi\u0026lt;\u003dN,0\u0026amp;ltweight_i\u0026lt;\u003d10^4。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e10\r\n7334\r\n1556\r\n8286\r\n1640\r\n2699\r\n4807\r\n8068\r\n981\r\n4120\r\n2179\r\n5\r\n3 4\r\n2 8\r\n2 4\r\n6 8\r\n7 10\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e1640\r\n981\r\n1556\r\n981\r\n981\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。\u003c/p\u003e \n \u003cp\u003e但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。\u003c/p\u003e \n \u003cp\u003e(虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!)\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m1\"\u003e提示一:二分法是宇宙至强之法!(真的么?)\u003c/a\u003e\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示二:线段树不也是二分法么?\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m1\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示一:二分法是宇宙至强之法!(真的么?)\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e虽说小Ho身经百战,但是面对这样一个他从来没有接触过的问题也一时挠头——数据范围的N和Q都在10^6这个级别,这就意味着至少需要一个时间复杂度为O(Nlog(N))才能解决这个问题。\u003c/p\u003e \n \u003cp\u003e“如果我\u003cstrong\u003e对于每个询问都扫描对应的区间,找到最小的值,那么最坏情况和平均情况下都是O(NQ)的时间复杂度\u003c/strong\u003e,无论数据是不是随即生成的,都不是一个很好的选择。”小Ho如是想道:“这就意味着\u003cstrong\u003e我需要事先进行一些预处理,使得一些重复计算的东西不再重复计算,才能够将复杂度降低下来。\u003c/strong\u003e”\u003c/p\u003e \n \u003cp\u003e小Ho暗自点头,随即想道:“那么如果我对于这整个区间维护一个线段树,维护每棵子树中的最小值,是不是就可以完美解决这个问题了呢?”,于是对小Hi说道:“我觉得线段树可以很好的解决这个问题!。”\u003c/p\u003e \n \u003cp\u003e“没有错呢~但是相比于线段树来说,我有一个更为容易事先的算法,你想不想听?”小Hi点了点头道。\u003c/p\u003e \n \u003cp\u003e“更容易实现?就是代码量更小咯?”小Ho作为一个懒病患者自然是很乐意:“快教我!”\u003c/p\u003e \n \u003cp\u003e“其实你利用线段树也就是这样来减少复杂度的——\u003cstrong\u003e先预先计算一些区间的最小值,然后把每个询问都拆成若干个计算了最小值的区间,并且统计这些区间的最小值的最小值,从而得出答案\u003c/strong\u003e的。”小Hi先总结道:“那么其实我可以将统计的区间这样规定——统计\u003cstrong\u003e所有长度为2的非负整数次幂的区间\u003c/strong\u003e。”\u003c/p\u003e \n \u003cp\u003e“整数次幂?也就是长度为1、2、4、8之类的区间咯?”小Ho答道:“我想想……如果我统计的是这些长度的区间的话,用\u003cstrong\u003epre_calc[L, Len]表示左边界为L,长度为Len的区间中的最小值\u003c/strong\u003e——那么对于一个询问[Li, Ri],我只要找到小于这个区间长度的最大的2的非负整数次幂——T,那么\u003cstrong\u003e这个区间中的最小值就是min{pre_calc[Li, T], pre_calc[Ri-T+1, T]}\u003c/strong\u003e咯?”\u003c/p\u003e \n \u003cp\u003e“反应的很快嘛,你看这样对于每一个询问,是不是就可以只用O(1)的时间复杂度就可以作出回答了,而且就只用一条很简单的语句而已。”小Hi笑道。\u003c/p\u003e \n \u003cp\u003e“但是我还不知道怎么求这些pre_calc啊?”小Ho不禁问道。\u003c/p\u003e \n \u003cp\u003e“我先问你,对于所有的i满足1\u0026lt;\u003di\u0026lt;\u003dN, pre_calc[i, 1]是不是很好求?”小Hi反问道。\u003c/p\u003e \n \u003cp\u003e“唔……是的,pre_calc[i, 1]就是标号为i的物品的重量weight_i。”小Ho答道。\u003c/p\u003e \n \u003cp\u003e“那么对于,所有的i, j满足1\u0026lt;\u003di\u0026lt;\u003dN, 1\u0026amp;lt2^j\u0026lt;\u003dN,pre_calc[i, 2^j]\u003dmin{pre_calc[i, 2^(j-1)], pre_calc[i+2^(j-1), 2^(j-1)]}是不是成立的?”小Hi继续问道。\u003c/p\u003e \n \u003cp\u003e“额……将一个区间,分解成两个一半长度的区间,利用已经求出的值进行计算,非常的合理!”小Ho赞叹道:“甚至于只需要一个二维循环就能够计算出来了。”\u003c/p\u003e \n \u003cp\u003e“怎么样!是不是比线段树简单许多呢?”小Hi笑道。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示二:线段树不也是二分法么?\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e“那这又是为什么呢……我感觉这两种方法都是二分区间啊。”小Ho生出一个疑问。\u003c/p\u003e \n \u003cp\u003e“这是由于这道题目的性质决定的啦,这个区间上的值都是已经确定的——\u003cstrong\u003e如果在询问的过程中,这些商品的重量还会发生改变,那么自然就不是我们之前提到的算法——ST算法能够解决的了\u003c/strong\u003e。”小Hi点出了一个要点。\u003c/p\u003e \n \u003cp\u003e“原来是这样,等等我还发现这和求的是最值有关,\u003cstrong\u003e如果求的是和值的话,由于[Li, T]和[Ri-T+1, T]这两段区间可能会有重叠的情况,所以也是无法求解的\u003c/strong\u003e呢!”小Ho很快也找到了另一个问题。\u003c/p\u003e \n \u003cp\u003e“是的呢!所以你现在应该知道了把——充分利用题目的特性,就能够很好的减少你编程的复杂度~当然你还要注意到这两种算法的时间复杂度其实是不一样的哦,但是因为这里的N和Q是一个数量级,所以才不会影响到你的解题方法呢。”\u003c/p\u003e \n \u003cp\u003e“原来是这样!”小Ho点了点头:“那么我去写程序啦!”\u003c/p\u003e \n \u003cp\u003e\u003cstrong\u003eTips:在记录pre_calc[i, 2^j]的时候,不要傻乎乎的就这么存了,事实上只要用pre_calc\u0027[i, j]的格式进行存储就可以了!\u003c/strong\u003e\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e每个测试点(输入文件)有且仅有一组测试数据。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第1行为一个整数N,意义如前文所述。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。\u003c/p\u003e \n \u003cp\u003e对于100%的数据,满足N\u0026lt;\u003d10^6,Q\u0026lt;\u003d10^6, 1\u0026lt;\u003dLi\u0026lt;\u003dRi\u0026lt;\u003dN,0\u0026amp;ltweight_i\u0026lt;\u003d10^4。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e10\r\n7334\r\n1556\r\n8286\r\n1640\r\n2699\r\n4807\r\n8068\r\n981\r\n4120\r\n2179\r\n5\r\n3 4\r\n2 8\r\n2 4\r\n6 8\r\n7 10\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e1640\r\n981\r\n1556\r\n981\r\n981\u003c/pre\u003e \n\u003c/dd\u003e"}}]}