Higher Order Functions

Currying

Haskell中的函数是柯里化（Currying）的，可以看作所有函数都只接收一个参数，而接收两个参数的函数实际上是这个函数接收了第一个参数后返回了一个接收第二个参数的函数，然后用这个函数接收第二个参数，返回最终的结果。比如max函数，它的类型签名是：

基础运算

• + - * / ()：加减乘除
• div：整除
• mod：取模
• True False：布尔值

学习一门新语言之Haskell

前言

之前一直很好奇函数式编程，觉得Haskell挺有意思的，想学学
现在高考完放假了，可以有时间具体学一学了
这里没有Haskell的教程，只有我在学习Haskell时写下的笔记

在使用manim时,对于Text类,会有一些bug,我尝试修复了它们

1. 在shaders分支下无法使用Text类
2. Text文字的stroke边框不完整,导致显示stroke会非常难看
3. 含有空格的Text的空格不在文字内部,而在ORIGIN的位置,导致Transform时会有字符在原位置和ORIGIN之间 反复横跳
4. Text文字的默认大小要比TextMobject大,不容易像TextMobject一样控制大小

这些问题已经通过#1030修复到了manim的master分支中

通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决

主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作

通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add操作,而不容易实现del的情况

通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似 达到del的效果

通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改

比如这道题目,需要实现以下目标

1. 查询$[L,R]$区间内不同颜色画笔的种数
2. 将$pos$处的画笔替换为$color$颜色

达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队

这篇文章来记录一下莫队算法时间复杂度的简单(不严谨)计算

首先分析一下莫队算法的时间复杂度有哪些方面构成

1. 对询问Query数组的排序
2. 区间左指针的移动
3. 区间右指针的移动

题目传送门: 「Luogu P1494」小Z的袜子
一道推公式，后使用莫队 玄学 优化的题目