区间统计类题目

admin

区间统计问题是信息学奥赛常出的题目，给定一个区间，其中满足条件的子区间。

一起来总结下这些题目：

1、总区间求和，最大值，最小值 这个很简单，其中同时求最大最小还可以递归；
2、区间最大最小值，一般可以使用ST表，线段树， 忠诚(P1816)，
3、区间求和可以考虑前缀和，树状数组
3、长度K区间的最大最小值  一般用单调队列
4、区间线段覆盖问题：
     给定若干线段，求总的覆盖长度  线段的重叠
     给定若干线段，选择最多的线段互不重叠（工作安排问题）
     给定若干区间，用N条线段覆盖他们所有
5、区间上的二分 复制书稿，数列分段II
6、区间上的DP  复制书稿，乘积最大。
7、二维区间问题  最大的正方形， 二维和最大。8、单调栈 ，积水面积，删数游戏

后面这两个涉及到修改，暂时不整理、
8、区间合并问题9、区间填补  道路5019，浇花


how many wrong answer

双指针法，(统计天数，有点像队列)
单指针法， 1042乒乓球 ISBN
有些单指针法有点像堆栈

n*m的矩阵里面每个数字a(i)(j)就是i*j（行号和列号的乘积）,求第k大。

1、P1317 低洼地 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36162
2、P1178 到天宫做客 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35903   
3、P1496 火烧赤壁 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36164
4、P1567 统计天数 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36165

NOIP普及组这几年的第一二题都是区间类的 图书管理员，龙虎斗，公交换乘，求和等

admin

连续区间最大和  两段最大和 环状最大和  二维平面的矩阵最大和

admin

有很多区间的问题是变成线段树，splay，treap等树状结构来做，还有些是变成网状结构图来做。