「JOI」 JOI 板刷记录

但愿我的故事不会是潦草地结尾。

虽然是板刷，但是跳过了一些不可做题。

JOISC 2022

Day 1

LOJ 3685 「刑務所 / Jail」

两条限制，对于一条移动路径 $S,T$，有

若 $S$ 在其他路径上，则必须比其他路径先走
若 $T$ 在其他路径上，则必须比其他路径后走

需要树剖加线段树优化建图，两个 $\log$，但是常数超级小。现在是 10:03，我看看我啥时候能写完。
现在是 12:12，我过了。

submission

LOJ 3686 「京都観光 / Sightseeing in Kyoto」

好题，先写一个很 naive 的转移式子

$$\begin{array}{}\text{(1)}& \begin{array}{r}d{p}_{x,y}=d{p}_{i,j}+min\{(x-i)\cdot b_j+(y-j)\cdot a_x,(x-i)\cdot b_y+(y-j)\cdot a_i\}\end{array}\end{array}$$

那么假设有不等关系

$$\begin{array}{}\text{(2)}& \begin{array}{rl}(x-i)\cdot b_j+(y-j)\cdot a_x& <(x-i)\cdot b_y+(y-j)\cdot a_i\\ \Rightarrow (x-i)(b_j-b_y)& <(y-j)(a_i-a_x)\\ \Rightarrow \frac{(x-i)}{(y-j)}& <\frac{(a_i-a_x)}{(b_j-b_y)}\end{array}\end{array}$$

稍微调整一下有

$$\begin{array}{}\text{(3)}& \begin{array}{r}\frac{(x-i)}{(a_x-a_i)}<\frac{(y-j)}{(b_y-b_j)}\end{array}\end{array}$$

那么整个过程可以看成在对这样的转移进行选择，每次选择一边往下走，更形象一点，转移在两个互不影响的凸包上进行，每次向斜率更小的一边移动，于是此题首先处理两个凸包，然后双指针移动即可。

submission

LOJ 3687 「スペルミス / Misspelling」

怎么这题目名一个字都不认识😂
假设我只有一条限制怎么做，即是说删去 $S_a$ 之后的字符串字典序小于删去 $S_b$ 之后的字典序。
首先规定 $a<b$，因为 $a>b$ 的情况只需要改一下符号。
首先砍掉 $S[1\dots a-1]$ 和 $S[b+1\dots n]$，这两部分在修改后的字符串中完全一致，不用考虑，于是现在的限制转化成 $S[a+1\dots b]\le S[a\dots b-1]$，考虑逐位比较，当前考虑到 $pos$，如果 $S_{pos}=S_{pos+1}$，那么上述限制需要靠后面的几位实现，否则取 $S_{pos}<S_{pos+1}$，那么上述限制可以直接被满足，后面的几位可随便选择。
于是记一个字符串 $c$，表示连接 $S_i$ 和 $S_{i+1}$ 的符号，于是限制就成了描述该区间里面出现的第一个非等号的符号是啥。
加入多个限制，优先考虑右端点较大的。

这个状态其实并不好想，首先完善一下上面的讨论，若有限制 $(i,j)$，在 $i>j$ 时表示区间 $[i,j)$ 中的第一个不等号是 $>$，否则表示 $(i,j]$ 中的第一个不等号是 $<$。
定义 $d{p}_{i,j}$ 表示前 $i$ 个字符满足了所有 $(l,r),i\in [l,r]$ 的限制，并且以 $j$ 结尾的方案数，转移用前缀和优化。
最终复杂度是 $\mathrm{\Theta }(26n+m\log m)$。

submission

Day 2

LOJ 3688 「コピー & ペースト 3 / Copy and Paste 3」

从基础的想法入手，定义 $d{p}_{l,r}$ 表示打印出 $[l,r]$ 中的字符需要花费的最小代价，首先考虑 $A$ 操作，转移很简单，直接往后面添加即可，即是 $d{p}_{l,r}=d{p}_{l,r-1}+A$。
现在需要加入 $B,C$ 操作，可以想象出来最后序列的某部分的最优构造长这个样子

$$\begin{array}{}\text{(4)}& \begin{array}{r}S{x}_{1}S{x}_{2}S{x}_{3}A\dots x_{n}S\end{array}\end{array}$$

其中 $x_i$ 是通过 $A$ 操作塞进去的字符，而 $S$ 是相同的可以剪切的部分。

所以转移为枚举 $k$，在 $S[l,r]$ 中贪心地去删掉最多的不重复的 $S[l,k]$。
但是这样状态较多，于是增加一个转移 $d{p}_{l,r}=d{p}_{l+1,r}+A$，这样不用去枚举 $k$，能转移当且仅当 $S[l,k]$ 是 $S[l,r]$ 的 boarder。
于是现在的问题是求 $[l,r]$ 中最多能删去多少个不重复的 $S[l,k]$，这样可以倍增求，复杂度为 $\mathrm{\Theta }(n^2\log n)$。
似乎上面那个做法有点小麻烦了，因为 $[l,k]$ 的枚举量是调和级数级别的，可以暴力冲。

submission

LOJ 3690 「チーム戦 / Team Contest」

为啥直接是 3690 呢，因为中间的 t2 是道通信题。
这道题感觉很 ez，反过来想，我肯定希望每种能力都选出来最大的然后加起来，如果不行，这就意味着某人至少占了其中两项的最大值，发现这个人一定不可能存在于答案之中所以直接删掉即可。重复这个过程到有解位置。

submission

Day 3

LOJ 3692 「スプリンクラー / Sprinkler」

注意到 $D\le 40$，所以有啥用呢？
感觉难以用数据结构维护，于是我开始写点分治，写到一半觉得这个 $D\le 40$ 应该很有挖掘的地方，于是去看了题解，确实很妙。
记 $ta{g}_{i,d}$ 表示以 $i$ 为根的子树内与 $i$ 深度差为 $d$ 的点需要加上的权值，于是问题是如何不重不漏地去覆盖目标节点，在从当前节点往父亲节点上爬的过程中，记往上已经走了 $k$ 的距离，于是在 $ta{g}_{f{a}^k(u),d-k}$ 处和 $ta{g}_{f{a}^{k}u,d-k-1}$ 处打标记就好了，正确性很显然，这样做规避距离奇偶性的问题。
所以用一个复杂度为 $\mathrm{\Theta }(nd)$ 代码超短的做法完成了本题，可以作为模板记一下。

submission

LOJ 3693 「蟻と角砂糖 / Ants and Sugar」

果然我二分图学得很烂啊。。。就当重学了，我来非常详细地写一下这道题怎么做。首先重新写一下扩展霍尔定理，因为之前我真的不怎么会用。

扩展霍尔定理

对于二分图 $G=(Vl,Vr,E)$，记邻域 $N(S)=y|\mathrm{\exists }x\in S,(x,y)\in E$，用大白话来讲，邻域就是直接于给定点集中的点相连的点构成的集合。
结论是 $G$ 的最大匹配为 $|V|-max|S|+|N(S)|(S\subseteq Vl)$。这个式子看起来很抽象，简单来说，一张二分图的最大匹配为左部点点数减去最大的左部点子集超过该子集的邻域的部分，更好理解一点，枚举左部点的所有子集，若此时的子集大于了它的邻域，就会有一部分($|S|-|N(S)|$)，匹配不了，减去最多不能被匹配的部分，剩下的是最大匹配。很明显这个是上界，但是能取到。
证明可以直接结合 hall 定理。

比较明显地看得出来这道题是最大匹配，然后看了一眼，裸的二分图匹配可以获得 $6pts$ 的好成绩。

然后我其实写了一遍题解了，但是写这一遍时我自己都完全没搞懂，所以现在我重新写一下我的理解，下面是个人认为写清楚了的版本。

然后考虑将这个问题转化一下，变成最大独立集问题，意味着选择的相邻的红、蓝点之间的距离应该大于 $L$，于是先选出所有红点，然后排除不能选的蓝点，剩下的是独立集。于是有两个重要的观察。

• 每个位置上的点要么都选，要么都不选，因为选了全部一定比只选部分更优，所以只用对位置考虑。
• 选择的相邻的两个红点之间的距离应该大于 $2L$，如果小于等于了 $2L$，那么可以将中间所有的红点都选上，因为不可选的蓝点的集合没变，而能选的红点变多了，所以这样更优秀。

于是这个问题被划分成了很多个独立的段，每个段以红点开头，以红点结尾，记为 $[l,r]$，计算这一段的贡献，记每个位置上红/蓝点个数为 $R_i,B_i$。
先选出所有红点，为

$$\begin{array}{}\text{(5)}& \begin{array}{r}\sum _{i=l}^r{R}_i\end{array}\end{array}$$

去掉 $R_i$ 邻域上的蓝点，为

$$\begin{array}{}\text{(6)}& \begin{array}{r}\sum _{i=l-L}^{r+L}{B}_i\end{array}\end{array}$$

这个是以区间和的形式出现的，所以拆一下前缀，并整理得到

$$\begin{array}{}\text{(7)}& \begin{array}{rl}& (\sum _{i=0}^r{R}_i-\sum _{i=0}^{l-1}{R}_i)-(\sum _{i=0}^{r+L}{B}_i-\sum _{i=0}^{l-L-1}{B}_i)\\ =& (\sum _{i=0}^r{R}_i-\sum _{i=0}^{r+L}{B}_i)+(\sum _{i=0}^{l-L-1}{B}_i-\sum _{i=0}^{l-1}{R}_i)\end{array}\end{array}$$

这个形式很优美，因为只用左右端点的信息就可以刻画整个贡献，分别可以记为 $f_r,g_l$。问题就变成了交替选择 $f_r,g_l$ 使得总和最大，这个是个经典问题，可以 ddp 解决，记录每个区间开头与结尾的类型就行。于是来解决带修改的版本。

• 加入 $R_i$

  • 对于 $j\ge i,f_j:=f_j+x$
  • 对于 $j\ge i+1,g_i:=g_i+x$

• 加入 $B_i$

  • 对于 $j\ge i+L,f_j:=f_j-x$
  • 对于 $j\ge i-L-1,g_j:=g_j-x$

发现形式不太好，拆一下操作

• 加入 $R_i$

  • 对于 $j\ge i+1,f_j:=f_j+x,g_j:=g_j+x$
  • 对于 $j\in [i,i+1),f_j:=f_j+x$

• 加入 $B_i$

  • 对于 $j\ge i+L,f_j:=f_j-x,g_j:=g_j-x$
  • 对于 $j\in [i-L-1,i+L),g_j:=g_j-x$

第一个操作变得非常好做，第二个操作有个区间修改，但是注意到一件事 $j\in [i-L-1,i+L)$，这个区间长度小于等于 $2L$，说明了这个区间里面只有一个 $g_j$，于是也就是一个单点修改。

然后怎么区间修改呢？如果当前区间选择的 $R$ 和 $B$ 的数目相同，那么整个区间的答案是不变的，并且注意到 $R$，$B$ 在交替出现，所以这两者的个数差在 $[0,1]$ 中，如何判断呢，其实之前 ddp 里面记录的 $0/1$ 状态已经指明了个数差。

更具体地给出状态表示 $(l,r)$ 二元组表示当前的状态以 $l\in [0,1]$ 开头，$r\in [0,1]$ 结尾。而对于上面讨论的是否存在一个选中的点位于修改的 $[i-L-1,i+L)$ 中，可以对所有的长度小于等于 $2L$ 的区间记录其中存在的 $g_l$ 的个数。

其实麻烦了，有没有种可能呢，就是说拆开维护的常数其实不大，并且非常好写，写法是用第二种情况去包含第一种情况。

submission

Day 4

LOJ 3695 「魚 2 / Fish 2」

但是我根本想不到这个合并区间的方式，原因在于我的思考方式里面没有对鱼的行为定向，而是采取了贪心的策略对每一条鱼考虑，这样导致每一条鱼都是割裂开的，没有办法做到正确的时间复杂度。
问了半天 duanyu 终于搞懂了怎么做，这题的网上题解真的写得丑陋。

首先观察一下不能继续吃的条件是啥，对于 $[l,r]$ 一个小区间，里面的鱼互相吃完之后不能再移动当且仅当 $a[l\dots r]<min\{a_{l-1},a_{r+1}\}$。
记一条鱼 $i$ 能够吃掉的极大区间为 $[l_i,r_i]$，发现在询问区间 $[L,R]$ 固定的时候，不同的 $[l_i,r_i]$ 的个数是 $\log V$ 级别的，因为当 $i$ 的扩展被挡住时，一定会出现一条和 $i$ 目前体积相当或更大的鱼，鱼的体积每次都在翻倍。
于是把生成了相同 $[l,r]$ 的鱼看作一个等价类。
先考虑全局问题，答案就是等价类 $[1,n]$ 的大小。对于局部询问，这个等价类的信息如何合并呢？
考虑合并两个相邻的区间 $[l,mid]$ 和 $[mid+1,r]$，能成为 $[l,r]$ 这个区间答案的等价类一定满足其中一个端点落在了 $mid$ 或者 $mid+1$ 上。很显然，如果一个等价类连两个子区间都无法跨过，那肯定吃不完整个大的区间，而有端点落在了 $mid,mid+1$ 的等价类有可能跨过所在的子区间，然后吃了相邻区间后折回来吃之前剩下的，于是对于一个子区间只需要保留为其前、后缀的等价类的信息即可。
更具体地合并方式，枚举左边的后缀，暴力右左横跳，能往右走就往右走，不能往右走了就折回头往左走，走到走不动位为止，如果生成的新的等价类有一端在合并过后的左、右端点上，则把它扔进合并后区间的前后缀集合里面，顺便维护等价类大小即可，整个过程可以双指针维护。

submission

LOJ 3696 「復興事業 / Reconstruction Project」

先转换成最小生成树问题，每条边的边权是 $|w_i-x|$，其中 $x$ 是每次给定的参数。
直接 kruskal 瓶颈在于排序与并查集。
本质是查询一堆一次函数边权的最小生成树在 $x$ 处的点值，显然可以从一次函数的性质入手每条边存在于最小生成树上的时间是一个区间，于是求出这样的时间段就行了，考虑沿着时间轴计算，当时间很小的时候（比如 $0$），每条边的边权就是初始值，直接求最小生成树即可，随着时间的推移，会有新的更小的边加入这棵树，必然会形成环，考虑环上的替换即可，这样看起来很容易，其实有问题，因为新加入的边是不可知的，所以换一下，按边权的大小从小往大加边，具体地有对于 $x,y$ 两条边，当前 $x$ 在生成树上，$y$ 能够第一次替换 $x$ 的时间是 $\frac{x+y}{2}$，但是可能会出现的问题是，这样出现的替换时间并没有序，但是没有任何影响。因为我们只需要保证每条边都被最早能替换它的边替换掉即可。
所以最终的做法很简单，每次找两点间最大权值的边，然后对询问的区间加一次函数。

submission

JOISC 2023

Day 1

LOJ 3966 「ふたつの通貨 / Two Currencies」

是个签到题，只要考虑当前点到 $1$ 上的路径即可，求解可以贪心，尽量多地用 Ag 去填小的收费站的坑，剩下的用 Au。于是得到了主席树上二分的做法。但是我写了很久，因为没有把题读清楚，注意一下每条边上可能有多个收费站。

submission

LOJ 3967 「JOI 国のお祭り事情 2 / Festivals in JOI Kingdom 2」

确实很难了。但是最近也做了比较多的这样的题，算是有了一个较好的理解。第一步是弄清楚他给的错误解法和正确解法分别是啥。

• 错误的贪心

  按左端点排序，与当前所有区间的并集没有交则直接取。

• 正确的贪心

  按右端点排序，与当前所有区间的并集没有交则直接取。

姑且这种对很多区间进行 dp 的方式称之为接口 dp，因为具体思想是把区间拆开，然后用右端点去接上空着的左端点。于是把左端点称之为接口，从左往右扫，记录当前在错误解法中没有封口的接口个数，然后还要记录在正确解法中没有封口的接口个数。写一个很大的 dp，记 $d{p}_{i,j,k,0/1/2}$ 表示前 $i$ 个位置，假设用正解求出来的最后一个区间结束的位置为 $pos$，$pos$ 前有 $j$ 个接口开始并且在目前位置没有结束，$pos$ 后有 $k$ 个接口开始并且在目前位置没有结束，发现这 $j$ 个接口都是不会出现正确解法中。

• $0$ 表示假做法没有少 $1$，且目前没有可用的接口。
• $1$ 表示假做法少 $1$，此时有可用的接口。
• $2$ 表示假做法少没有 $1$，目前有可用接口。

LOJ 3968 「パスポート / Passport」

直观感受往往能带来较强的性质，注意到每一次的操作是将包含当前点的一个集合扩大，于是出发点能够到达的位置都是连续的，改写所求问题，求到达所有点改为，到达 $1$ 和 $n$ 两个点。
发现这个不能拆开做，原因显而易见，继续直观感受，最优方案长成啥样呢，首先走到达到某个区间 $[l,r]$ 之前这两条路都是相同的，之后分开求解。
更好地转化一下，从 $1,n$ 出发往中间走到某个区间 $[l,r]$ 合到了一起。
所以现在的解法为，首先分别从 $1,n$ 出发做最短路，求到达某个相同的点时的步数，分别记为 $di{s}_1(i),di{s}_n(i)$，现在对于 $i$ 的答案上界为 $di{s}_1(i)+di{s}_n(i)$，问题在于怎么把前面部分的相同路径减去。
到这里我就不会了。
注意到一件事情对于 $(u,v)$，总会有 $di{s}_v\le di{s}_u+1$，所以如果发现了 $di{s}_v>di{s}_u+1$，那就重新松弛，具体过程再用一次 0/1 bfs 实现。

submission

Day 2

LOJ 3970 「議会 / Council」

从贡献入手，有一些议案是在去掉某一人的票之后会无法通过的，首先固定主席，去掉他的贡献，发现有可能挂掉的议案是票数等于 $\lfloor \frac{n}{2}\rfloor$，令其构成的集合为 $s$，令每一个议员构成的集合为 $t_i$，那么 $i$ 当选副主席造成的贡献为 $s\mathrm{\&}{t}_i$ 中 $1$ 的个数。
所以，对于每一个 $t_i$，都用前缀和得到子集，找一个最大的子集有值的 popcount 即可。

submission

Day 3

LOJ 3972 「ビーバーの合唱 / Chorus」

简化后的题意大概是，将一个只包含 $\mathtt{A}\mathtt{/}\mathtt{B}$ 的字符串划分成 $k$ 个不相交的子序列，满足每个子序列不为空，且子序列中的 $\mathtt{A}$ 都在 $\mathtt{B}$ 的左边，两者相等。
需要先弄清楚对于一个固定的序列怎么去算它最大能分成几个合法的子序列。贪心地去想，若能分出来形如 $\mathtt{AAABBB}$ 这样的子序列，可以再继续划分变成三个 $\mathtt{AB}$，于是发现划分成 $k$ 个必须满足能划分成小于等于 $k$ 个。

有一个简单的观察是一首歌是由连续的 $\mathtt{AB}$ 来完成的，于是划分 $k$ 段就行了，每一段保证其中的 $\mathtt{A}\mathtt{/}\mathtt{B}$ 的数量相等。
定义 $d{p}_{i,j}$ 表示算到第 $i$ 个 $\mathtt{A}$，总共划分了 $j$ 段的代价，记 $cn{t}_i$ 表示 $i$ 之前的 $\mathtt{B}$ 的数量，有转移。

$$\begin{array}{}\text{(8)}& \begin{array}{r}d{p}_{i,j}=\underset{k=0}{\overset{i-1}{min}}d{p}_{k,j-1}+(\sum _{l=k+1}^{i}max(cn{t}_l-k,0))\end{array}\end{array}$$

然后是分讨斜率优化。

LOJ 3974 「旅行 / Tourism」

如果它想搞多组询问，完全可以每次重新给一个可以生成的排列，但是非得在开给出，每次询问某一个连续段，意思是让我写莫队？对于这种包含了所有关键点的连通块，有几种理解。

树上连通块大小为边数与连通块个数之和
首先固定根，连通块为所有点到根的链的并扣去所有点的 lca 到根的链

考虑与边数之间的关系，边数是容易求的，即是

将所有关键点按 dfn 排序，让 $1$ 和 $n$ 相邻，则总边数为每相邻两个点之间的距离和。

然后可以得到一个 $\mathrm{\Theta }(n\sqrt{n}\log n)$ 的做法，考虑如何把 $\log n$ 去掉，发现在只删的情况下用链表可以去维护前驱和后继，于是直接回滚莫队。
要注意序列上只加或者只删时的性质。

submission

但是这份代码有必要写注释，因为我写起来真的挺困难的。

「JOISC 2023 Day3」旅行

struct node { int pre, nxt, ind; };
inline void solve() {
  int n, m, q, t; std::cin >> n >> m >> q, t = log2(n);
  std::vector<std::vector<int>> g(n + 5);
  auto addedge = [&](const int& u, const int& v) { g[u].push_back(v), g[v].push_back(u); };
  for (int i = 1, u, v; i < n; i++) std::cin >> u >> v, addedge(u, v);

  /* 预处理 dfn 序，redfn 序，dep，st[][0] */
  int dfn_cnt = 0;
  std::vector<int> dfn(n + 5), dep(n + 5), redfn(n + 5), lg(n + 5);
  std::vector<std::vector<int>> st((n << 1) + 5, std::vector<int>(t + 5));
  auto dfs = [&](auto self, const int& u, const int& fath) -> void {
    dep[u] = dep[fath] + 1, redfn[dfn[u] = ++dfn_cnt] = u, st[dfn_cnt][0] = fath;
    for (int v : g[u]) if (v != fath) self(self, v, u);
  };
  dfs(dfs, 1, 0);

  auto _min = [&](const int& x, const int& y) { return dep[x] < dep[y] ? x : y; };
  auto init = [&]() {
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; j <= t; j++)
      for (int i = 1; i <= n; i++)
        st[i][j] = _min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  };
  auto lca = [&](int l, int r, int k = 0) {
    if (l == r) return redfn[l];
    if (l > r) std::swap(l, r);
    l++, k = lg[r - l + 1];
    return _min(st[l][k], st[r - (1 << k) + 1][k]);
  };
  init();
  auto dis = [&](const int& u, const int& v) {
    return dep[redfn[u]] + dep[redfn[v]] - 2 * dep[lca(u, v)];
  };
  /* 预处理结束 */

  /* 处理询问顺序 */
  std::vector<int> a(m + 5);
  for (int i = 1; i <= m; i++) std::cin >> a[i];

  int siz = std::sqrt(m);
  std::vector<int> bl(m + 5);
  std::vector<node> que(q);
  for (int i = 0; i < q; i++) std::cin >> que[i].pre >> que[i].nxt, que[i].ind = i;
  for (int i = 1; i <= m; i++) bl[i] = (i - 1) / siz + 1;

  std::sort(all(que), [&](const node& x, const node& y) {
    if (bl[x.pre] == bl[y.pre]) return x.nxt > y.nxt;
    else return x.pre < y.pre;
  });
  /* 处理询问顺序结束 */

  /* 回滚莫队 */

  /*
    cnt 每个数在序列中出现的次数
    pre/nxt 链表
    stk 存回滚操作的栈
  */
  int l = 1, r = 0, res = 0;
  std::vector<int> cnt(n + 5), pre(n + 5), nxt(n + 5), ans(q + 5);
  std::vector<node> stk;

  /*
    opt = true 表示此次操作后续需要回滚，会扔进栈里面
    opt = false 表示此次操作是右端点在往回收，有单调性，不回滚
  */
  auto del = [&](const int pos, const bool opt) {
    if (opt) stk.push_back(node{ pre[pos], nxt[pos], pos });
    if (!--cnt[pos]) {
      /* 删中间加两边 */
      res += dis(pre[pos], nxt[pos]) - dis(pre[pos], pos) - dis(pos, nxt[pos]);
      pre[nxt[pos]] = pre[pos], nxt[pre[pos]] = nxt[pos];
    }
  };

  for (int i = 0; i < q; i++) {
    if (!i || bl[que[i].pre] != bl[que[i - 1].pre]) {
      /* 新块 重新计算一次贡献，贡献的区间为当前块的左端点到末尾 */
      cnt.assign(n + 1, 0);
      int pos = (bl[que[i].pre] - 1) * siz + 1;
      for (int j = pos; j <= m; j++) cnt[dfn[a[j]]]++;
      /* 链表 */
      int lst = 0;
      for (int j = 1; j <= n; j++) {
        pre[j] = lst;
        if (cnt[j]) lst = j;
      }
      for (int j = 1; j <= n; j++) if (!pre[j]) pre[j] = lst;
      lst = 0;
      for (int j = n; j >= 1; j--) {
        nxt[j] = lst;
        if (cnt[j]) lst = j;
      }
      for (int j = n; j >= 1; j--) if (!nxt[j]) nxt[j] = lst;
      res = 0;
      for (int j = 1; j <= n; j++) if (cnt[j]) res += dis(pre[j], j);
      r = m;
      /* 此时答案区间的 l = (bl[que[i].pre] - 1) * siz + 1，r = m */
    }

    l = (bl[que[i].pre] - 1) * siz + 1;
    while (r > que[i].nxt) del(dfn[a[r--]], false); // 保持单调往回收，不用回滚
    int rec = res;
    while (l < que[i].pre) del(dfn[a[l++]], true); // 左端点在块内跳，需要回滚
    ans[que[i].ind] = res / 2 + 1;
    res = rec;
    while (!stk.empty()) { // 回滚，依次弹栈即可
      node u = stk.back(); stk.pop_back();
      if (!cnt[u.ind]) nxt[u.pre] = u.ind, pre[u.nxt] = u.ind;
      cnt[u.ind]++;
    }
  }
  for (int i = 0; i < q; i++) std::cout << ans[i] << "\n";
}

LOJ 3977 「ビ太郎の旅 / Bitaro’s Travel」

能直接预处理所有答案吗？
首先研究答案之间有没有啥关系，手玩发现不太行，于是提示是预处理每个点的答案的复杂度应该不怎么大。
数据范围是 $2e5$，大概是两个 $\log$ 的。
关键方法仍然是重新描述题目，检查刻画题目信息的要素，显然去刻画这条路径，要素是：起点，方向，拐点。因为可以用拐点的相对位置刻画方向，所以把方向省略掉。
于是该路径就表示为 $(s,\{t\})$，$\{t\}$ 是包含所有拐点的有序集。
考察如何生成 $\{t\}$，先讨论 $x_{pos}$ 出现时调转方向往左走，当一个拐点 $x_{pos}$ 生成，只可能是 $x_{pos+1}-x_{pos}>x_{pos}-x_{l-1}$，其中 $l$ 是在 $pos$ 出现之前有序集中最小的下标编号，整理一下这个式子 $x_{pos+1}+x_{l-1}>2x_{pos}$。所以 $x_{pos}$ 出现之后会意味着拐点之间的距离至少翻倍，向右调转方向是一个道理。拿到翻倍这个性质，得到 $\{t\}$ 的大小是 $\log V$ 级别的。
现在的目标是直接处理出来这个集合，首先在起点处判断一下第一步的方向，从直观感受或是上面的式子都很容易看到在过程中维护最左和最右的拐点即可，于是这一步的二分查找就很容易了。

JOISC 2020

Day 1

LOJ 3271 「ビルの飾り付け 4 / Building 4」

想一下，有什么固定的方法能很确定地找出一组解？首先写个暴力状态 $d{p}_{i,j,0/1}$ 表示 $A$ 选了 $i$ 个，$B$ 选了 $j$ 个，最后一个选的是 $A/B$ 是否可行。

然后如果是赛时估计会先写这个暴力，或者是直接信仰 $\mathrm{\Theta }(\frac{n^2}{\omega })$ 创过去。写了暴力可能会发现，当 $i$ 固定时，对应 $dp$ 值为 $1$ 的 $j$ 是一段连续的区间。

其实一开始就在往这方面想，考虑建图，连边为相邻列的 $a,b$ 若满足可转移关系则连。那么最终的合法路径一定是上下各经过了 $n$ 次。
这中间会发现有些列可转移的点是固定的，先把这些地方往外扩展，因为有可能可以直接确定相邻的一部分位置。
写得更具体一点，如果存在 $a_i$ $\le$ $a_{i-1}$, $a_i$ $\le$ $b_{i-1}$ 或者 $a_i$ $\ge$ $a_{i+1}$, $a_i$ $\ge$ $b_{i+1}$，那么 $i$ 这个位置上必须选择 $b_i$。如果当前位置必须选择 $b_i$，并且 $b_{i-1}$ $\ge$ $b_i$ 那么前一位只能选 $a_i$。
剩下的都是上下都能走的转移点，假设处理到当前第 $i$ 列，$a_i$ 和 $b_i$ 都能走。不妨假设 $a_i$ $\le$ $b_i$，则 $a_i$ $\le$ $a_{i+1}$, $a_i$ $\le$ $b_{i+1}$，$b_i$ 至少小于其中一个。有

• $b_i$ $\le$ $a_{i+1}$$b_{i+1}$，仍然是 $i+1,j+1$ 都能选择。
• $b_i$ $\le$ $a_{i+1}$，那么 $b_i$, $b_{i+1}$ 不能同时选择。

于是现在就有某些位置已经确定，某些相邻的位置不能同时选择特定的两个元素。
所以结论正确。

submission

LOJ 3272 「美味しい美味しいハンバーグ / Hamburg Steak」

看了一下表，部分分有点搞笑，打满都只有 21pts，虽然比上一题打满只有 11pts 好点，只能说 JOISC 对水平要求真的挺高的。
注意到 $k\le 4$ 并且矩形有四个边界，想想这里是不是突破口？
很好题目，爱来自 JOI，破防了，搞了 1.5h 啥都没想出来。
然后逆天随机化能过，此处不研究。
先求出 $minR,maxL,maxD,minU$，如果 $minR\ge maxL$ 或是说 $minU\ge minD$，那么这一维相当于是没起作用，直接退化成了一维的情况。
否则，很《容易发现》，$K$ 的分布在于这几个边界值组成的矩形的边界上，这里的确很容易，但是我连把四个边界值搞出来这步都不会。
因为当 $K\le 3$ 时，不能完全把四条边都兼顾上，所以说必须放一个点在角上，这样可以一个点控制两条边，于是直接去爆搜枚举这条边即可，复杂度是 $\mathrm{\Theta }(4^{K}n)$ 的。
当 $K=4$ 时，如果按照上面的方法搜不出来解就一定会说明这 $4$ 个点都在矩形的边上，相当于是四个点在限定的范围内可以移动，可以看成 $4$ 个变量，然后开始对每一个小矩形和这个大矩形的位置关系开始分类讨论。

• 如果这个小矩形完整包含了大矩形的一个边界，那就不用管它，一定可以被覆盖到。
• 如果这个小矩形只和大矩形的某一个边界有交，那就是限定了某个变量的范围。
• 如果这个小矩形和大矩形的两个边界有交，相当于是两个变量范围二选一，这个是个 2-sat 问题。

于是这题做完了，代码逆天，复杂度 $\mathrm{\Theta }(n(4^k+\log n))$。

wdnmd

submission