JOI Final 2021 题解
JOI Final 2021 C-E 题的题解
集合写真 / Group Photo
考察符合条件的序列的性质，一定可以被分割成为 \(m\) 个降序连续段：\((r_1\sim l_1);(r_2\sim l_2);(r_3\sim l_3);\cdots;(r_m\sim l_m)\) 其中 \(l_1=1,l_2=r_1+1,r_3=l_2+1,\cdots,r_m=l_{m-1}+1\) 不难证明不满足以上结构的排列都是非法的。
考虑调整次数即前后相对顺序改变的无序对个数，于是就可以 dp 了。
设 \(f_i\) 表示 \(1\sim i\) 调整成若干连续段的最小代价，考虑若最后一段是 \((i\sim j),j\le i\) 那么对于一个 \(j\le k\le i\) 和它产生贡献的有：(1) \(1\sim j-1\) 中位置在它后面的数，(2) \(j\sim k-1\) 中位置在它前面的数，(3) \(k+1\sim i\) 中位置在它后面的数。
- 和 (3) 都可以用树状数组简单处理，考虑将 (2) 转化为找在 \(j\) 后面的 \(k\)，于是用一个树状数组维护 \(1\sim i\) 的位置，对每个 \(k\) 加上位置在它后面的数的个数，这样会算多 \(j\sim k-1\) 中位置在它后面的数，可以在 \(j\) 向左移动时减掉，于是再用一个树状数组维护即可。
时间复杂度 \(\operatorname{O}(n^2\log n)\)。
ロボット / Robot
考虑从 \(u\) 到 \(v\) 的一条颜色为 \(c\) 长度为 \(w\) 的边，设 \(S_{u,c}\) 为以 \(u\) 为端点所有颜色为 \(c\) 的边的长度之和，要经过该边有两种策略：
- 将该边改为一种不冲突的颜色，费用 \(w\)。
- 将所有相同颜色的其他边改掉，费用 \(S_{u,c}-w\)。
发现 \(u\) 是菊花的中心且每条边的颜色两两不同的情况下 1 策略是不合法的，但是此时 2 策略费用为 \(0\) 故可以不考虑。
发现若有 \(u\to v\)，\(v\to x\) 两条边颜色都为 \(c\) 在 \(u\to v\) 选择 1 策略，\(v\to x\) 选择 2 策略那么改变 \(u\to v\) 边的颜色的代价会计算两边，考虑减去。
考虑建立虚点 \(v_c\) 由 \(u\) 向 \(v_c\) 连边权为 \(0\) 的边，\(v_c\) 向 \(x\) 连边权为 \(S_{v,c}-w\) 的边，发现这样 \(u\to v_c\to x\) 就是先 \(1\) 策略再 \(2\) 策略的代价。
于是跑 Dijkstra 即可。
最多每条边都建一个虚点，故点数是 \(\operatorname{O}(n+m)\) 的，边数还是 \(\operatorname{O}(m)\) 的，时间复杂度 \(\operatorname{O}((n+m)\log m)\)。
注意：以下参考代码大量使用 STL 和 C++17 特性，常数巨大且需要注意编译选项。
ダンジョン 3 / Dungeon 3
JOI 总是有很多考思维的数据结构题
首先有显然的贪心：对于一个位置 \(i\) 找到他后面第一个价格小于它的位置 \(j\)，二者距离为 \(L\)，如果 \(L\le U\)，那就将能量填到 \(L\)，否则填满。
考虑 Subtask3 (\(T=N+1\)) 每次找后面小于它的位置可以联想到离线询问然后倒着扫用单调栈维护价格，每次退栈（当前的价格优于之前的价格）就考虑是否能在当前位置买能量，替代后面的，当前要购买的能量是已知的，考虑要删去多少：
设当前位置到栈顶的距离为 \(L\)，到栈顶下一个元素的距离为 \(L^\prime\)，如果 \(L^\prime\le U\) 删去全部 \(L^\prime-L\)，否则 \(L^\prime-U\) 是必须的，只能删去 \(L^\prime-L-(L^\prime-U)=U-L\) 于是即为 \(\min(L^\prime,U)-L\)。
最后栈顶还要加上 \(\min(L,U)\)。
考虑用数据结构维护所有 \(U\) 的值，我们发现我们要加的都是一条折线（一条斜线段在加上一条平行与 \(x\) 轴的线段），我们发现这是可以用树状数组简单维护的，具体来说，设 \(l\) 到 \(r\) 是斜线段，斜率为 \(k\)，截距为 \(b\)，平行段的 \(y\) 为 \(c\)，我们用一个树状数组维护斜率，另一个树状数组维护截距，用差分的思想给 \(l\) 斜率加上 \(k\)，\(r+1\) 斜率减去 \(k\)，\(l\) 截距加上 \(b\)，\(r+1\) 截距加上 \((r+1-l)\times k\)。
然后考虑满分做法：设 \(f(S,T)\) 为 \(S\) 到 \(T\) 的答案，我们找到距离 \(T\) 小于等于 \(U\) 的最小价格处 \(m\) 发现只要经过 \(m\) 就一定会在 \(m\) 处买能量的，于是 \(f(S,T)=f(S,N+1)-f(m,N+1)+dis(m,T)\times b_m\) 不用担心在 \(m\) 之前买的能量没有用完的问题，这笔钱在 \(f(m,N+1)\) 被减去又在后面被加上，但 \(f(S,N+1)\) 中在 \(m\) 前买的能量是一直有贡献的，用 ST 表找一下 \(m\) 即可。
时间复杂度 \(\operatorname{O}(n\log n)\)。