华师一附中OI组

标题: 区间统计类题目 [打印本页]

作者: admin 时间: 2018-7-3 16:44
标题: 区间统计类题目
区间统计问题是信息学奥赛常出的题目，给定一个区间，其中满足条件的子区间。

一起来总结下这些题目：

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 时间: 2020-3-8 19:34
连续区间最大和两段最大和环状最大和二维平面的矩阵最大和

作者: admin 时间: 2020-3-15 18:26
有很多区间的问题是变成线段树，splay，treap等树状结构来做，还有些是变成网状结构图来做。

欢迎光临华师一附中OI组 (http://hsyit.cn/)