#edu2026. 树状数组例题
树状数组例题
树状数组例题
例:P6278[USACO20OPEN] Haircut G
【题意简化】
给定一个长度为 的序列 ,询问对于将所有 高于 的降为 时逆序对个数,需要依次输出 时的答案。
【分析】
如果直接暴力,时间复杂度是 , 会超时。分析一下,对于 , 在 中高于 如果都降低到 的高度,依然会形成逆序对。那么对于 , 形成的逆序对 都是有效的,就是在树状数组 做区间加操作。问题就转化为 “区间修改,单点查询”,可以利用差分求前缀和的方法求出。
参考代码:点击
例:P1972[SDOI2009] HH的项链
【题意简化】给定一个长度为 的序列 ,不同 表示不同的颜色, 进行 次询问,询问区间 内颜色的种类数。
【分析】多次查询区间种类数。
对于所有询问,按照右端点排序,记录每种颜色上一次出现的位置 表示颜色 上一次出现的位置。对于每一个 , 在 位置上 +1
, 在 位置 ,避免同一种颜色统计重复,对于右端点落在 位置的查询区间和,就是这个区间对应的答案。
例:P2163 [SHOI2007] 园丁的烦恼
【题意简化】二维平面上给定 个点,进行 次询问,询问给定一个矩形: 左下角 ,右上角 区域内点的数量。
【分析】二维平面数点问题经典问题。可以先思考一个简单问题,每次只查询 左下角的点的个数 , 可以将点与查询以 排序, 遇到点在对应 位置 ,遇到查询,直接询问 前缀和。(注意 相等的时候,需要将点排在前面)
利用容斥原理,每个询问转变为 个前缀和 。
参考代码:点击
例: P3755 [CQOI2017] 老C的任务
【题意简化】
【分析】二维平面求和,类似与二维平面数点。
学习完毕
{{ select(1) }}
- YES
- NO