在讨论《关于记忆力问题》回复：

@[How1ver](luogu://user/510823) 可以重开了

模拟赛题，经典套路，断环成链。 两条弦有交当且仅当其对应区间有交且无包含关系。 具体地，对于弦 $(l,r)$，与其相交的弦应该满足 $(l_i r_i)$。 满足的条件是互斥的，算两次。 第一次将弦按照 $l$ 升序排序做二维数点，第二次同理。 时间复杂度 $\Theta(n\log n)$。 ```cpp #inc…

观察到 $100$ 以内的质数只有 $25$ 个，这是一个很好的折半搜索的数据范围。 考虑一个中间值 $B$，搜出 $\le B$ 的所有情况和 $>B$ 的所有情况，枚举一下拼起来即可。 这里只用选取一个合适的 $B$ 就可以了。打个搜索出来看一下数据规模，发现取 $B=8$ 非常优秀，开销在对 $>B$ 部分的排序…

# [F - Rated Range](https://atcoder.jp/contests/abc389/tasks/abc389_f?lang=en) 先离线，发现初始时 $X<Y$，那么从开始到结束的所有过程 $X\le Y$，即相对顺序不发生改变。 把询问的每个值拍到序列上，发现一次操作的影响是一段区间。 为…

定义：$s,t$ 的汉明距离定义为 $$\sum_{i=1}^{|s|} [s_i \not = t_i]$$。 ## [P9187 [USACO23OPEN] Field Day S](https://www.luogu.com.cn/problem/P9187) 给点 $n$ 个长度为 $c$ 的字符串，对每一个字…

结论题。 要求 $a$ 所有子区间与 $b$ 的汉明距离为偶数的数量。 这里先给出结论：设 $a$ 中 $1$ 的个数为 $x$，$b$ 中 $1$ 的个数为 $y$，$a$ 和 $b$ 的汉明距离为偶数当且仅当 $x \equiv y \pmod 2$。 ::::info[证明]{open} 不妨令 $x > y$，…

首先可以发现只有两种边界：延续之前的填法，或者顶着当前喷泉选。这一点是好证的，从样例解释也可看出。 考虑哪些喷泉会被顶着选：不存在 $x$ 比它大的喷泉，$y$ 比它小。这说明如果按 $x$ 排序，他的 $y$ 一定是后缀最小值。 知道怎么填这个题就做完了，第二问 $a_i = 1$ 说明它是严格后缀最小值。 ::::…

在讨论《洛谷入门赛 #41 赛时答疑》回复：

@[xiehy](luogu://user/677626) 厉害

# 1 有 $n$ 个点和 $m$ 条边，点编号依次为 $0,1,\cdots, n-1$。 如果一个点的三元组 $(i,j,k)~(i<j<k)$ 两两**没有边**相连，那么它的贡献为 $A\times i+B\times j+C\times k$。 求出所有三元组的贡献和。 如果采用容斥原理，将所有 $(i,j,…

# 一阶差分和多维差分 ## 一阶差分 $b_i = a_i - a_{i-1}$，定义 $b$ 为 $a$ 的差分数组。 注意到 $\sum_{i=1}^{i} b_i = a_i$，差分为前缀和的逆运算。 ::::info[应用]{open} 对数组 $a$ 的修改 $a_i \gets a_i + v, i\in…

# 一阶差分和多维差分 ## 一阶差分 $b_i = a_i - a_{i-1}$，定义 $b$ 为 $a$ 的差分数组。 注意到 $\sum_{i=1}^{i} b_i = a_i$，差分为前缀和的逆运算。 ::::info[应用]{open} 对数组 $a$ 的修改 $a_i \gets a_i + v, i\in…

在讨论《如果题目改成这样还能做吗？》回复：

@[panzhouao](luogu://user/973352) 是对的，感谢

在讨论《如果题目改成这样还能做吗？》回复：

@[panzhouao](luogu://user/973352) 细说 $\sum 1$ 怎么求，感谢

求 $\sum (a_i - 1)^2$

# 朴素的背包

一个人能收到礼物的条件是：他带了礼物，有人给他带了礼物。 建图 $i \to p_i$ 代表 $i$ 能给 $p_i$ 提供礼物。不难发现原图是多个环。 第二问很好做，不给一个人提供礼物会造成 $2$ 的贡献（$i$ 和 $p_i$ 不能收到礼物）。特别地，长度为奇数的环可以消耗 $1$ 而得到 $1$ 的贡献，这个最…

# [思维](https://www.luogu.com.cn/training/607752#problems) ## T1 最短路状物，最多只会走 $1000$ 天，$f_{u,t}$ 表示在第 $t$ 天走到 $u$ 的最大价值，有向无环图，跑什么都行。 时间复杂度 $\Theta(nT)$。 [code](ht…

先考虑最小值怎样求得。 建图连边，对每个怪物建点 $1\sim n$，对于每个限制建立虚点，虚点向原怪物连边，边权是爆出的钻石数量，新怪物往虚点连边，边权是这个怪物的个数。 开始是先从只能爆出钻石的怪物开始，如果不存在只能爆出钻石的怪物，说明每个点至少有一条边连向其他点。这样形成了一个内向基环树森林，怪永远打不完。 然…

T1 过大样例，先打网络流后打贪心，用时较长。 T2 忘删边，但分段打了，48左右。 T3 写了玄学算法，期望n^2。 T4 没时间打。

厉害的一道题。 将无根树变换为以 $1$ 为根。直接做肯定不行，总点数是很多的，但 $d\le 40$，启示我们将管辖的信息缩小到这个范围。 令 $tag_{u,i}$ 表示 $u$ 的子树内与 $u$ 距离 $i$ 的点需要乘上的值，那么求 $u$ 的权值只用依次往上跳。 接下来考虑修改，发现 $tag_{u,i}$…

普通矩阵乘法： $$ C_{i,j} = \sum_{k=1}^{A.m} A_{i,k} \times B_{k,j} $$ 定义两个新运算 $\oplus,\otimes$，广义矩阵乘法： $$ C_{i,j} = \bigoplus_{k=1}^{A.m} A_{i,k} \otimes B_{k,j} $$ 想…

# mx1 赛：85 + 24 + 40 + 0 补：100 + 100 + 100 + 24 总结：$10^6$ 不能双 $\log$，注意题目没写在数据范围里的部分分。 ## [P110120 宇宙（universe）](https://www.mxoj.net/problem/P110120?trainingNu…

撤销的时候符号不要反了

限定范围的最长不降子序列与最长不降子区间

模拟赛题。 连接 $(i,j)$ 两点后，新直径只可能为 $d_1,d_2,dis_i+dis_j+1$，其中 $dis_i$ 为 $i$ 在 $T_1$ 中最远的点的距离，$dis_j$ 为 $j$ 在 $T_2$ 中最远的点的距离。 $d_1,d_2$ 两次 BFS 求出，关键在于 $dis_i,dis_j$ 怎么…

模拟赛签到题。 做过 [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839) ，中位数的经典套路。 考虑二分答案 $v$，将数组中 $ #define umap unordered_map #define vint vector #define ll…

# C 环上平移，设一个 $\Delta$ 直接算。 # D $f_{u,S}$ 代表到 $u$ 点能否凑出 $S$，总状态数

# 数据结构 ## 线段树 ### 线段树维护方差 ```cpp struct seg{ struct node{ int l,r; db sum,x2,add; }tr[N >1; build(ls(p),l,mid),build(rs(p),mid+1,r); pushup(p); } void update(in…

# C ## 题目分析 首先有一个很显然的贪心，如果当前骨牌的大小为 $x$，我们一定会选择 $\le 2x$ 且最大的骨牌作为下一个，这样能使我们用更少的骨牌接近目标大小。 接下来找到这个值就行了，答案显然满足可二分性，直接二分即可。 时间复杂度上界是 $\Theta(n \log n)$ 的，但事实上根据官方的题解…

# 题目分析 有 $m$ 次操作，每次交换两个数，求出交换后的逆序对数。 先离散化，然后考虑在线地维护这个过程。假设我们交换了 $l,r(l h_r]} - \sum_{i=l+1}^{r-1}[h_i h_r] + \sum_{i=l+1}^{r-1} [h_i h_l] $$ 发现这是求区间排名问题。 同时交换操作…