陈紫阳的博客

奋斗于OI之路

终于把这个东西搞定了。 定义 就是砍树。 这东西可以动态维护一些树上的操作。 其实就是把树上结点映射到区间上。 使用 先来一坨定义。 重儿子:相比于其他儿子,以这个点为根的子树大小最大。若有多个最大任选一个即可。 轻儿子:非...

发布 0 条评论

之前看了乘法逆元(详见除法取模与逆元),发现不能处理不互质的情况,于是去找方法,最后找到了Lucas定理。。。 虽然与期待中的不一样,但是还是非常有用的。 (1)Lucas定理: 若p为素数,则有: Cnm≡∏i=0kCnimi(modp) Cmn≡∏i=0kCmini(...

发布 0 条评论

传送门 题目大意 维护一个序列A。m次操作分2种。 2 x y 把A_x改成y。 1 l r 求l到r的最大子段和。 n\le 5\times 10^5,m\le 10^5 分析 看上去线段树很可做。 要求的是最大的连续和,那我们拆区间时就要多维护一些值。 sum_p  子段...

发布 0 条评论

传送门 题目大意 维护一个长度为n的序列。 两种操作: C l r d  l到r加上d Q l r 求l到r的gcd n \le 5\times 10^5 思路 非常毒瘤,没见过这么毒瘤的。 我们知道我们计算gcd时,一般会这样写: C++ in...

发布 0 条评论

中国剩余定理 用来求解线性同余方程组。 x\equiv a_i(mod\ m_i),其中m_i两两互质。   设M= \prod _i^nm_i,M_i=\frac{M}{m_i},M_i关于m_i的逆元inv_i。 由于m_i两两互质,M_i和m_i也必定互质,inv_i肯定是可以求出来的。 那么...

发布 0 条评论

传送门 题目大意 对于任何正整数x,其约数的个数记作g(x)。 例如g(1)=1 g(6)=4 定义如果某个正整数x满足g(x)>g(i)且1\le i\le x-1,则称x为反质数。 现在给定一个数N,你能求出不超过N的最大的反质数么? 数据范围:1\le N\le 2\tim...

发布 0 条评论

传送门 我们可能会遇到一些解线性方程组的问题。 这个时候,我们就需要用到高斯消元。 举个例子: 我们可以先把它转化成一个3\times 4的矩阵。 其中前面3\times 3表示系数,后面3\times 1表示等号右边的常数。 我们发现,类似方程...

发布 0 条评论

传送门 非常有趣的一道题目。 题目大意 坐标系上有n个点,编号为0到n-1每个点的坐标是(x, y) 初始时点与点互相独立。 然后会有m次操作。 给定两个点A,B,把A和B连线,使他们成为一个联通块。 询问一条y=C的水平线与几个联通块内部的...

发布 0 条评论

填坑美滋滋。 割点是什么 如果一个点A是割点,那么在原图删去A点后原图联通块数会增加。 Tarjan 先只考虑联通图。 算法主体是dfs,依赖于一个叫“时间戳”的定义。 时间戳就是说执行这一次dfs是第几次。 emmm可以用这个东西卡时间骗分 ...

发布 0 条评论

C++ #define DREP(i, s, e) for(register int i = s; i >= e ;i--) #define REP(i, s, e) for(register int i = s; i <= e ;i++) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\...

发布 0 条评论