Deep_Kevin的娱乐空间

正题      第五题：[CQOI2007]余数求和      这道题看到余数，就会觉得很恶心对不对，但是我们可以从商入手。      因为如果在一段数里面，他们的商相同，那么他们的余数就是递增的。      那么我们很容易就想到了除法分块和级数求和。      没错我们设l，r满足k/i相等(i属于[l,r])      我们首先可以知道当前的l，那么用k/[k/l]就可求出r      下一个...

正题      这题其实在思路上不难，但是时间却非常卡人。      首先我们看到加点，我们就知道要用分块来解决这个问题，在分块的方式上选择size分块。      然后对于每一个建好的块，建一棵主席树来维护信息。      改权值的时候，我们就需要先把先前的权值的那条链都加上-1，再把新的权值的那条链加上1.      然后再加点时，就根据父亲来看一下，是加入父亲的那个块还是自己新开一个块。  ...

正题      其实这题，就跟Gty的妹子树是差不多的。就是多了一个删边操作。      我们还是选择了分块+主席树，但是问题就是怎么断边。      首先我们可以知道如果这条边是块与块之间的连接边，那么直接断就可以了。      如果不是，那么我们要继续往下搜索，把那些原先在块内的节点都删掉，然后在新开一个块存储断边后u所在的块，那么这时候u肯定是块顶。      然后让那些子树内原先连着u所在...

正题 题目传送门 我们考虑分块，第一块先做一遍暴力，转移好的Dp数组后，直接做一遍高维前缀和，具体高维前缀和的实现就是枚举每一个质数，再枚举每一个m的约数，再枚举这个质数的几次方，使得这个约数乘上质数的几次方仍然是m的约数，那么就转移一下，因为是每个质数依次转移，所以相当于。 相当于算了这一个块向后走一步的贡献，然后直接将这个东西赋值到下一个块。 ...

正题 将一个集合划分成若干个规模较小的子集合，一般来说，我们倾向于把性质接近的元素分到同一个子集里面，并把每个子集的元素按照一定结构组织起来，形式主要有两种： 1.线形序列的分块化 2.树形结构的分块化 先讲讲现行序列的分块化。 线形序列预处理：在分好块之后，尝试对线性序列进行预处理。当查询任意区间的时候，对于预处理的部分直接返...

专题测试 第一题：经典带修莫队：数颜色。 虽然打了出来但是证明复杂度也是刚才才会。 题意就是一开始给你一个序列，每次要么询问x到y中不同元素的个数，要么修改第x个元素为y。 假如我们按S把询问分块，一开始按第一关键字把l所在的块排序，按第二关键字把r所在的块排序，按第三关键字把t排序。 t就是这个询问之前的修改操作个数。 ...

正题 今天讲的是一些杂题 一开始的是一些搜索。 1.长度为N的数列，已知N个前缀和以及N个后缀和共2N个数打乱后的结果，已知数列中每个数的范围是不超过500的整数，求原数列，存在多组时间求字典序最小的。1<=N <= 1000 我们考虑将整个序列从小到大排序，然后第一个元素一定是F[1]或者G[1]。就这样按顺序得向下选，就可以...