二元操作关系，我们不妨直接考虑建图。容易发现若把每次操作的 $(u,v)$ 连边后，由于每条边需要对应一个点，则每个连通块的边数不超过点数。且根据连通块定义，边数至少是点数 $-1$。即每个连通块为树或基环树。 令连通块点集为 $S$，容易发现树的定向方案数为 $|S|$（钦定某个点还未被选择），基环树的定向方案数为…

很容易发现竞赛图中一定能找到一个点到其余点的距离 $\le 2$，也就是说最终图的第 $0$ 层与第 $1$ 层的点会形成菊花，而第 $1$ 层的点与其所管的第 $2$ 的点同样也会形成菊花。 我们考虑增量维护前两层的结构。对于新加的点 $x$，先访问第一层的点，若存在一个点连向 $x$ 则可以直接加入进这个点的管辖集…

超级分讨题吗，哈哈那无敌了。 这种题可以先想一下怎么做多项式复杂度。考虑一个点的度数至多为 $3$，因此我们可以分类讨论一下有关其交换的顺序。我们发现在交换了 $x$ 与 $fa_x$ 之间的边后 $x$ 子树内为独立问题，可以想到记录子树型状态。 那么我们要记录什么样的状态呢？显然我们关心 $x$ 与 $fa_x$…

观察原序列与最终保留序列的关系：首先原序列中 $h_i = n$ 的两个位置中靠后的位置一定会保留下来。原因是它后面的位置再出现一个 $n$。此刻靠前的位置变为 $n-1$。 然后再加入原序列中 $h_i = n-1$ 的两个位置，现在这三个位置中最靠后的也会被保留下来，原因相同。再往后加入 $h_i \in [1,n…

怎么大家都会拆贡献？来写一篇与拆贡献无关的做法。 若对每个点 $u$ 钦定其儿子访问顺序，我们发现 $f(x,y)$ 等于 $x\to y$ 路径上的最小点权或每次 $u\to v(y\in subtree(v))$ 之前 $u$ 访问的其他儿子的子树最小值。即若干个子树 $\min$ 与单点点权取 $\min$ 的形…

# 前言 你猜为啥是 "5"？ # Day -inf NOIP 拿到了 348. # Day 0 去福州，干了啥我忘了。 # Day 1 早上起来没发生啥。 进场，看了 T1 秒了。写了。看了 T2，小想了一会，研发了一个 $O(\frac{nq\log n} w)$ 的唐氏做法。写了，大样例 7.1s。扔了。写 T3…

/tx/tx/tx 签到。桂花树。天天爱打卡。 开题顺序正确的情况下相当于约 3.5h 做一题。然后这题是桂花树式的部分分设计。 去写 A 构造的输麻了。永远只想着“稳健”是这样的。 noip 和 wc 我都是 FJ 在役选手 rk7。但是前面 6 人交集为 1。 wc rk10 ~ rk60 差了 12 分。 /xk…

在文章《EC-Final 2024 游记》发表评论：

三颗“孤星“不仅指代强大的自己与带领的队友，同时象征着为了队友吹过的三个气球，作者自喻为夜空闪烁的星斗，展示了自己强大的算法竞赛能力、出色的团队领导能力以及充沛的肺活量。

在文章《EC-Final 2024 游记》发表评论：

作者使用环境描写，太阳日落西山，由红色转向橙黄色，分别象征着作者由 G 题转战 F 题却最终还是遗憾离场的失落与不甘；作者看着”东方的黯夜“，不禁想到明日冉冉升起的太阳，如同未来在 ICPC WF 上吹起的一颗颗气球，表达了作者渴望重铸中国算法竞赛荣光的使命与信念。

在文章《EC-Final 2024 游记》发表评论：

日落西山的太阳将西方的天空染成昏黄，暗橙色的天幕渐变成东方的黯夜，三颗孤星悬挂在夜空之上，见证着这个古城和城墙的前世今生。

# CF1930H 概述：交互库给你一棵树，你需要在所有询问开始前给交互库两个排列 $p1,p2$，随后交互库每次生成一个排列 $a$ 与两个点 $u,v$，要让你求树上 $u,v$ 路径间 $a_i$ 的 $mex$，你可以询问 $5$ 次两个排列上的区间最小值。$n\times q\le3\times 10^6$。…

概述：给出一个长度为 $n$ 的排列 $a$ 与 $q$ 个区间 $[l_i,r_i]$，称两个区间本质不同当且仅当二者的小根笛卡尔树不同构，求这 $q$ 个区间中有几种本质不同的区间。 思路：考虑该区间笛卡尔树形式，发现其左链为从 $l$ 不断往右边比当前值小的位置跳直到跳到最小值，右链同理，除左右链外与原序列笛卡尔…

笨方法做题。 考虑如何找出最大的需要保留的点，发现我们可以二分点权值 $x$，删掉比 $x$ 大的点后看是否存在一个连通块具有所有颜色。这样我们就在 $O(n\log n)$ 时间内找到了一个答案的必须点。 接下来我们先视为保留 $[1,x]$ 的所有点，然后再进行删点。将 $x$ 视为根，则我们后面要删掉点 $u$…

在文章《NOIP2024 游记》发表评论：

呃呃

好题。 考虑对于一个给定的 $b$ 序列如何 check。有一个 $O(n^2)$ 的 $f_{l,r}$ 表示前 $r-l+1$ 大的 $b_i$ 能否放进 $[l,r]$ 中。但是这明显没有利用完全性质。 将 $b$ 从大往小排序，若存在一个长度 $\ge i$ 的包含 $j$ 的连续段，满足其中的值都大于 $b_…

呃呃呃呃。 # Day ０ 我干了啥来着？ # Day １ 早上吃了点东西。比较神秘的进了场。 看了下题。发现 T4 是 DS。30 min 过了前两题之后思考了一下 T4 发现不会 /jk。跑路做了一年 T3，从 $k=1 \to k=2 \to k\le 8 \to k<n$ 写了不知道多久。写完之后感觉 T4 一…

在讨论《请求添加题解（不同做法）》回复：

我可以 at 谁呢/yun

题解区大部分做法都维护了二次前缀和，并且推了若干个式子，但是我的做法是不需要的。 [我的题解](https://www.luogu.com.cn/article/raiy3tpz)

在讨论《APIO/THU/PKU SC 2024 游记集合贴》回复：

https://www.luogu.com.cn/article/ujobpcts/edit

在讨论《建议撤下第一篇题解》回复：

题解我已经修改后重新提交了。

在讨论《建议撤下第一篇题解》回复：

在代码预处理部分 ```cpp for(int i = 1;i<len;i++)a[++n]=-a[n-len+1],p[n]=a[n]; ``` 这样处理是会UB的。 现在把代码调整成 ```cpp for(int i = 1;i<len;i++)++n,a[n]=-a[n-len+1],p[n]=a[n]; ```…

在讨论《建议撤下第一篇题解》回复：

感谢hack，已经找到问题了

现在有 $m$ 个操作，第 $i$ 个操作有参数 $l_i,r_i(l_i\le r_i)$，执行该操作会把 $a_{l_i+1\cdots r_i} $赋值为 “$a_l$”。 应为 $a_{l_i}$。

输入的第一行包含两个正整数 $n,q$，表示**子**符串长度和询问次数。

在讨论《NOI 2023 游记集合贴》回复：

[https://www.luogu.com.cn/blog/11454s1/noi2023-da-tie-ji](https://www.luogu.com.cn/blog/11454s1/noi2023-da-tie-ji)

在讨论《警示后人》回复：

orz

在讨论《关于最小花费的疑问》回复：

orz

在讨论《WA on #29 求调》回复：

警示后人：（虽然大家不会和我一样蠢） 不要像我一样把两个前缀优化点混建。

```cpp #include using namespace std; const int N=2e5+5; int n,m,head[N must[N]; struct edge{ int nxt,to; }e[N*20]; inline void add(int a,int b){ e[++tot]={head[…

在讨论《缩点+dij最短路，29ptsWA求助，真没找到错哪QAQ》回复：

orz tarjan巨神