Note: Author is using: As the image shows, some proxy providers will provide some nodes specifically dedicated to downloading task, with lower ratio but lower rate limit (10Mbps in image above). This post demonstrates how to use Load Balance proxy group feature in clash core to download files using several such “download nodes”, effectively bypassingContinue reading “Clash Load Balancing to Bypass Speed Limit”
Category Archives: Techs
Git LFS
Enable LFS Install & Track First of all, install lfs for git using following command: Then add track of large files using lfs: Note that the command above will also update .gitattributes file automatically. Migrate Steps above will only handle future large files. To migrate large file to LFS storage for previous commits, we couldContinue reading “Git LFS”
About GPG
For GPG basic concepts, check out this blog post on Median, which well explained what GPG is and the basic practice is about it. Sign Content Here we use Kleopatra on Windows to demonstrate how to sign content using its Notepad feature. As shown above: Sign Commit Using Git Set Up GPG Sign for GitContinue reading “About GPG”
A Simple Image Hosting Solution Using FTP
Previously trying to use NextCloud and webdav as the way to upload and manage images, but it turns out that deal with share links of those images in NextCloud is not a easy thing to do, so I started to think another way. I found this project on GitHub called PicGo, which allows user toContinue reading “A Simple Image Hosting Solution Using FTP”
Gitea – Self-Hosted Git & CI/CD Tools
This article is about my deployment experience of Gitea, a self-hosted GitHub like code hosting service which also support CI/CD pipeline workflows like GitHub Action. Why I Need It Recently, I was searching for a way to host Obsidian vault on the Internet. There is an official way to achieve this using Obsidian Publish, however,Continue reading “Gitea – Self-Hosted Git & CI/CD Tools”
Simple Callback Function In C++
This article will discuss the basic practice of using callback functions in C++ Function Type To use function type as parameter, it’s recommended to use functional library to define function type: In the code snippet above: Use With Lambda It’s recommended to use Function Type with Lambda Expression: For more info about the C++ LambdaContinue reading “Simple Callback Function In C++”
Segment Tree
Theorem Some diagrams and contents are based on Segment Tree – Algorithms for Competitive Programming. A segment tree should be a binary tree like the one below, additionally, we could proof that Segment Tree should NOT have any node with degree 11. Based on the property of binary tree, we can calculate the index ofContinue reading “Segment Tree”
Lambda Expression in C++
Lambda表达式是编程中很实用的工具,作为热门的,最受欢迎编程语言之一(大概?),C++11及其以后版本,也提供了对lambda表达式的支持,下面让我们逐步学习和了解C++中的Lambda表达式吧 首先我们先看一个lambda表达式的使用例子: 观察得到,C++ lambda表达式基本结构如下: 接下来我们将逐个部份进行介绍。 Capture Clause 首先是第一部份[]。这一部份被称之为捕获语句(Capture Clause)。在这一部份,你可以捕获lambda声明时范围内的变量。你可以在周围环境中捕获需要的变量,同时可以选择捕获类型为值传递还是引用传递。 默认情况下,Capture语句中捕获的变量将会以值传递形式传递。 需要注意,配置默认捕获模式将会将周围环境的所有变量暴露给lambda表达式。如上述代码,lambda c和d均设置了默认Capture设置,这种情况下,周围环境的所有变量都将会被Capture,c和d可以各自依照自己设定好的默认捕获模式访问到num2,但是a和b不能访问到num2。 同时,lambda表达式初始化时,也允许进行赋值操作,请看下面的代码。 如上述代码,我们可以在lambda表达式的 Capture Clause 部分声明新的变量。新的声明变量同样可以是值传递或者引用传递。需要注意的是,在 Capture Clause 声明变量时,我们无需显式指定变量类型,lambda表达式会自动推断其类型(如上述代码中,refToC自动被推断为 int & 类型) 还有一个需要注意的点,默认情况下,Capture Clause 中捕获和声明的所有变量将会以const形式进行传递。也就是说lambda body中,默认不可以对 Capture Clause 中的变量进行更改。如果您想在 lambda body 中对 Capture Clause 中的值或者引用进行更新或修改,请在参数列表,函数体前加上mutable关键字。
An Approach to Implement Log2 Lower Bound Function
If we consider the binary representation of numbers, we could find that the result of log2(n)\log_2(n) is actually related to the position of the first appearance of 11 in the binary bits. Let’s see some example below: For any positive integer nn, we have the following relationship:
Sparse Table
ST表,全称 SparseTable,也叫做稀疏表。是用来解决区间和和区间最大最小值问题的一种工具。其实推广开来,其可以用来解决任何可重复贡献(associative)问题。 使用条件 可重复贡献问题 ST表要求其处理的问题必须具有“可重复贡献”这一特征。具体是什么意思呢? 假设有操作F,使得其满足下列关系: 则称F符合可重复贡献问题的特征。 如图,不难发现max()最大值函数就符合可重复贡献问题的特征;读者可以自行验证,sum(),min()等函数都符合这个特征,这也证明了ST表可以解决最大最小值以及区间和等问题。 元数据可不能改变噢 在使用ST表解决问题时,我们必须确保所有的查询结束前,ST表所对应的元数据都不改变。 有些数据结构(比如线段树)在元数据更新之后(比如原来的数组中,某个数值由3变成了5),可以有对应的事件复杂度比较低的方法对结构进行更新,以达到一边更新一边查询的效果。ST表则无法提供类似的方法,所以确保你的问题中没有要求在查询期间动态调整元数据的要求。 SparseTable意义与使用 接下来,我们采用由表及里的过程,先了解ST表的意义以及使用方法,之后再来说明如何生成ST表。 一些准备——向下取整的Log2函数 由于SparseTable的特性,无论是根据数据生成ST表,还是得到ST表后对数据进行查询,都会比较频繁的用到向下取整的log2函数,所以特地说明。我们对于向下取整的log2运算稍加分析,可以得到log2(x)向下取整的具体意义是: 对于某一个数N,返回可能的最大的数字n,使得2的n次方小于等于N,且2的n+1次方必定大于N。 比如对于7,log2(7)向下取整为2,2的2次方不超过7,但可以保证2的3次方一定大于7(8>7)。 了解了这个之后,让我们来看看SparseTable如何快速解决规模庞大的可重复贡献问题吧~ ST表中数据的意义 我们接下来选择一个经典的可重复贡献问题——区间最大值问题,作为示例。 假设我们有一个数组 {3, 2, 1, 4, 5, 9, 7}, 其数据元素个数为7,要求必须在非常低的事件复杂度内,查询某个特定区间(比如从下标0到下标5)的最大值。此时,如果直接循环求解,会导致复杂度随着查询区间长度不断增高,这就是ST表登场的时候啦。 如上图,对数组进行处理之后,就可以得到下方的二维数组,也就是我们大名鼎鼎的SparseTable——ST表。那么问题来了,图中ST表中的数据,到底具有什么含义呢? 首先需要知道的是,ST表正常情况下使用一个二维数组st[idx][pow]来储存。下面对这个二维数组每一个位置元素的意义做出解释: 例如,对于区间最大值问题,假设原数组为arr,处理后得到的ST表中,st[1][2] = 5,则说明:原数组,从下标为1开始,长度为2^2=4的区间内,最大值是5。 特定区间的查询 知道了ST表的数据的意义,我们就可以着手解决特定区间查询问题。 这里需要注意的是,虽然ST表可以解决不同的可重复贡献问题,但是其在面对不同的可重复贡献问题时,最优查询方式可能有一定的区别。接下来,我们先通过上方的“区间最大值”例子,介绍一下区间最值问题的ST表查询。 合适的长度 首先,为了降低时间复杂度,我们希望用尽可能少的区间查询来拼凑出完整答案。可以证明,在ST表处理区间最值问题时,无论区间长度位置,我们都可以用ST表支持的两个区间,拼接出答案。比如对于区间(1, 6),可以由区间(1, 4)和区间(3, 6)区间的结果再求最值得到。对于“最值”问题,我们只需要保证选择的区间完整覆盖住所求区间,且不超过所求区间即可,而这多个区间允许有重复部分。 同时,为了保证所用区间尽可能少,每个区间就要尽可能大。这个时候,上方说到的log2向下取整计算就派上用场了。由于ST表代表的区间长度只能是2的n次方倍,所以,不超过区间范围的区间,其最长长度就是log(区间长度)向下取整。 比如对于(1,6)区间进行最值计算,log2(6)向下取整=2。说明只需要在合适的位置,用两个长度为2^2=4的区间覆盖即可。这代表了,我们要取的数据肯定在ST[idx][2]内——我们确定了pow。 合适的位置 我们已经知道了,只要位置安排合理,我们肯定能用两个长度为4的区间覆盖住(1, 6),那么这两个区间的位置,应该如何选择呢? 思考之后发现,我们肯定希望: 如上图,最终,我们可以得到: 我们对这两个区间的最大值再求一次最大值即可,最终答案为max(5, 9) = 9。 如果用ST表来计算,运算过程如下: 是时候该自己实现ST表啦Continue reading “Sparse Table”