块状数组,块状链表,分块的简单题及难题

块状数组,块状链表,分块是编程学术界的一种比较重要的算法。

现在稍作解释这三大算法:

块状数组:

块状数组是基于分块思想的数据结构,较基于分治思想的数据结构如线段树、平衡树等效率较低,但通用性更强。在块状数组的基础上加以扩展,就可以得到块状链表。

块状链表:

块状链表是基于分块思想的一种数据结构,在信息学中较为常用。

其优点是做到了时间的平衡掌控

由于其可实现可持续化,并且易于理解,因此深受广大OIer们喜爱。

分块:

分块算法是一种很常见的根号算法,一般它的时间复杂度会带根号。

简单来说,分块算法就是优化过后的暴力

在这里我稍作整理了一些关于这三大分块思想的算法题目,大家可以进行练习~


  1. CF816B - Karen and Coffee
  2. P3870 - [TJOI2009] 开关
  3. P4109 - [HEOI2015] 定价
  4. P4863 - JerryC Loves Driving
  5. P4168 - [Violet] 蒲公英
  6. P1903 - 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列
  7. P3203 - [HNOI2010] 弹飞绵羊
  8. P4345 - [SHOI2015] 超能粒子炮·改
  9. P3707 - [SDOI2017] 相关分析
  10. P3645 - [APIO2015] 雅加达的摩天楼
  11. CF920F - SUM and REPLACE
  12. CF940F - Machine Learning
  13. P4117 - [Ynoi2018] 五彩斑斓的世界
  14. P5692 - [MtOI2019] 手牵手走向明天
  15. P3710 - 方方方的数据结构