问题引入 题目要求解决的模型： 给定有向图G（可能有环）和图中的一个点r，对于G中的任意一个点x，求从r到x的路径上（可能有很多条）必须经过的点集。 Flow Graph：若有向图G中存在一点r，从r出发可到达G中所有的点，则称G是Flow Graph，记为(G,r)。 必经点（dom）：若在(G,r)中从r到y的路径一定经过点x，则称x是从r到达y的必经点，记为x dom y。 从r出发到达

来自Petrozavodsk Winter-2018. AtCoder Contest里的D题 题意是说，有QQQ次操作，分为两种，一是添加一个重量为www，价值为vvv的物品，保证插入的www单增，二是删除当前重量最小的物品。每次操作完之后，都有一个询问，询问能否从已有物品中选出一个子集，使得重量之和在模MMM之后在区间[l,r][l,r][l,r]内，并且价值和最大。 数据范围，Q≤10000

关于Stern-Brocot tree网上的资料较少（后记：实际上并不少，只是竞赛中讨论的不多），能够找到的资源有Wikipedia以及《具体数学》上的介绍，这里大概总结一下这个树形结构的性质。 Stern-Brocot tree: Stern-Brocot tree构成了一个无限的二叉排序树，可以将所有的正有理数从小到大列举出来。 构造方法可以理解为：先在左边写上01\frac{0}{1}10

适用条件：动态开点的(权值)线段树。 关于时间复杂度的结论： 每次合并的代价是两棵树的公共节点数。 若有n棵含有单个元素的树，经过n-1次merge操作，将他们合并成一棵树的代价是O(nlogn)O(nlogn)O(nlogn)或O(nlogC)O(nlogC)O(nlogC)的 单次merge操作开销可大可小，均摊下一次就是一个log的。 关于空间复杂度，普通版本是O(nlogn)O(nlo

最近想起来这么一道题，当时q神没rush出来，赛后几分钟AC掉的 题目链接：https://nanti.jisuanke.com/t/17114 题意是树上有NNN个点，每个点的点权是一个01矩阵，有QQQ次询问，每次问树上从x到y这条路径上的矩阵依次乘起来的结果是多少(模2意义下)。数据范围N≤3000,Q≤30000N\le 3000,Q\le 30000N≤3000,Q≤30000，矩阵大小

最近做了几道高维偏序的简单题。 对于这类题目一般有三种通用方法，一是cdq分治，维数越多嵌套次数就越多，总体来说思路就是对时间分治，每次统计出左半区间的贡献点对右半区间的询问点的贡献，这样对于每个询问点来说，它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力，应该只能处理计数问题，但优点是好写，适合做高维偏序。三是KDtree，emmmm，这个没怎么写过，多校训练十分艰难的写过一

偏序关系 首先回顾一下偏序，集合X上的偏序是一个自反、反对称且传递的关系 如果对于X中所有的x，都有x R x，则R是自反的 如果对于X中所有x和y，若x R y和y R x同时成立则x=y，则R是反对称的 对于X中所有的x，y和z，只要x R y且y R z，就有x R z，则R是传递的 通常用≤\le≤取代R来表示偏序关系，常见的偏序关系有集合的包含，小于等于，整除等。<<&

推导 有时候需要快速计算如下式子(比如数据范围都是 10910^9109 ) f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor f(a,b,c,n)=i=0∑n​⌊cai+b​⌋ g(a,b,c,n)=∑i=0ni⌊ai+bc⌋g(a,b,c,n)=\sum_{i=0}^{n}i\lfloor

写在前面 推荐hihocoder上的讲解，可以说是十分清楚了。 用好后缀自动机不是十分容易，但看完本文的总结应该能至少达到签到水平…

西江月 瑟瑟微风夜半，潇潇细雨黎明。雄鸡一唱与谁听？几度茫然光景。 壮志还须努力，何时乡返功成。椟中美玉尚无名，待得他人相赠。 七绝·四季 漫漫冰霜眼底收， 西风萧瑟欲何求。 独怜明媚绝非夏， 四季如春花满楼。 第一首是词的作业，第二首是诗词格律与写作期末题，这学期另作了一首五古，质量不高，就不放出来了=、= 关于诗词创作就到这里了（撒花）