Forever you~

来自Petrozavodsk Winter-2018. AtCoder Contest里的D题 题意是说，有$Q$次操作，分为两种，一是添加一个重量为$w$，价值为$v$的物品，保证插入的$w$单增，二是删除当前重量最小的物品。每次操作完之后，都有一个询问，询问能否从已有物品中选出一个子集，使得重量之和在模$M$之后在区间$[l,r]$内，并且价值和最大。 数据范围，$Q\le 100000,2\le M\le 500$。 $Q$和$M$一开始给定，之后每次操作强制在线。 做法：首先背包比较容易看出，但是有动态的插入、删除，这里的动态实际上是队列的模型，队尾入队，队首出队。我们将所有物品分成两部分，右半部分直接组成一个背包，左半部分记录从分界线开始的所有后缀组成的背包状态。那么插入就直接背进右边，删除直接删除左边第一个物品，不影响其他后缀，当左边为空时，就将右边所有物品移到左边，即将... Continue reading...

关于Stern-Brocot tree网上的资料较少（后记：实际上并不少，只是竞赛中讨论的不多），能够找到的资源有Wikipedia以及《具体数学》上的介绍，这里大概总结一下这个树形结构的性质。 Stern-Brocot tree: Stern-Brocot tree构成了一个无限的二叉排序树，可以将所有的正有理数从小到大列举出来。 构造方法可以理解为：先在左边写上$\frac{0}{1}$，右边写上$\frac{1}{0}$，代表零和正无穷，然后分子、分母分别相加，得到$\frac{1}{1}$，写在中间，之后每次把当前层复制到下一层，然后对于下一层相邻两个有理数之间还是分子分母分别相加，得到新的有理数，写在两者中间，重复这个操作就可以无限的写下去，进而得到所有的有理数。树形结构的获得见上图。 记树中的一个节点$\frac{y}{x}$，它是由$\frac{L_m}{L_n},... Continue reading...

适用条件：动态开点的(权值)线段树。 关于时间复杂度的结论： 每次合并的代价是两棵树的公共节点数。 若有n棵含有单个元素的树，经过n-1次merge操作，将他们合并成一棵树的代价是$O(nlogn)$或$O(nlogC)$的 单次merge操作开销可大可小，均摊下一次就是一个log的。 关于空间复杂度，普通版本是$O(nlogn)$的。 直接给出代码，merge操作十分简洁： 12345678910111213141516void insert(int &x,int y,int l,int r){ ++sum[x=++tot]; if(l==r) return; int mid=l+r>>1; if(y<=mid) insert(ls[x],y,l,mid); else insert(rs[x],y,mid+1,r... Continue reading...

最近想起来这么一道题，当时q神没rush出来，赛后几分钟AC掉的 题目链接：https://nanti.jisuanke.com/t/17114 题意是树上有$N$个点，每个点的点权是一个01矩阵，有$Q$次询问，每次问树上从x到y这条路径上的矩阵依次乘起来的结果是多少(模2意义下)。数据范围$N\le 3000,Q\le 30000$，矩阵大小$64\times 64$。 首先这里的模2意义下的矩阵乘法可以用bitset优化，每行一个bitset，每列一个bitset，这样做乘法就是左行右列and起来，然后count一下1的个数，复杂度$O({64}^2)$。 注意到这道题中维护的信息只能合并，不能做“减法”，也就是不能使用逆矩阵，因为逆矩阵不一定存在。 一个显然的暴力思路是就是树上倍增，但很不幸，时间复杂度$O({64}^2QlogN)$达到了$1.4\times 10^9$肯定... Continue reading...

最近做了几道高维偏序的简单题。 对于这类题目一般有三种通用方法，一是cdq分治，维数越多嵌套次数就越多，总体来说思路就是对时间分治，每次统计出左半区间的贡献点对右半区间的询问点的贡献，这样对于每个询问点来说，它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力，应该只能处理计数问题，但优点是好写，适合做高维偏序。三是KDtree，emmmm，这个没怎么写过，多校训练十分艰难的写过一次，通过了90%的数据然后TLE了。 1.LOJ#112 三维偏序计数题，对其中一维排序后，cdq分治套树状数组，时间复杂度$O(nlog^{2}n)$。 2.COGS 2479[HZOI 2016] 偏序计数题，四维偏序，cdq分治套cdq分治套树状数组，时间复杂度$O(nlog^{3}n)$。 怎么理解这个分治套分治呢。假设属性为a,b,c，第一次分治的时候我们将区间[l,mid]的点标... Continue reading...

偏序关系首先回顾一下偏序，集合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来表示偏序关系，常见的偏序关系有集合的包含，小于等于，整除等。$<$表示严格偏序（反自反，反对称，传递），比如严格包含于，小于关系等。 可比与不可比对于X中x和y，如果x R y或者y R x，则说x和y是可比的，否则就说x和y不可比 极小元极大元对于偏序集X中的元素a，不存在满足x<a的元素x，则a是偏序集的一个极小元。对于偏序集X中的元素b，不存在满足b<y的元素y，则b是偏序集的一个极大元。 链与反链设$(X,\le)$是有限偏序集，链是X的一个子集... Continue reading...

推导有时候需要快速计算如下式子(比如数据范围都是1e9) $$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$$ $$g(a,b,c,n)=\sum_{i=0}^{n}i\lfloor\frac{ai+b}{c}\rfloor$$ $$h(a,b,c,n)=\sum_{i=0}^{n} {\lfloor\frac{ai+b}{c}\rfloor}^2$$ 先推导一下$f(a,b,c,n)$，分两种情况 1.当$a\ge c$或$b \ge c$时， $$f(a,b,c,n)=f(a%c,b%c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor$$ 2.当$a<c$且$b<c$时，令$m=\lfloor\fra... Continue reading...

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

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

以下内容摘自《算法导论》思考题30-3 我们可以将一维离散傅里叶变换推广到d维上，这时输入是一个d维的数组$A=(a_{j_1,j_2,\dots,j_d})$，维数分别为$n_1,n_2,\dots,n_d$，其中$n_1n_2\dots n_d=n$。定义d维离散傅里叶变换如下: $$y_{k_1,k_2,\dots,k_d}=\sum_{j_1=0}^{n_1-1}\sum_{j_2=0}^{n_2-1}\dots\sum_{j_d=0}^{n_d-1}a_{j_1,j_2,\dots,j_d}\omega _{n_1}^{j_1k_1}\omega _{n_2}^{j_2k_2}\dots\omega _{n_d}^{j_dk_d}$$ 其中$0\le k_1<n_1,0\le k_2<n_2,\dots,0\le k_d<n_d$ a.证明：我们可以依次在... Continue reading...