AtCoder ABC457-E 复盘:区间并集判定、结构分类与离线树状数组
一道关于区间并集精确覆盖的复盘:将“两块布恰好覆盖询问区间”抽象为两个区间的并集判定,并将合法结构拆分为左右拼接与完整区间加内部区间两类,分别使用端点分组二分和离线树状数组完成查询。
一道关于区间并集精确覆盖的复盘:将“两块布恰好覆盖询问区间”抽象为两个区间的并集判定,并将合法结构拆分为左右拼接与完整区间加内部区间两类,分别使用端点分组二分和离线树状数组完成查询。
从洛谷 P1637 三元上升子序列出发,推广到 SPOJ INCSEQ 的长度 k 严格上升子序列计数问题,复盘分层动态规划与树状数组优化的通用做法。
复盘逆序 k 倍对问题,从普通逆序对模板出发,分析判断条件变化对查询边界与离散化集合的影响,并总结树状数组模板改造的关键思路。
复盘洛谷 P8613 小朋友排队问题,从冒泡排序与逆序对的关系出发,分析如何用树状数组统计每个元素参与的逆序对数量,并总结重复身高下按个体粒度维护答案的重要性。