[离线+ODT+扫描线+线段树]2022 CCPC 广州 B【Ayano and sequences】题解
题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发现涉及到时间和区间两个维度，并不是很好...
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
题目概述Suffix Automaton解题报告被时限骗了，以为做法是两个 $\log$（空间爆炸），其实只要离线就可以一个 $\log$ 。求出后缀数组后，第 $i$ 个后缀多出来的就是 $[...
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路，我们记录 $pre_i$ 表示 $i$ 上次的出现位置，这样的话对于一个左端点 $L$ ，只有 $pre_i<L...
[单调栈+扫描线+线段树]2020 ICPC 小米 网络选拔赛热身赛 H【Equivalent Prefixes】题解
题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间（ $a_i$ 最小的区间），还有 $[LB_i,RB_...
[扫描线+线段树]Codeforces1435C【Perform Easily】题解
题目概述CF1435C解题报告将 $a$ 排序，令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ，然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ，...
[扫描线]Codeforces853C【Boredom】题解
题目概述CF853C解题报告直接求很麻烦，我们求不满足的个数。对于询问的矩形 $A$ ，我们划分出八个区域： | 0 | 1 | 2 |
-------------
| 3 | A | 4 ...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树，每个节点有颜色，求路径上没有相同颜色的路径个数，每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑，模拟考的时候我疯狂想容斥，我都想到用正解做链了却没想到...
[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解
题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减去一个资源点都没有的子网格个数，把...
