ZigZagK的博客
[后缀数组+离线+扫描线+线段树二分]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$ 个格子有资源点,问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化,那么就是用总方案数减去一个资源点都没有的子网格个数,把...