本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-26 07:42:43

前置

本 caiji 因为 CSP-S 挂大分，然后没资格参加 noip，然后喜提省选锻炼选手。 去年省选的 rp 今年加倍偿还。

2024.2.18

CF 回蓝，近 4 个月的 rating 曲线是个近似下凸壳。 前两个月因为停 OI，rating 狂掉 240，Expert -> Pupil。 然后一步步缓了过来，寒假净增长 240+，差不多抵消。

2024.2.24?

lxn 通知报名。

洛谷有人支持查询初印象。

我的查询结果：caiji。

看来我是真的蒟。

当晚 ABC 先做 G 题，结果愣是没想到 lazytag 不用下传，然后又去学线段树分治，然而没能套用在这题，最后 20min 写了 $O(n \sqrt n \log n)$，TLE 了。

2024.2.25 之前

mx 集训，集训，集训。 想推掉学校上午即将安排的 3 节高中课程，结果是到时候试试。 另外，出了点破题。 原本总共造了 8 个破题 ，但只有 3 个造了数据。 然后又从奥数书上“借鉴”了一个 idea，开大数据范围使得直接抄是 0 分，2024.2.23 造了一上午数据。

然后又造了两道 @KSCD_ 的题的数据。

不得不说 Codeforces 的 polygon 平台好用，std 写挂了，一键重建数据。

2024.2.26

停止集训？

2024.2.27

晚上 Div.3 看了 F,G，都不会，放弃了。 F 题之前被我出过，但以为是不可做就扔了，悲。 $\color{black}\text{I}\color{red}\text{ceturky}$ perf 2200+，Pupil->Expert，orz

2024.2.28

lxn 安排了 10 道 Div.2 C。 前 2h OI 赛制，第 3 h 乐多赛制允许修补。

前 2h 思路上做了 9 题，然而 B 题因为没看清楚样例寄了（最后乐多赛制减分，因此没有榜一），I 题假了。

乐多开始后，尝试修 I 题，然而 40min 了还没修好。

J 题还没看题面，挺慌的，不过还好是一个组合数学的一眼题，用了 15min 通过了。

最终结果通过 A,B,C,D,E,F,G,H,J，rk2（然而有 $\color{black}\text{l}\color{red}\text{sxhyyds},\color{black}\text{I}\color{red}\text{ceturky}$ 等大佬不屑于打)

2024.2.29

28 年一遇的 2.29 + 星期四。

想着把板子都看一遍，然而太摆了。

下午听课，成功解决了一个困扰很久的关于 dp 顺序的问题，心理压力小了很多。

晚上打 CF，原本怕掉分，准备开小号，但得知 chb 和 gwf 都大号，然后成功被激励用大号打。

最后掉了大分。

2024.3.1

按照惯例应当颓废。

开了一局 MC，然而没什么进展。

lxn 来了后暂时收手，但是什么都学不进去。

中午从学校出发。

穿得太厚了，再加上离车站较远，感觉在火炉里。

到了高铁上继续颓 MC，生存模式收集了几个箱子的奇奇怪怪的东西，比如海洋之心，锋利 V，精准采集的金斧。

同时得知了 Rated/Unrated 分开考，挺不舒服的，本来想去见见原来烟台二中队友。

济南还和几年前一样热闹，但我不再是之前那个初学者了。

我和 wcz 一个房间，都是去年 CSP-S 爆炸遗憾没能参加 NOIP 的。

晚上就我和 wcz 去 Unrated 考点，看着冷清的考场，感觉有一种很悲伤的氛围。

草草写了个快读快输就走了。

晚上别人想要复习，我不想去。

过了一会听说他们在聚众颓废，我就去参与了。

在 wjr 的帮助下，我成功首次在 MC 生存模式下找到下界要塞。

然而出乎意料的是，我发射的火焰弹被凋零骷髅打了回去，我来不及举起盾牌就被自己的火焰弹打暴毙了。

一直戴着耳机听 Last Reunion，然而摘下来发现别人都能听见。。。。

Day1

早上去酒店餐厅吃饭。

由于是自助餐，就点了几个甜品，豆浆。

上路！

步行走了感觉挺长的距离到了考点。

考前打板子，意外发现可以联网。

然后询问了监考是否可以复制板子，监考说不可以。

没过多久考试开始。

感觉 T3 不可做，于是我将范围限定为 T1，T2

一开始感觉 T1 可做，就大量时间攻 T1 正解，并且整出了个好像是对的的做法。

然后样例一直寄寄寄，看着只剩 1.5h 了，就去写 T2。

写完 T2 暴力又返回去写 T1，过了小样例，但是大样例寄了。

分析了一下只能证明 T1 在某个特殊性质下是对的。

我手动模拟了大样例，修改后 wa 的 testcases 少了很多，但仍然 wa。

最后调试过程中考试结束。

看到座位表上有 dcy 和 hjr，但是没找到他们。

出考场发现除了 cxm1024，大家都不会 T1。

有些后悔去打 T1 正解了。

下午试图和 wjr 联机 MC，然而一直连接失败，花了一个多小时才修好。

感觉 wjr 好厉害，被带飞了。

看了看犇犇，发现有一些人对 __int128 用 abs CE 了，我赛时也这么干了，还好我赛时开了 C++14 被编译器指出了这个错。

晚上集体出去吃饭，对我来说主要是观赏景色。

蜜雪冰城口感真好！

晚上继续自己的 MC 生存模式存档，通过搜刮下届堡垒遗迹，主世界挖矿获得钻石，制作了附魔台，但是没搞出什么有用的东西。

Day2

出发去合了照，站在 cxm1024 旁边。

试机在代码头里膜拜了 ZGC,LHX,LCQ,PT,GYF,LY,330,HJR,DCY,CXM,CHB,WJR

考试开始先读完了所有题，感觉 T1 最值得做。

于是大量时间投入攻 T1 正解，然而失败了。

但在此期间解决了暴力和 A 性质，并通过对应大样例。

权衡了一下，决定去解决 B 性质，我写了个很长的树形 dp，耗了较长时间写完。

这时候突然想到去检查一下之前写的对不对。

我震惊发现，我判定 n<=4 使用暴力，而 A 性质对应大样例全都是 n=4，也就是说我根本没有测试 A 性质写对了没有！！！

幸运的是，A 性质的代码实际上是正确的。

测了 B 性质，几乎全 WA。

我把调试信息全部输出，并在草稿纸上模拟大样例 3，发现我有个地方漏统计了。

改完之后大部分对了，仍然有一个样例 wa。

我继续调试，然而失败。

只剩 20min 了。

我以我最快的手速写了一个 121 行的暴力，然而没过样例。

干脆输出 1。

最后 1min 打开 T3 源文件，写了以下内容：

不破楼兰终不还

加油！

考完之后沟通了一下，感觉打得不行。

高铁上在 MC 生存里造了一个自动化甘蔗农场。

下车后就不再颓废了，下次颓废计划放到 CSP-S2024 考前，自认为应该平时卷，赛前颓。

听说回来每天还得去提前学高中课程，哎。

回来写游记，结果这个游记洛谷专栏不小心关了，导致丢失，又在 cnblogs 上重写了一份。

晚上出了民间榜，@cxm1024 山东队长！
另外感觉和 chb 等人差距很大。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-26 20:44:01

这个远古时期的 *1900 到现在感觉只有 *1500 难度了，5min 想出正解。。。。。但是调了 0.5h。

• 显然的结论：如果 $x,y$ 两个数有关联，那么 $x$ 和 $y$ 中每一个质因数在 $x,y$ 的质因数分解中出现次数的奇偶必须相同。

• 以下具体内容用来解释。

考虑一下 $\frac{lcm(x,y)}{\gcd(x,y)}$ 的实际意义是什么。

• $lcm(x,y)$
  考虑质因数分解 $x,y$，对于任意一个 $x$ 或 $y$ 中分解出的质因数 $k$，设 $k$ 在 $x$ 中出现 $a$ 次，在 $y$ 中出现 $b$ 次，那么就将 $k^{\max(a,b)}$ 算进 $x,y$ 的 lcm。
• $\gcd(x,y)$
  和 lcm 相反，仍然考虑质因数分解 $x,y$，对于任意一个 $x$ 或 $y$ 中分解出的质因数 $k$，设 $k$ 在 $x$ 中出现 $a$ 次，在 $y$ 中出现 $b$ 次，那么就将 $k^{\min(a,b)}$ 算进 $x,y$ 的 lcm。

两个数相除，造成的影响是什么呢？
假设 $x$ 除以 $y$，那么对于每一个 $x$ 中的质数，其在最后的商的质因数中出现次数等于它在 $x$ 中出现次数减去在 $y$ 中出现的次数。

综上，回到第一个问题，$\frac{lcm(x,y)}{\gcd(x,y)}$ 的实际意义是：假设可以分解质因数成这个形式：$x = a_1^{c_1}\cdot a_2^{c_2}\cdot a_3^{c_3}\cdots,y = b_1^{d_1}\cdot b_2^{d_2}\cdot b_3^{d_3}\cdots$，那么 $\frac{lcm(x,y)}{\gcd(x,y)}=a_1^{\max(c_1,d_1)-\min(c_1,d_1)}\cdot a_2^{\max(c_2,d_2)-\min(c_2,d_2)}\cdot a_3^{\max(c_3,d_3)-\min(c_3,d_3)}\cdots$

另外，完全平方数的每个质因数在其因式分解中的幂都是偶数。
综上，显然可以证明开头的结论。

另外开头结论又可以推出一个实用的小结论，即两个关联的数的奇数次幂的质因数列表都是相同。

问题是现在也只解决了 $O(n)$ 操作一秒钟内的变化，而题目最多有 $10^{18}s$，还需要继续挖掘性质。

想一下每个数操作后会发生什么变化。

所有相关联的数进行乘积，相同质因数的次幂会相加。

另外注意，相关联的数的相同质因数的次幂的奇偶都是相同的，而我们只关心幂的奇偶，所有可以再根据 $d_i$ 讨论。

显然有以下结论：

• $d_i$ 为奇数
  对于每个质因数，操作完之后其次幂的奇偶不会改变。
• $d_i$ 为偶数
  每个质因数操作完之后其次幂都变成偶数。

第一秒操作完之后，不难发现所有能改变的数都改了，剩下的数其质因数的次幂无论如何不会再改。

也就是说原题的 $10^{18}$ 秒就是个诈骗，第 $1$ 秒和第 $t \gt 1$ 秒答案是一样的。

只需要算出 $0,1$ 秒的答案。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-26 21:53:02

应该是 3500 里面比较简单的了，至少一遍看懂了题解，刚刚手动重新推导了本题做法，记录一下大概。

先考虑计算出单个排列的贡献。
看着这个式子没啥好下手的，先拆成 $i,j$ 分别的贡献相加的形式。
然后发现可以表示成外层 $i$，里层 $j$ 的套壳 simga 形式。
然后稍微转化一下发现这个这个式子可以用表示成 $\sum_{i=1}^n i(i-p_i)$

然后推导出每个数的期望位置，然后就算出答案了。

UPD:

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-06 13:42:57

被 lxn 用来当模拟赛了。
打得稀烂。
赛后用了不少时间推完除了 Ex 所有题做法。

• D 题连值域范围不看，就整了个很长的线段树上去，WA 样例了才知道做法假了，然后改成 deque 实现的一个类似启发式合并的东西。最后数组开小爆零了，不开小就能过。
• F 题最后时间不够用，想出了区间 dp ，但是赛时傻逼，顺序处理搞错了，而且忘写记忆化了（然而过了所有样例！！！！！），最后甚至还不如骗分的得分多。
• G 题，赛时没做，但感觉还是一个比较简单的容斥板子，赛后自己推导做法 AC 了。

最后垫底了。

C

模拟

D

我会两种做法

• 第一种：
  离散化，然后对于每个线段维护一个 deque，每次分裂优先把较小的段分裂出去，这样类似于启发式合并，复杂度 $O(n \log n)$ ，但是 deque 的空间占用巨大，我开了 1e5 个 deque，用了 700+ MB，还是手写链表更保险。
• 第二种：
  本质上，只需要知道 $x$ 左右两边最近的端点。
  用 set 维护所有的断点就可以了。

E

观察发现，新插入的元素可能破坏原来元素的有序性，所以干脆分成两个集合，将会破坏有序性的元素单独放。

维护两个集合：按照从小到大排序的集合 $s$，按照插入时间排序的集合 $t$。

显然 $s$ 中的元素比 $t$ 中插入时间早，查询第一个元素优先查 $s$，再查 $t$。

如果进行排序，那么将 $t$ 所有元素插入 $s$，再清空 $t$ 就可以了。

F

一眼区间 dp，设 $dp_{l,r}$ 代表区间 $l,r$ 全部消除的方案数。

然后想想怎么拆成子任务。

显然只需要枚举 $l$ 与哪个点一起出去就可以了。

假设 $l,rg$ 一起出去，那么如果不考虑顺序，答案就是 $dp_{l+1,rg-1} \cdot dp_{rg+1,r}$。

但现在，$[l+1,rg-1]$ 区间和 $[rg+1,r]$ 区间可以交替执行操作，那么只需要求出有多少种交替执行的顺序就可以了。

可以这么想：左边的区间有 $\lfloor \frac{rg-l+1}{2} \rfloor$ 次操作，也就是说有 $\lfloor \frac{rg-l+1}{2} \rfloor+1$ 个空（包括左右两端以外），而右边有 $\lfloor \frac{r-rg}{2}\rfloor$ 次操作，现在需要将它们插入到这些空，或者说把这 $\lfloor \frac{r-rg}{2}\rfloor$ 个操作分到 $\lfloor \frac{rg-l+1}{2} \rfloor+1$ 个可空集合里面，求方案数，这个 OI-wiki 组合数基础上有。

然后没了。

G

下面是我一步步推导出本题的草稿：

mod M= 0:
mod M= 1:
mod M= 2:
mod M= ...:
注意到，由于两个模 M 结果相同的数不能放在同一个组，也就是对于每个同余组合，都要进行排列，选择前往的组。
设模 M 同余 i 的，有 $siz_i$ 个，总共 $k$ 个组，则有 $C(k,siz_i)$ 的方案数选择组，再乘上 $siz_i!$ 代表排列数。
但是，现在要求 k 个组都不能空，也就是说，不合法方案为：存在至少一个组，满足任意模 M 同余集合都不选择它。
具体如何计算呢？
先不考虑集合不能为空，计算出总方案数，然后减去 （满足限制 1，但是有组为空 的方案数）
注意到，假设有 i 个组是空的，那么 C(k,i) 种选择组的方案数，然后呢，对于每个同余集合，只剩下 C(k-i,siz) * siz! 种合法的方案，然后每种集合方案数乘起来
也就是说，如果分组数量确定为 k，那么枚举空的数量 i，但是每枚举一个 i，每个同余集合的答案就变了，还得重新计算。
显然不可接受，考虑如何 O(1) 从 k,i-1 继承到 k,i，设 n=k-i，m=siz 则 继承后，n-=1，原来是 $fact[n]/fact[m]/fact[n-m]$，现在是 $fact[n-1]/fact[m]/fact[n-1-m] = (fact[n]/n)/(fact[m])/(fact[n-m]/(n-m)) = fact[n]/fact[m]/fact[n-m]/n * (n-m) = C(n,m)(n-m)/n= C(k-i,siz)(k-i-siz)/(k-i)$
感觉上面不太好处理，所以是否可以枚举预处理对于任意 n,m，C(n,m) 的值？
然后，注意到，对于每个集合的组合数，其选择 必然等于 siz，所以可以仅枚举 $k-i$ 的值，预处理出对应的方案数总和。
接下来就好办了，这样做应该就可以了：
枚举分组 $k$，先计算出允许空组但模 M 意义下相同的两个数不能在同组的情况下的总方案数（记为 $sum_1$），然后通过容斥计算出必须有空组，且模 M 意义下相同的两个数不能同组的方案数（记为 $sum_2$），则答案是 $sum_1 - sum_2$
但是注意题目说两种情况不同，当且仅当两个数在第一种情况同组，第二种情况不同组，也就说分成的所有组没有编号，易知，$sum_1 - sum_2$ 统计的情况数是按组有编号计算的，题目的每种不同情况都会被统计 $k!$ 次，所以最后真正的答案是 $\frac{sum_1-sum_2}{k!}$

Ex

没看题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-13 14:30:15

赛时没开 long long 吃了 5 个罚时在这题。

做法

先计算出 $a_{i+1}-a_i$ 的最大值，如果这个最大值多次出现，那么显然答案无法改变，直接把最大值输出就行。

然后，考虑如何搭配 $f,d$ 使得插入后的值能更好的减少最大值。

显然，设最优方案为 $f_i+d_j$，另设 $a_{p+1}-a_p$ 是 $a$ 相邻元素差值的最大值。那么 $f_i+d_j$ 应尽可能均分 $a_{p+1}-a_p$，也就是说 $f_i+d_j$ 应尽可能接近 $\frac{a_{p+1}-a_p}{2}$。

此时解决方案已经很明显了。

枚举 $f_i$，并二分 $d_j$，找出使得 $f_i+d_j$ 能达到的最大的小于 $\frac{a_{p+1}-a_p}{2}$ 的值对应的 $d_j$，以及使得 $f_i+d_j$ 能达到的最小的大于 $\frac{a_{p+1}-a_p}{2}$ 的值对应的 $d_j$。以上操作用 lower_bound 就可以解决。

注意计算 $\frac{a_{i}+a_{i+1}}{2}$ 如果先加后除，那么会爆 int，我赛时因此吃了 5 个罚时。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-13 15:04:24

赛时因为这题没有 AK，有点遗憾。
赛后写了个朴素分层图做法 TLE on test47，参考了 @Iceturky 的代码后 AC，本题解大概是我对 @Iceturky 代码的理解。

做法

首先，有一部分普通的暴力分层图是错的，原因，但很神奇的是它们都过了 pretests，虽然最后死于 FST。

显然，同一种颜色的边在最优路径上都是连续的。

所以说，假设目前到达了第 $i$ 个点，且上一个边颜色是 $j$，那么我们可以在任意颜色为 $j$ 的边上瞬移。

也就是说，我们主要关心两个变量：当前在哪个点，到达当前点的上一条边的颜色。

感觉瞬移有点难处理，按上述定义建立分层图很容易寄（如果有分层图做法不会寄，希望有人告诉我）。

于是干脆将每个颜色都建成一个点，反正相同颜色可以互相瞬移。

对于每个点，它都可以进入它的所有的边的颜色对应的连通块。就是说对于每个点 $i$，设其所有边的颜色的集合是 $s$，那么 $i$ 和 $s$ 中每个元素连无向边。

最后，不难想到最优路径中，每个点在上述连边状态下都会访问一次自己所在的连通块节点，所以最后 $b$ 到 $e$ 最短路长度除以 $2$ 就是正确答案。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-14 20:05:49

题外话

代码量挺大，赛时没想到思路，会了思路后写了半个点才过

思路

考虑最优路径是什么。
显然，每个点如果需要购买，那么需要购买的物资应该在起始节点到本节点路径中价格最便宜的节点购买（$p$ 值最大）。

换句话说：

假设最优路径路径上第 $a_1,a_2,\cdots,a_l$ 点进行了购买操作。
那么不存在 $j \lt a_i$，满足 $p_j \gt p_{a_i}$。

现在我们要考虑什么 dp 状态已经清晰了：

• 目前所在的节点
• $(1,1)$ 到当前节点路径上的最低价格

另外，对于 dp 值，首先需要维护题目要求的最少操作次数，其次，还需要计算到达当前节点剩余的物资。

dp[i][j][k][l] = pair<int,int>

维护个 queue 跑 dp 就搞定了（其实就是 bfs）
复杂度 $O(n^4)$。

submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-24 12:07:37

赛时过 ABCDEF，同时想出了 G 题正解但没时间写了。

A

模拟。

B

注意 $W,B$ 很小，所以实际合法区间的 $l,r$ 也不会很大。
把 S 设置为暴力重复 500 次 wbwbwwbwbwbw 差不多肯定可以了。

然后暴力枚举合法区间。

C

先算出 $1$ 到 $K$ 的和，然后依次减去里面出现过的就可以了。

D

我是比较麻烦的分类讨论做法。
先思考下 dp 有哪些需要关注哪些状态？

• 目前枚举到了第 $i$ 个字符，计算前 $i$ 个字符组成的字符串的答案。
• 另外，转移的时候发现，我们似乎不知道第 $i-1$ 个字符是什么，没法转移。所以加入状态：第 $i$ 个字符是什么？
• 另外还要注意一点：正好有一对相邻值相等，那么我们还需要考虑另一个状态：前 $i$ 个字符是否已经存在一对相临值相等？
• 我们还需要求出最小代价，这个加入 dp 值就可以了。

综上，设置 $dp_{1 \le i \le n,a \in (0,1),b \in (0,1)}$ ，注意 $a$ 代表真，$b$ 代表假，那么这个 dp 代表前 i 个字符，且第 $i$ 个字符发生变化的真假为 $a$，前 $i$ 个字符存在一对相邻值相等的真假为 $b$，此时最小操作代价。

转移：

#define FOR(i,a,b) for(int i=a;i<=b;i++)
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
dp[1][0][0] = 0;
dp[1][1][0] = c[1];
FOR(i, 2, n)
{
    \/\/ case1: 上一个不变
    if (s[i - 1] == s[i])
    { \/\/ 和上一个相同
        \/\/ ca1: 这次变，不会影响相同数量变化
        ckmn(dp[i][1][1], dp[i - 1][0][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][0][0] + c[i]);
        \/\/ ca2 这次不变
        ckmn(dp[i][0][1], dp[i - 1][0][0]);
    }
    else
    {
        \/\/ ca1：这次不变，不影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][0][1]);
        ckmn(dp[i][0][0], dp[i - 1][0][0]);
        \/\/ ca2: 这次便
        ckmn(dp[i][1][1], dp[i - 1][0][0] + c[i]);
    }

    \/\/ case2：上一个变
    if (s[i - 1] == s[i])
    {
        \/\/ ca1：这次不变，不会影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][1][1]);
        ckmn(dp[i][0][0], dp[i - 1][1][0]);
        \/\/ ca2: changed now
        ckmn(dp[i][1][1], dp[i - 1][1][0] + c[i]);
    }
    else
    {
        \/\/ ca1: 这次变，不会影响相同数量
        ckmn(dp[i][1][1], dp[i - 1][1][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][1][0] + c[i]);
        \/\/ ca2:  not change
        ckmn(dp[i][0][1], dp[i - 1][1][0]);
    }
}
printf("%lld\n", min(dp[n][1][1], dp[n][0][1]));

E

以下，可能会用括号代表一个整体。

考虑每次操作实际会有多少影响。

显然，第 $i$ 次操作的影响为：第 $i$ 次覆盖的点数 - （($\cup_{j=i+1}^M$ 第 $j$ 次操作覆盖的点集）$\cap$ (第 $i$ 次覆盖的点集)）的大小

而这个怎么处理呢？

• 如果存在 $j \gt i$，使得第 $i,j$ 次操作相同，那么第 $i$ 次操作可以忽略。

• 否则，第 $i$ 次操作实际贡献为第 $i$ 次覆盖点数 - 第 $j \gt i$ 次操作中与第 $i$ 次覆盖方向不同的操作数量。
  倒着算就可以了。

F

单调性是显然的，可以二分 $k$。

然后，其实没啥技术含量的，判定是否合法，只需要枚举每一位模拟就行。

细节不少，但是没啥记录的意义，唯一要注意的是 check 过程可能会爆 long long。

G

直接做不好做，那么反过来考虑每个元素对哪些 $[l,r]$ 有贡献。

假设目前是第 $i$ 个元素，$p$ 是最小的 $p$ 满足区间 $[p,i]$ 只存在一个 $a_i$，$q$ 是最大的 $q$ 满足区间 $[i,q]$ 只存在一个 $a_i$。那么显然，对于所有的 $p \le l \le i,i \le r \le q$，区间 $[l,r]$ 合法。

注意到这里的贡献对 $l$ 和 $r$ 各进行了一个区间范围的限制，而上面实际上可以抽象成一个二维平面，所有满足 $p \le l \le i,i \le r \le q$ 的点 $(p,q)$ 都可以计入最终贡献，也就是说它实际上将一个矩形内的所有整点加入了最终贡献。

最终答案可以转换成，有多少点 $(p,q)$ 满足 $1 \le p \le q \le n$，且被任意一个矩阵覆盖过。

这个东西扫描线搞定。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=2e5+5;
int n;
int a[maxn];
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
\/*
对于每个 i，设有效区间 [a,b]

那么对于区域 [a<=l<=i][i<=r<=b] 所有点都有解
加入矩阵即可。
然后扫描线求出矩阵面积并，然后就是答案。
*\/
vector<int> pos[maxn];
struct Matrix{
	int x_l,x_r,y_l,y_r;
}matrix[maxn];
Matrix mkmt(int a,int b,int c,int d){
	Matrix res;
	res.x_l=a,res.x_r=b,res.y_l=c,res.y_r=d;
	return res;
}
int cntmat;
struct Seg_Tree{
	int cov[maxn<<2];
	int len[maxn<<2];
	int L[maxn<<2],R[maxn<<2];
	void build(int pos,int l,int r){
		L[pos]=l,R[pos]=r;
		if(l==r){
			return;
		}
		int mid=(l+r)\/2;
		build(pos*2,l,mid);
		build(pos*2+1,mid+1,r);
	}
	void pushup(int pos){
		if(cov[pos]){
			len[pos]=(R[pos]-L[pos]+1);
		}else{
			if(pos*2<maxn*4){
				len[pos]=len[pos*2]+len[pos*2+1];
			}else{
				len[pos]=0;
			}
		}
	}
	void chg(int pos,int l,int r,int add){
		if(L[pos]>=l&&R[pos]<=r){
			cov[pos]+=add;
			pushup(pos);
			return;
		}
		if(R[pos]<l||L[pos]>r)return;
		int mid=(L[pos]+R[pos])\/2;
		if(mid>=l)chg(pos*2,l,r,add);
		if(mid<r)chg(pos*2+1,l,r,add);
		pushup(pos);
	}
	int getsum(){
		return len[1];
	}
}sgt;
struct Line{
	int y_up,y_dw,x;
	int add;
}line[maxn*2];
void solve(){
	scanf("%d",&n);
	FOR(i,1,n){
		scanf("%d",&a[i]);
		pos[a[i]].emplace_back(i);
	}
	FOR(i,1,n){
		for(int j=0;j<pos[i].size();j++){
			int l=1,r=n;
			if(j!=0){
				l=pos[i][j-1]+1;
			}
			if(j+1!=pos[i].size()){
				r=pos[i][j+1]-1;
			}
			matrix[++cntmat]=mkmt(l,pos[i][j],pos[i][j],r);
	\/\/		printf("add  = %d %d %d %d\n",l,i,i,r);
		}
	}
	assert(cntmat==n);
	FOR(i,1,cntmat){
		line[(i-1)*2+1].y_up=matrix[i].y_r;
		line[(i-1)*2+1].y_dw=matrix[i].y_l;
		line[(i-1)*2+1].x=matrix[i].x_l;
		line[(i-1)*2+1].add=1;
		
		line[(i-1)*2+2].y_up=matrix[i].y_r;
		line[(i-1)*2+2].y_dw=matrix[i].y_l;
		line[(i-1)*2+2].x=matrix[i].x_r+1;
		line[(i-1)*2+2].add=-1;
	}
	sort(line+1,line+cntmat*2+1,[&](Line& a,Line& b){
		return a.x<b.x;
	});
	sgt.build(1,1,n);
	ll s1=0;
	line[cntmat*2+1].x=n+1;\/\/占位
	\/\/ 注意到，有些线段可能会到达 x=n 位置，此时贡献
	FOR(i,1,cntmat*2){
		ll len=line[i+1].x-1-line[i].x+1;\/\/ 当前纵线的有效长度
		sgt.chg(1,line[i].y_dw,line[i].y_up,line[i].add);
		s1+=(ll)sgt.getsum()*len;
	}
	printf("%lld\n",s1);
}
int main()
{
    int T=1;
	while(T--){
		solve();
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-26 09:28:43

https://www.luogu.com.cn/contest/146539

https://www.luogu.com.cn/team/1759#problem?page=17 ，本场题目是公众可见。

听 HaoBa 课的缘故晚了 2.5h 参赛，没想到抢到了 F 题首 A 同时也是唯一 AC，遗憾的是 G 题没时间写了不然能再得到一个气球。

E

https://www.luogu.com.cn/problem/T401411

注意 $A \le B \le C$ 的一个很好的性质：$A$ 最多枚举到 $n^{\frac{1}{3}}$，$B$ 最多枚举到 $\sqrt {\frac{n}{A}}$，$C$ 可以直接计算。

F

https://www.luogu.com.cn/problem/T401117

建图然后 BFS。

具体建图方式为枚举每个点以及横向伸展长度，然后计算出纵向。

G

https://www.luogu.com.cn/problem/T396540
显然应将其中一个升序，另一个降序，

$A,B \le 200$ 意味着可以桶排序，然后双指针扫就行。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-03 00:51:19

由于 F 题 2800 的评分，没时间补完了，先放上前 5 题。

感觉这次 E << D，赛时没做 E 有点亏。

A

如果存在连续 3 个空位置，那么答案显然最多是 2。

其余情况统计空位数量即可。

B

假设只剩下 $a$，被消耗掉的是 $b,c$。
略微思考可发现，主要在于如何让 $b,c$ 数量相等。
而不管怎么操作，$b,c$ 数量差的奇偶不变，所以根据奇偶判断就行。
数量不用担心，只用看奇偶。

C

树形 dp 基础题。
设 $dp_i$ 为 $i$ 到其子树叶子节点的最小操作次数。

后面懒得写了。

D

欧拉函数求两两 gcd 之和 + 分块算法
为了方便，如果两数相同，编号靠前的小。

排个序然后枚举 $b$ 的位置，计算 $b=i$ 时，对于所有可能 $a$ 的 gcd 之和（参照如何计算两两 gcd 之和，可以容斥），另外计算出多少种 c 时可行的。

然后没了，赛时计算两两 gcd 之和是抄的网上板子（按 CF 规则不违规），最后一刻提交，变量名 data 撞标准库 CE 了，赛后加 namespace 过了。

E

为数不多的独立解出的 Div.2 E，可惜是赛后。

考虑原题加边带来的影响。

原图能沿着什么路径走，现在仍然能且只能按照什么路径走。

为什么这么说呢？

现在的图，每一个点向所有原来途中自己能到达的点连了边。

虽然现在的图不允许路径重复经过点，却可以跳跃到达按照原图路径能到达的点（假设原图中允许重复经过点）

本质上问题转化成，给你一张图 $G$（就是原始图），可以重复经过点，要求找出最长路径，同时满足权值和最小。

这个问题 tarjan 缩点+拓扑排序 dp 就能解决。

F

待完成。