在文章《题解：P14588 [LNCPC 2025] 前线支援》发表评论：

对的，感谢指正

好难写。 ## 手稿  ## 电子版 考虑树上差分，令 $d_u=a_u-a_{fa_u}$（特别地，$d_1=a_1$，并且由于这个东西不好用线段树维护，我们后面单独将它列出来）。那…

## 分析 考虑暴力做法：每次修改一个红球之后可以立刻找到所有包含它的传感器，直接判断传感器里面是不是和为 $1$。这个做法非常暴力，复杂度高达 $O(n^2m)$。 然后想到一种 trick 叫拆区间，即把每一个传感器覆盖的 $[l,r]$ 拆成若干个线段树上的区间，至多 $O(\log n)$ 个，这样就只需要判断…

## 分析 无解当且仅当有两个车挨着，下讨论有解情况。 我们定义一对相互连接的车（即互相能攻击的车）为车对，考虑到对于某两对的车对，有可能可以用一个障碍阻挡（即两组车对相连的线段垂直且有交且交不在端点上），所以令车对为点（其中 $x$ 坐标相同的为左部点，$y$ 坐标相同的为右部点），对能用一个障碍阻挡的点连边，答案为…

## 分析 这种长得很像 dp 但是复杂度显然有问题的题应当考虑贪心。但是发现正常贪心不行，所以考虑反悔贪心。 对于反悔操作，考虑原本选了 $x$，会导致 $x-1$ 和 $x+1$ 选不了。反悔之后，当然希望同时选回这两个数（$x-2$ 或者 $x+2$ 选了的情况之后会说明），于是相当于选下 $x$ 之后往贪心的优…

## 分析 我的代码在 loj 上过了，洛谷评测机太菜了 #50 一直被卡，破防了。 发现 $\sum Y\le 10^5$，考虑对大于等于特定阈值 $B$ 的 $Y$ 直接 $O(n)$ 暴力求，因为这样的询问数量不超过 $\frac {10^5} B$ 个，总复杂度是等同于 $O(\frac {qn} b)$ 的。…

## 分析 考虑将排列看成 $[0,1)$ 间的随机实数列（由于实数列离散化一下就变成排列了，所以可以对应上），考虑对实数列 $p$ 做差分并取小数部分，即 $a_i=[p_i using namespace std; #define int long long const int mod=1e9+7; int qpo…

两年前被搬到过模拟赛里面的题目。 ## 分析 考虑到一列放下两个帐篷之后就不能再放，其实相当于删除这一列，因此直接令 $f_{i,j}$ 表示网格大小是 $i$ 行 $j$ 列的方案数。 按行 dp。对于 $f_{i,j}$ 有四种转移： - 这一行什么都不放，直接删除该行，$f_{i,j}\xleftarrow+f_…

考虑添加 $4$ 个虚拟栅栏，分别是正方形的四个角（一个点也可以作为栅栏），这样问题就变成了围住正方形所需的最少成本，使任意两条栅栏之间的连线不穿过正方形。此时，考虑将栅栏视作点，两条栅栏之间连一条长度为两栅栏距离的边（前提是这个距离画出来不会穿过正方形，否则不符合条件。对于其它的连法，总能找到其中一个栅栏连向某个角，…

## 分析 考虑到它是先找区间再推平的操作，不难想到有 odt。然后因为它这个建设的成本看着就很像逆序对，所以可以把 odt 每个段长度存进树状数组里面，做类似求逆序对个数的东西。这个题就只是把序列上的东西拉到树上了，所以再加一个树剖。求每次的成本是一次 odt 的 perform，之后会立刻对同一区间进行 assig…

## 分析 如果最终的树可分，那么必然是存在一条边把 Group X 和 Group Y 分到两部分，考虑求出这些边（称作可分边）。我们发现如果 dfs 这棵树，那么对于一个点，dfs 序中上一个与其颜色相同的点到这个点的路径上的边都不可能是可分边。除此之外的所有边都是可分边。对于上述情况我们需要的是并查集把路径上的点…

## 分析 选好 $m$ 个物品后，显然从小到大组环最优，否则会多出某个物品的 $C$ 值两次。因此从小到大按 $C$ 排序后区间 $[l,r]$ 中选物品的答案 $w(l,r)=\displaystyle\max_{S\in[l,r],|S|=m}\left(\sum S\right)-2(C_r-C_l)$。考虑四…

## 分析 我说怎么我看这题这么熟悉，原来两年前就在 AtCoder 写过了。 由于开灯（下称 on）关灯（下称 off）操作是覆盖，所以其操作必然在翻转（下称 tog）之前，否则 tog 无意义。 其次 on 区间和 off 区间不可能相交，它们自己也不相交，这个显然。 最后如果两个 tog 区间（$[l,r]$ 和…

这题 $q$ 最多能到 $n$，和让你求出所有 $E$ 的答案没啥区别。 先考虑 $E=1$，不难先通过 dfs 求出 $1$ 号作为度假城市的最多可以省的钱数 $f_1$。对这种选择关键点的题目可以直接考虑换根 dp，转移如图： ![](https://cdn.luogu.com.cn/upload/image_ho…

## 分析 诡异的 kruskal 重构树板子。 考虑直接对图建立重构树，边权为连接两个点的高度 $\max$。这里的重构树与正常的有一点区别，在于它的叶子有点权，为点自身的高度。我们考虑一个点 $u$，令 $nxt_{u,k}$ 表示从节点 $u$ 执行跳高 $2^k$ 次能跳到的最浅节点，不难发现 $k\ge 1$…

前言：经过本文可能可以更容易开盒我（其实本来也只有 $3$ 个人符合条件）。 ## Day $-\infty$ 给学弟们搬了 $40$ 题模拟赛（存疑），本来打算讲的，结果学校组织校运会冲掉了讲课。 ## Day $-\frac \infty 2$ 停课开始一直做题感觉快做不动了。 ## Day $-1$ 摸了一天的鱼…

套路地想到对于询问区间 $[l,r]$ 前缀 OR 只有 $\log$ 种，同理后缀 AND 也只有 $\log$ 种，二分求出来之后把能改变前缀 OR 或者后缀 AND 的位置都从小到大排一下，考虑枚举最终的前缀 OR 值是多少，找到它对应的改变位置，那么它的下一个改变位置必然改了一个后缀 AND（否则前缀 OR 会…

## 分析 若 $r using namespace std; int testcase; void solve() { int n,m,u,r,d,l; cin>>n>>m>>u>>r>>d>>l; vector > c(n+1); for(int i=1;i (R+m-2)/(m-1)+1;i--) c[i][1]…

## 分析 这题一看就非常不可做，再一看值域怎么这么小，考虑枚举答案。枚举完之后只考虑边权不超过当前值的边，问题变成动态加边删边判连通性，因为没有重边以及删不存在的边这种东西，直接上线段树分治即可。 ## AC Code ```cpp #include using namespace std; const int N=…

## 分析 考虑 topo 的过程，我们使用小根堆维护当前所有入度是 $0$ 的点，每次取出最小的那一个继续 topo。对于题目给定的允许加入的 $k$ 条边，我们发现就是用来干预这个 topo 取出最小点的过程的。每次我们要取出最小点之前，如果还有边的额度，我们就可以用某一个点给这个点连边以不让它这么早出现在 top…

## 分析 我们对 $a$ 进行从小到大排序，考虑以下结论： 1. 若 $\exist a_i>i$，则 $i \sum[a_j\ne a_{j-1}]$，输出 `-1`。 5. 不在上两个范围内的 $i$，按照如下方式构造答案：除 $a_j=j$ 的点外，取出与前面这些 $j$ 不同并且互相也不同的 $i-\sum[…

## 分析 先建出 $i\rightarrow p_i$ 的边，得到若干个环，计 $c_i$ 表示长度为 $i$ 的环长有多少（不难发现环长相同的是等价的，后面除掉构造环的方案数即可）。我们发现一次交换两个 $p$ 值在这些环上等价于合并两个环或者拆分一个环。然后考虑倒着做，求出从原排列 $q_i=i$ 出发有多少种交…

考虑这个每次把点分成两部分的操作长得很像一个树形结构，所以可以建出一个二叉树，每个叶子是一个点，现在题目变为“可以交换某个节点的两个儿子的子树，求叶子从左到右走的最短距离（这里的左和右指的是建出树之后的左右，不是原来的点的左右）”。不妨设两个节点 $l,r$ 为某一个节点 $u$ 的最左侧和最右侧叶子，则我们找出 $u…

## 分析 初始局面下，所有给定的点都是 `#`，所有这些点加上 $(-w_x,-w_y)$ 都是 `.`。我们发现对于某一个 `#`，如果它在加上某个别的 $(-w_x,-w_y)$ 后位于方格内，那么鉴于它并没有成为该风的边界，必然有该格子为 `#`。这种 `#` 号的传递有递推关系，可以使用 bfs 扩散出去。同…

## 分析 ~~整场 arc 唯一一道我会证明我的做法的题目。~~ 提供一个 $O(n)$ 做法。我们考虑 $k=2$，必然会构造出 $n+1$ 和 $2n+1$，这个自证不难。这启示我们把序列首项设为 $x+1$，那么我们希望尽可能地吃到余数的加成，自然第二项就是 $2x+1$，第三项就是 $4x+1$，以此类推，第…

## 分析 这题在一长串东西里搜索子串就感觉非常哈希。所以我们考虑将那些随机数中的一个子串的哈希值求出来，但是这样会很麻烦，不好维护。我们将一个原排列给转换为它的逆，即 $b_{i,a_{i,j}}=j$，这样就不需要考虑随机数间的相对大小关系，只需要管位置就行了。初始时，把前 $k$ 个随机数加进 sgt 里面，然后…

在文章《题解：P14094 [ICPC 2023 Seoul R] Special Numbers》发表评论：

补充：k有超过10的质因子中的“无解”指数字中必须含0

## 分析 现在本题仅存的题解未给出详细证明，故稍微写一下。 对于 $\forall i using namespace std; #define int long long inline int c(int x) { return x*(x-1)/2; } void solve() { int n,k,q; cin>…

## 分析 我们考虑一种比较好维护的构造：先尽可能竖着放砖，如果发现缺一格就塞一块横着的砖。接下来就是证明这样放能构造出来是本身能构造出来的充要条件。考虑一组构造，我们先去除连续的横砖，再把它的横砖移到所有竖砖上面，然后重复操作，如图所示： ![image](https://cdn.luogu.com.cn/uploa…

## 分析 首先不难发现旋转夹角 $\alpha$ 必然是某两个点之间连边与 $x$ 轴夹角之一。 关于如何求夹角和旋转后的欧几里得距离：  如图所示，不难发现 $\alpha=\ar…