文章

我们已经见证了线性筛有多么强大，它强大到 4·108 内的所有素数可以在 1.6s 内求出， 而普通筛法只需要+1s 。所以这么好的一个算法，可以为你续一秒，何乐而不用呢? 用法 1：筛素数 void get_prime() { int pnum = 0; for(int i = 2; i < 阅读更多…

1. 题目 传送门=￣ω￣= 题意： I C1 C2 K: 把 C1 与 C2 的路径上的所有点权值加上 K D C1 C2 K：把 C1 与 C2 的路径上的所有点权值减去 K Q C：查询节点编号为 C 的权值 有多组数据，n<=50000 2. 题解 树链剖分模板题 树剖以后用线段树维护 阅读更多…

1. 前言 如果给你一棵树，求点 u 到点 v 路径上点的权值之和，你可能会说：倍增啊！ 那如果出题人：我还要你支持修改某个点的权值！ 或者再 j 一点：我还要你支持修改点 u 到点 v 路径上点的权值！ 那就得用树链剖分了。 2. 什么是树链剖分 上面那个问题，树上区间修改。 区间修改最常见做法就 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 树链剖分模板题。 先剖树成链，再用线段树维护一条一条的链。 线段树连懒惰标记都不用，单点修改 代码： #include <bits/stdc++.h> #define LS(a) (a<<1) #define RS(a) ((a&lt 阅读更多…

树链剖分是极其恶心的要用到其他数据结构的一种数据结构（或者说处理策略）。在应用之前，需要熟练掌握树形 Dp，Dfs，Dfs 序，对数相关概念，线段树/Splay/…。这道题就要用到树链剖分。 题意 给定一棵 n 节点树 (n<=５×10４)，和 q 次操作 (q<=105)， 阅读更多…

这是一道挂羊头卖狗肉的题。（虽然我也不知道究竟能不能用线段树解决）但是分块实在是太方便了。 题意 给定一个长度为 n 的序列和一个正整数 k，有 m 次操作。(n,m,k<=105) 每次操作是将一个区间 [a,b] 加上一个数 c，或者询问区间 [a,b] 中是 k 的整数倍的数有几个。 思 阅读更多…

sogou 输入法比较 magic，挺好用，但用着用着就出现 “ubuntu 系统错误” 然后搜狗输入法就 gg 了，连中文都打不了 其实 ubuntu 自带的 fcitx 输入法挺好用的，界面也挺美观。 但是有个问题，打全角中括号 “【】” 时会打出这种东西：·「」十分的有趣 于是第一次搜狗爆炸 阅读更多…

1. 题目 传送门=￣ω￣= 有 n 个数和 5 种操作 add a b c：把区间 [a,b] 内的所有数都增加 c set a b c：把区间 [a,b] 内的所有数都设为 c sum a b：查询区间 [a,b] 的区间和 max a b：查询区间 [a,b] 的最大值 min a b：查询区 阅读更多…

1. 题目 传送门=￣ω￣= 给你 N 个数，有两种操作 1：给区间 [a,b] 内的所有数都增加 X 2：询问区间 [a,b] 能被 7 整除的个数 2. 题解 对于线段树的每个节点，搞个数组 d，d[i] 表示在这个节点表示的区间内，对 7 取余等于 i 的数字有几个。 那么每次区间加 x 就是把数 阅读更多…

1. 题目 传送门=￣ω￣= 题意：一条很长（L）的画板（初始颜色为 1），有 T 种颜色，O 个操作；每次操作将一个区间刷成一种颜色，或者查询一个区间内所含的颜色数。 其中 L<=1e5,T<=30,O<=1e5 TMD 有多组数据 2. 题解 显然线段树 然后因为颜色数不大于 3 阅读更多…