由于要做年轻人的第一次技术分享，因此我挑了个epoll实现原理作为课题，主要是先做下快速介绍，然后直接杠源码（长篇大论没人听警告） PS. 不想看一堆代码可直接快速浏览文中的流程图，点我直达 涉及到的内容 epoll是什么，大概怎么用 了解epoll实现前需要知道的工具 三大实现流程，及其内部数据结构 实际需要考虑的问题及总结 epoll是什么 epoll 全称 eventpoll，是 linux 内核实现IO多路复用的一种实现。 IO多路复用的意思是在一个操作里同时监听多个输入输出源，在其中一个或多个输入输出源可用的时候返回，然后对其的进行读...

鉴于C++标准库并没有提供侵入式容器供我们使用，这里只简单梳理一下侵入式容器的特性 最简单的侵入式容器 先看一个最简单的示例：list_head struct list_head { list_head *prev, *next; }; 这是Linux提供的内核链表，一个最简化的侵入式容器 可以与非侵入式STL风格的实现对比一下 template <typename Tp> struct ListNode { ListNode *prev, *next; Tp value; // ... }; 相比于STL风格的区别，可以...

摘要 本文深入探索g++钦定的西半球最快的排序算法 说明 下文中提到的STL都是指GNU ISO C++ Library（既libstdc++）下的具体实现 流程分析1-policy STL的sort实现是使用一种内省式排序的算法，也就是大范围（使用快排+递归过深使用堆排）+最终使用完整的插入排序来完成 template<typename _RandomAccessIterator> inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) ...

前置 首先你要知道什么是variant，还有它的好伙伴visitor 看这里 看完之后你应该觉得它是个好东西 背景 没啥背景，就是有一天觉得用variant来造JSON库似乎非常简单，恰好又没在github上找得到，因此想验证一下 但是既然是造一个库，那当然是从零写起最有挑战也最有成就感 因此这篇就是用来探索如何从varint写起 尝试造一个简单的std::variant，目标500行以内吧（实际上300行就足够了！） 需要什么 这是一道填空题，填完了你就能拥有类型安全的union、功能强大的visitor （为了便于阅读和思考，做了稍微省略调整） templat...

轮子所用的定时器方案大概定型了，觉得可以对一下思路，讨论一下逐步扩展的实现 需求 要设计任何一个东西其实要基于需求比较好，虽然本质上我就是想自己造轮子，但是需求能给人一种方向感，以及能说服自己为什么要这么写 功能相对丰富 性能不太拉跨 线程安全 接口友善 代码简洁 功能与接口 接口的友善基于两点：user define literal和builder模式 在说明前我先介绍在设计之初就构思的两个类：TimerEvent和Timer， TimerEvent包含时间参数和可调用对象，Timer封装调度用的容器 具体操作就是构造TimerEvent然后丢...

最近在写一个库，有一个场景是std::vector存储一些对象，每次都是往后面添加，但是内部的元素可能会随机地失效（且不可恢复），这种场合下需要针对性地优化vector： 尽可能回收这些占坑的无效元素，避免容器支离破碎的碎片 降低添加过程的响应时间，避免扩充时造成的\(O(n)\)卡顿（就是要求严格\(O(1)\)，非均摊\(O(1)\)） 其中要求一是这个特殊容器的特定条件，要求二是这个容器需要达成的目的，不希望加入两个元素之间有过大的性能差异（这会对其它操作有影响），而扩容是vector的通病 一个场景的模拟 -------------------------...

支持任意可调用对象，任意参数，任意作用域，跑的还快，go看后一言不发，惊呼C++不可战胜(x #include <bits/stdc++.h> ///// class Defer: std::__shared_ptr<Defer, std::_S_single> { public: template <typename T, typename ...Args> Defer(T &&func, Args &&...args) : std::__shared_ptr<Defer, st...

简单记录一下这个拖了许久的小轮子 Overview 目前实现了一个简单的数据库存储引擎，具有的功能 可持久化 B+树索引 页级缓存 页的回收复用 SQL解析 （即将完成）大型记录存储 （极其粗糙版）事务并发与日志 实现的细节大部分是自己推敲，整体思路是参考书籍，整个过程写起来还是挺愉悦的 持久化的实现 要实现持久化，就是要定制从内存到外存之间的转换协议，我的做法是针对一个表（内存）对应一个文件（外存） 文件是单一的，但内部需要分页，正常人的做法是分页大小为4K字节的倍数，比如InnoDB采用16K，我选择8192字节，实测相对快一点 每个页...

说明 一般的哈希考虑的是均匀分布，即使是对于一个极大的文本串中仅有一处偏差也可能引起极大的计算差异 而谷人希出品的SimHash是一种具有局部敏感性特征的哈希，简单地说就是克服了前面提到的的缺点（讲道理应该叫局部不敏感吧） 因此SimHash不仅能判断是否相等，还能判断是否高度重复 定义 \(feature\)：特征，一般是文本串中的关键字 \(weight\)：权重，由对应的\(feature\)经过哈希得出，是个整数 \(fingerprint\)：指纹，文本串最终形成的产物，是个整数 当两个\(fingerprint\)的hamming距离（就是相互xor的bitc...

虽然说是没啥卵用的东西，但学习证明它为什么是互斥的还是有点意思 定义 箭头\(A \to B\)表示事件\(A\)先于\(B\)的意思，\(I(A,B)\)为\(A\)和\(B\)之间的间隔，多个不存在\(\to\)关系的间隔就称为是并发的 \(CS_A^k\)表示线程\(A\)第\(k\)次进入临界区里头的时间段 临界区的开始需要调用lock()，结束需要调用unlock() 锁算法的特性 【必须】互斥：不同线程的临界区无重叠，设线程\(A,B\)和任意整数\(j,k\)，要么满足\(CS_A^k \to CS_B^j\)，要么满足\(CS_B^j \to CS_...

算是个小知识点吧 对于常见的前缀和，正常人知道的求法是通过容斥 （为了方便表示就用了1开始的下标和伪代码） loop i:[1,x] loop j:[1,y] loop k:[1,z] sum[i][j][k] = arr[i][j][k] + sum[i-1][j][k] + sum[i][j-1][k] + sum[i][j][k-1] - sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1] + sum[i-1][j-1][k-1] 其实还有更低复杂度的写法 loop i:[1,x] lo...

\(shift-and\)字符串匹配算法适用于模式串长 \(|P|\)短于机器字长\(w\)的情况，直接用位运算来\(O(|T||P|/w)\)获得文本串后缀和模式串前缀的所有匹配信息 定义 文本串\(T\)，模式串\(P\)，不解释了 位向量\(D\)：\(D\)的长度为\(P\)的长度，每一位表示前缀的匹配程度，\(D[j]=1\)表示前缀\(P[0,j]\)匹配后缀\(T[i-j,i]\) 预处理位向量数组\(B[Σ]\)：对于字符集\(Σ\)的每一个字符\(c\)，\(B[c][j]=1\)表示\(c\)允许在位置\(P[j]\)出现 过程 还是增量法的观点，假设已经...

无旋Treap是一个非常精简的平衡树，定义也挺简单的，旨在替代splay等反人类旋转树 定义 \(fix\)：决定节点间父子关系的随机权重（就是作为堆的key） \(val\)：真实的权重，决定节点间中序关系 \(split(cur,pivot,u,v)\)：把当前的\(cur\)树划分成\(u,v\)子树，按照\(pivot\)大小划分 \(merge(u,v)\)：把\(u,v\)子树合并，按照\(fix\)决定树的结构 细节 一般treap更适合用于区间操作（把\(pivot\)按照\(size\)来划分即可，而树形操作则用\(val\)来比较），因此这里没有\(cn...

数组版写着就是数服！ PS.是左偏红黑树 #include<bits/stdc++.h> using namespace std; namespace util { template<typename T> inline void empb(vector<T> &v,const T &arg) { v.emplace_back(arg); } inline void fast_io() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } } ...

定义 定义估价函数\(f=g+h\) \(f(x)\)为总估价值 \(g(x)\)为真实价值 \(h(x)\)为当前估价值 对于\(K\)短路问题来说\(f\)为\(s \to t\)的总花费，\(g\)为\(s \to x\)的真实花费，\(h\)为\(x \to t\)的预估花费 过程 \(h(x)\)的存在要求在以\(t\)为起点的反向图中求出最短路 初始状态放入优先队列中 每次依次挑\(f\)最小的节点，对邻接的点重新估值更新并加入队列中 当第\(k\)此到达节点\(t\)，就是\(s \to t\)的\(K\)短路 优化部分：对于某个经过\(k+1\)次的...

定义 奇根\(0\)：长度为-1的回文串所在节点（为了便于处理） 偶根\(1\)：长度为0的回文串所在节点 \(len[u]\)：当前节点\(u\)维护的回文长度 \(trans[u][c]\)：转移函数，注意其中所有状态均为回文（单次转移相当于\(u\)节点代表字符串左右两边加上\(c\)） \(fail[u]\)：失配指针，指向\(u\)最大匹配后缀回文的所在节点 前置理论 一个长度为\(n\)的字符串中，本质不同的回文子串个数也不超过\(n\) 对于在一个串中新增一个字符的情况下，本质不同回文子串个数最多新增1个 证明： 考虑增量过程中新增的字符\(str[i]...

定义1 \(Pattern\)：模式串 \(Text\)：文本串 \(next\)：失配函数， \(next[i]=j\) 表示\(Pattern\)的最大自匹配的真前缀（\(|pre| \lt len\)）的下标（这里是为了方便代码实现），即模式串的子串\(P[0,j] = P[i-j,i]\)，并且\(next[0] = -1\) 构造过程 构造过程就是初始化\(next\)的过程 假设存在\(i,j\)指针，\(i\)为当前要处理的指针，而\(j\)对应于上一次\(i-1\)时匹配的失配指针 就是说有\(nxt[i-1]=j\) 说明最大的自匹配为\(P[0,j]=...

对于一个关于只接受\(str\)后缀的后缀自动机，其后缀肯定能从起始状态\(S\)合理地转移，而非后缀必然无法转移 定义 定义相关的函数 \(trans[u][ch]=v\)：表示\(u\)状态沿着\(ch\)边转移到了\(v\)状态的转移函数 \(endpos(s)\)：表示\(str\)的任意子串\(s\)的终止位置集合，用于子串归类 性质1：当\(len(s1) \le len(s2)\)且\(endpos(s1)\)包含\(endpos(s2)\)所有子集时，\(s2\)是\(s1\)的后缀（充要） 当两个集合\(endpos(s1)==endpos(s2)\)，则认...

众所周知，求最大流要是没有反向边，基本都是错的 那为什么反向边能修正错误的增广 查了一些资料，好像没有什么严格证明的样子，可能图论还是太复杂了点 不过还是找到了PKU camp的PPT，感觉说的还不错，大概意思就是反向边可用于二路合并 （你刚才说我画的丑是吧） 考虑某种情况，如图有一条增广路通过\(a \to b\)的路径，\(flow = n\) 那么至少说明， 边\(e1,e4\)有\(cap-flow=n\)， 如果此时已经跑不动了，那就只能增广到这里得到最大流\(n\) 假如添加了反向边的机制，发现能\(b \to a\)反向流动\(flow=n-k\)...

定义 \(sa[i]\)：字典序第\(i\)小的后缀（suffix array） \(ra[i]\)：后缀\(str[i...n]\)在\(sa\)中的下标（rank） 思路 假定字符串长度为\(n\)，它必然是一个2的幂（不足就认为后面是空） 后缀数组\(sa[i]\)可认为是长为\(n\)的情况下字典序第\(i\)小的子串\(sa_n[i]\)（不足就认为后面是空） 它可以通过长度为\(n/2\)的字典序\(sa_{n/2}[i]\)（以及当前的\(ra\)）的所有情况来\(O(1)\)判断得出 （也就是说对于\(str[i,i+2^j)\)可通过\(str[i,i+2...

I see you gather before me… hungry… terrified… Clutching your babes to your breast. 各位聚集在我面前……饥肠辘辘又恐慌不安…… 胸前还紧抱着孩子。 Emperor Emhyr has marched his legions into our lands… Laid siege to every fortress from here to the Blue Mountains.. Rabid and ravenous, he bites and bites away. 恩希尔大帝的军团已经攻入了...

背景 为什么我会去考据这些东西 只是觉得有点匪夷所思（总不能说是无聊没事干） 在Java中一个32位的数就是int，没有任何争议 而C/C++由于强依赖于硬件体系就显得非常自由了 出于可移植性、可读性和鲁棒性，差不多的类型总有些微妙的不同 因此本文旨在收集一些过于自由不常见的类型和推测其设计目的，just4fun int32_t / int_least32_t / int_fast32_t int32_t在标准中为exact-width，就是必然是32位，因为在16位的机子中int是16位的，其设计目的就是用于保证可移植性。另外，标准中提到类似intN_t的是opti...

TV第一季 TV01 好心提醒你一下 在那边学的东西最好全部忘掉 现实中那些玩意儿一点用都没有 是不是觉得很荒谬 不过话说回来 我们的工作本来就没什么道理可言 人们在想什么 在祈求什么 这个时代里机器能读透人心 即便如此却依然有大把的人去憎恨他人 甚至试图加害 这不是荒谬是什么 TV02 所以 我再问你一次 你 是为什么成为监视官的 对不起 向执行官道歉的监视官可真少见 你果然在生气吗？ 那是你的判断 我没理由抱怨 我判断错误了吧？ 只会拖大家的后腿 将大家害得陷入危险的境地吧 我已经做了很久的执行官 毫无迷茫 毫不犹豫 听从命令去...

所有考试总算考完了，于是我被LAJi学校坑去生产线QAQ 趁着脑袋还记得先马一下（距离遗忘DSP所有内容还有30min 计算过程 已知\(X[m]=\sum_{k=0}^{N-1}x[k]W_{N}^{km},m=0,1,...N-1\) 那么 [\begin{align} X[m] &= \sum_{k=0}^{N-1}[k==2r]x[k]W_{N}^{km}+\sum_{k=0}^{N-1}[k==2r+1]x[k]W_{N}^{km} &= \sum_{r=0}^{N/2-1}x[2r]W_{N}^{2rm}+\sum_{r=0}^{N/2-1}x[...

随便敲的，看看就好（被书折腾后凭感觉写的，可能小误 PAXOS针对2PC的保守策略改为少数服从多数的更为合理的策略 每个Acceptor可批准多个提案 每个Proposer有唯一的身份标记\(M_i\)，以及对应的提案内容\(V_i\),用\(<M,V>\)表示一个提案 注意提案者\(M\)其实是会暗中附和其它人的提案内容，因此\(V\)并不唯一，所谓的选定提案更为关注的是内容\(V\) 提案超过半数即大于等于\(\lfloor \frac{n}{2} \rfloor+1\)的Acceptor批准时，该提案被选定，内容由Learner发布 规定： P1.Acc...

本篇是head first设计模式的读书笔记，关键的定义我会摘录书里的原话（一般比较简短），自己思考的部分不一定很正确，有错误请指出（又没人看唉） PS.书上的设计原则和设计模式是混合编排的，因此本笔记也会跟随这种排版 策略模式 策略模式定义算法族，分别封装起来，让它们之间可以互相替换，此模式让算法的变化独立于使用算法的客户 关于继承/接口 在超类上添加的方法将会使得所有子类具备该方法，如果某一个子类不需要该方法，那么就要重写覆盖掉（空），如果多个方法不需要使用，那就要多次重写，显得很sb 如果改为利用接口实现这种难以预测的子类行为，仅在需要时才实现该接口，那代码重...

NanjingOnsite:三维坐标下给出\(n\)个点\(p_i\),找到一个点\(best\)使得\(max_{i=1}^ndis(best,p_i)\)最小,\(n\le 100\) 最小球覆盖呵呵 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 103; const double PI = acos(-1); const double EPS = 1e-6; int n; double ans; struct Point{ double...

题意:给出\(a[1...n]\),共\(n\)次操作,每次删除一个位置\(p_i\)(强制在线),此时区间会变为两个分离的区间,求每次操作的最大区间逆序对 首先要知道必要的工具,按权值建立的主席树可以在\(O(nlogn)\)内得到任意区间长为\(n\)的逆序对 但每次切除的点如果是不断沿着边来切,那么要统计的区间总长是\(O(n^2)\) 考虑逆序对的贡献是可以互为计算得到的,那么能否每次只对相对较小的区间的复杂度进行统计,得到\(O(nlogn)\)的区间统计总长? 如果已知一个区间\([L,R]\)的总逆序对\(oldans\),切点为\(M\),且更靠左边, 那可以对...

题意:n个左下角为原点右上角在第一象限的矩形不断覆盖,求最后形成的图形的周长 x和y是独立的,分别维护两棵线段树,一棵表示x坐标下最大的y值,另一棵表示y坐标下最大的x值 从覆盖的角度来考虑,如果逆序处理,当前处理的段的贡献为大于等于当前位置的最大值的差 比如一条横的线段i,坐标为[x1=0,x2],y 那它对答案的贡献为max(0,x2 - max_x of [y,maxy]),此时的区间存在的线段为逆序第n条到第i+1条 处理完后再插入到对应的线段树中即可(其实贡献为0的不插也行,因为都是不断取一个后缀最大的值) #include<bits/stdc++.h>...

题意：给你一棵树，n个点q次操作，操作1查询x子树深度为d的节点权值和，操作2查询子树x权值和 把每个点按(dfn，depth)的二维关系构造kd树，剩下的只需维护lazy标记即可 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) #define erep(i,u) for(register int i=head[u];~i;i=nxt[i]) #define ...

题意:给定\(a[1...n]\),多次询问\([L,R]\)中的任意一对数使得\(gcd(a_i,a_j)\)最大 对于gcd,区间内至少存在两个相同的因子才能作为合法的解,存在两个相同因子且最大就是最优的解 对区间右端点进行离线排序,用线段树维护\([L,R]\)内最大的gcd(存在两次以上的因子) 具体的更新策略:记录因子\(j\)的上一次出现的地方\(last_j\),当\(last_j\)已存在时再插入\(last_j\)就能维护两次以上的信息,离线处理保证了后面的因子不会插入到当前查询范围的某个\(last_j\)中,具体看代码 #include<bits/s...

题意:给出一棵树共\(n\)个顶点,每个顶点有一个权值\(val_i\),你需要对每个节点统计一个最优解, 每个节点的解按照一定规则产生:取出该节点的子树下所有的顶点,把顶点任意排序成一个序列,设为\(v_1,v_2...,v_k\), 此时解为\(\sum_{i=1}^{k}\sum_{j=1}^{i}val_{v_j}\),最小的解为最优解 对于每个解的处理来说,子树下值小的顶点肯定放前面,按这样来贪心无疑是正确的(前缀贡献尽量小) 那么对于无序的插入过程,当前节点\(u\)的贡献为\(val_u+cnt+num*val_u\) 其中\(cnt\)为当前小于\(val_u...

Luogu - P3384 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) #define println(a) printf("%lld\n",(ll)a) using namespace std; const int MAXN = 2e5+11; typedef long long ll; ll MOD; ll read(){ ll x=0,f=1;...

题意:给出\(a[1...n]\),找出一个连续区间\(a[l...r],r>l\),令该区间的次大值为\(a_k\),使得\(a_k⊕a_i,l≤i≤r\)最大,输出全局最优解 (这题意有点别扭) 异或这种套路,一般都是上trie,区间异或就加个可持久化 但问题是怎么找区间 不妨令每一个\(a_i\)为当前区间的次大值,那我们的目标就是尽可能找出该次大值的最远左右边界 令\(a_i\)从大到小插入,使用平衡树动态维护位置,那么\(pos_i\)的前驱和后继都是比\(a_i\)大的值的下标 假设第一个比\(a_i\)大的左边界下标是\(L1\),第二个比它大的是\(L...

题意:给定\(a[l...r]\),多次询问区间\([l,r]\)中的最大连续异或和\(a_i⊕a_{i+1}⊕...⊕a_{j},l≤i≤j≤r\) 一眼过去认为是不可做的,但题目给出\(n=1.2e4\),提供了分块暴力的余地 首先处理成前缀形式,对于询问\([l,r]\)既为\([l-1,r]\)中寻找两个数xor最大 维护\(f[i][j]\):第i个块到第j个数的任意异或最大值 这个只需\(O(30n\sqrt{n})\)的代价即可预处理 对于每次询问,首个残缺的块暴力,其余块直接由\(f\)得到答案,复杂度\(O(30m\sqrt{n})\) Yet Anoth...

题意:给出一个图,先求出最大生成树,然后多次询问树上路径\(u→v\)的有向最大极差\(max(a_i-a_j),i>j\),其中\(i\)和\(j\)指代节点在路径中出现的顺序 极差具有单调性和可相交,因此可以用倍增来合并答案求解 维护变量 \(mx[i][j]\):\(i\)节点到\(i\)的第\(2^j\)个祖先的最大值 \(mn[i][j]\):\(i\)节点到\(i\)的第\(2^j\)个祖先的最小值 \(f[i][j]\):\(i\)节点到\(i\)的第\(2^j\)个祖先的最大极差 \(g[i][j]\):\(i\)的第\(2^j\)个祖先到\(i\)节...

题意:在\(n*m\)的网格中,某个物体初始置于点\((x,y)\),每一步行动都会等概率地停留在原地/往左/往右/往下走,求走到最后一行的的步数的数学期望,其中\(n,m<1000\) lyd告诉我们这种题目要倒推处理.设\(f[i][j]\)为(i,j)到(n,k)的步数期望,k为任意数 那么对于各种边界有如下情况 [f[n][j]=0] [f[i][1]=\frac{1}{3}f[i][1]+\frac{1}{3}f[i][2]+\frac{1}{3}f[i+1][1]+1] [f[i][m]=\frac{1}{3}f[i][m]+\frac{1}{3}f[i][...

题意:n个墙壁m个粉刷匠,每个墙壁至多能被刷一次,每个粉刷匠要么不刷,要么就粉刷包含第Si块的长度不超过Li的连续墙壁(中间可不刷),每一块被刷的墙壁都可获得Pi的利润,求最大利润 避免重复粉刷: 首先对Si排序并定义\(f[i][j]\):前i个木匠处理到第j块木板时的最大利润 此时[j+1,n]保证没被处理以满足无后效性 保证情况一的合法 [f[i][j]=f[i-1][j]] 保证情况二的Si必须被粉刷 定义处理的区间为[k+1,j] 则\(f[i][j]=max_kf[i-1][k]+P_i*(j-k)\) 此时要求Si必须在[k+1,j]内部,则对k加以限定...

题意:给出\(n<3e4\)个有序组\((a,b,c,d,e)\),求对第\(i\)个有序组有多少个\(j\)满足\((a_j<a_i,b_j<b_i,c_j<c_i,d_j<d_i,e_j<e_i)\) 五维偏序问题按套路来可以排序+树套树套树套树(打死 然而这是显然连\(O(n^2)\)暴力都不如的 可是题目给4s,\(O(n^2)\)是不可能的,但在神奇的bitset加持下\(O(5*n^2/32)\)的时空复杂度是可以卡过去的! 用bitset表示集合,\(bit[i]:\)如果\(i\)在集合中就设为1,否则0 维护\(bit[i...

题意：给出一棵带边权树，询问有多少点对的距离小于等于\(k\) 本题解参考lyd的算法竞赛进阶指南,讲解的十分清晰,比网上那些讲的乱七八糟的好多了 不过写起来还是困难重重（史诗巨作 打完多校更详细做法 对于所有路径,以某个节点u来看分为两种情况 1.经过u的路径 2.不经过u的路径 能对答案有贡献的肯定是1类型，对2我们处理完1后递归求解 于是条件变为 以u为根的树中，其联通块中的点对符合 距离u之和小于等于k ① 且位于各不同的u的子树（u单独处理） ② 不妨先维护①再维护② 每一次选定根u后预处理联通块内的点相对于u的距离dis,以及归属于哪个子树belo...