limohan

本站停用,新站已更换地址
http://limohan.cn/
本站点留作纪念

©limohan
Powered by LOFTER
 

关于搬迁新站limohan.cn

新站地址:http://limohan.cn

至于原因吗。。lofter的功能太少了,尤其没有代码高亮,也没有TEX更不能自定义html.....

综合种种原因,我决定重回老路,博客自行维护。

该博客留作纪念 (使用时长:不到半年。。。)

 

【转载】[洛谷日报第4期]浅谈线段树——Segment Tree

一、简介线段树

ps: _此处以询问区间和为例。实际上线段树可以处理很多符合结合律的操作。(比如说加法,a[1]+a[2]+a[3]+a[4]=(a[1]+a[2])+(a[3]+a[4]))

线段树之所以称为“树”,是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的(包括RMQ、RSQ问题等。


图片来源于互联网。

对于每一个子节点而言,都表示整个序列中的一段子区间;对于每个叶子节点而言,都表示序列中的单个元素信息;子节点不断向自己的父亲节点传递信息,而父节点存储的信息则是他的每一个子节点信息的整合。

有没有觉得很熟悉?对,线段树就是分块思想的树化,或者说是对于...

 

[BZOJ2086/Luogu3503][POI2010] Blocks

Description

给出N个正整数a[1..N],再给出一个正整数k,现在可以进行如下操作:每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后,问最大能够选出多长的一个连续子序列,使得这个子序列的每个数都不小于k。
总共给出M次询问,每次询问给出的k不同,你需要分别回答。

Input

第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。
第二行N个正整数,第i个正整数表示a[i] (a[i] <= 10^9)。
第三行M个正整数,第i个正...