ZigZagK的博客
[珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛(5)1001【Pandaemonium Asphodelos: The First Circle (Savage)】题解
题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色,所以我们可以考虑用set维护所有的颜色相同的线段,然后每次操作就是对set中的线段进行分裂以及合并,复杂度分析和...
[随机化+线段树维护凸包+最小圆覆盖]2022“杭电杯”中国大学生算法设计超级联赛(3)1006【Dusk Moon】题解
题目概述HDU7167解题报告被队内计算几何选手演了😡,本来写个最小圆覆盖就过了。首先很显然 $n$ 个点的最小圆覆盖和这个 $n$ 个点求完凸包之后的最小圆覆盖是一样的。而且数据保证随机,那么...
[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解
题目概述Cut解题报告这题思路是不难的,但是如果没写过类似的就会巨难写(细节比较多)……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列(正序或者倒序...
[矩阵乘法+线段树]Codeforces1701F【Points】题解
题目概述CF1701F解题报告对于 $x$ ,设 $[x-d,x-1]$ 上共有 $cnt$ 个点,那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(...
[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解
题目概述Paimon Segment Tree解题报告首先肯定考虑离线,把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序...
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
题目概述Suffix Automaton解题报告被时限骗了,以为做法是两个 $\log$(空间爆炸),其实只要离线就可以一个 $\log$ 。求出后缀数组后,第 $i$ 个后缀多出来的就是 $[...
[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解
题目概述xay loves sequence解题报告先对数组差分,令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ,所以不难发现...
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题,定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前...
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路,我们记录 $pre_i$ 表示 $i$ 上次的出现位置,这样的话对于一个左端点 $L$ ,只有 $pre_i<L...
[线段树维护DP]Codeforces1479B【Painting the Array】题解
题目概述CF1479B1 & CF1479B2解题报告在本算法下,B1和B2其实没有很大区别,所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i$ 放了 $0/1$ 颜色,并且另...