JOI Final 2021

A - 有趣的家庭菜园 4

考虑原数组的差分数组，满足题目的条件相当于存在一个 \(k\) 使得 \(k\) 前面都是负数，后面都是正数。

枚举这个 \(k\) 算下答案取最小值就行。

B - 雪球

显然一个雪球能卷到的雪是个区间。

考虑对于每个雪球二分出它和相邻的雪球的区间相交的最早的时刻。

可以通过这个算出每个雪球对应的区间。

C - 集体照

一个合法的序列，大概样子是一个把 \(p_i=i\) 的序列划分成若干个区间，然后 \(\text{reverse}\) 每个区间。

考虑根据这个 dp，具体转移可以考虑逆序对个数的变化，容易通过预处理做到 \(O(n^2)\)。

D - 机器人

我的做法好像有点麻烦。

把每条边看做是点跑最短路。

令 \(dis_{i,0/1,0/1}\) 表示到第 \(i\) 条边，且第 \(i\) 条边是否变色的最短路。

直接建边的话边数是 \(O(m^2)\)。

优化大概是考虑当一个点 \(u\) 已经被遍历到后了，后面到这个点的边最多只会更新 \(O(1)\) 个点。

这样复杂度就对了。

E - 地牢 3

考虑一层一层做过去，维护一个关于 \(B_i\) 的单调栈，同时还要维护每个 \(B_i\) 最多还能用几次，每次相当于加入一个 \(B_i\) 然后次数是 \(U\)，再所有单调栈里的次数减去 \(A_i\)，具体贡献是取栈头那个位置的 \(B_i\),如果栈头高度为 \(0\) 了就弹掉。

再深入分析一下这个过程，我们考虑对每个 \(B_i\) 计算出他对答案的贡献系数。

首先对于一个位置 \(i\)，它的贡献的就是它被后面加入的弹出前能贡献的次数再减去它入栈的时候前一个位置的能贡献的次数。

我们设它前面最后一个比它小的数和它的距离为 \(x\)，它后面最后一个比它小的数和它的距离为 \(y\)，那么它对答案的贡献就是 \(B_i\times \max(0,\min(y,U)-\max(0,U-x))=B_i\times \max(0,\min(y,U)+\min(x,U)-u)\)。

核心代码大概长这样：

再加上 \(l,r\) 我们发现这是一个四维偏序问题。

首先我们注意到外面的 \(\max(0,...)\) 只有当 \(x+y<U\) 的时候才会取到 \(0\)，于是我们可以分别维护 \(x\)，\(y\) 和 \(x+y\)，已经可以用树套树在 \(O(n\log^2n)\) 的复杂度内解决原问题。

但用这个做法做 Sub3 就是二维偏序问题了，那么对于 \(r\ne n+1\) 的询问，我们能否拆成两个 \(r=n+1\) 的询问来达到降维的作用呢？

可以发现对于 \(r\) 往前走最多 \(U\) 能走到的位置中 \(B_i\) 最小的位置 \(t\)，如果我们把 \(r\) 替换成 \(n+1\)，这个时候我们走到 \(t+1\) 时的能量和从 \(t\) 出发到 \(n+1\) 走到 \(t+1\) 时的能量是一样的，这意味着两者之后的决策也会是一样的。而对于 \(l\to r\) 的询问走到 \(t\) 之后的决策一定是在 \(t\) 就把能量补充到能恰好走完剩下的路程，于是我们只要考虑修正 \(B_t\) 的贡献就行，对于前者 \(B_t\) 前的系数是 \(y-(x-u)\)，后者是 \(y\)，而真正的系数应该是 \(z-(x-u)\)，其中 \(z\) 是剩下的路程，于是我们把答案加上 \(B_t\times z\) 即可。

JOI Final 2020

A - 只不过是长的领带

考虑删掉一个后显然 \(A\) 的第 \(k\) 大和 \(B\) 的第 \(k\) 大配是最优的。

前后缀 max 搞一搞就行了。

B - JJOOII 2

预处理每个位置 \(i\) 求出 \(i\) 后第 \(m\) 个 'J'/'O'/'I' 的位置。

枚举第一个 'J'。

C - 集邮比赛 3

考虑 DP。

设 \(f_{i,j,k,0/1}\) 表示 \([i,j]\) 中收集到了 \(k\) 张，人在 \(l/r\) 的最小时间。

直接转移就行。

D - 奥运公交

为了少打几个字，设 \(dis(i,j)\) 表示 \(i\) 到 \(j\) 的最短路。

先搞出 \(1\) 到 \(n\) 的一条最短路和 \(n\) 到 \(1\) 的一条最短路。

枚举改变方向的边 \(i\)，如果不在搞出最短路上，\(dis(1,n)\) 会改成 \(dis(1,V_i)+C_i+dis(U_i,n)\) 和一开始搞出的最短路的长度的 \(\min\)，\(dis(n,1)\) 同理。

如果在搞出的最短路上，就重新算跑一遍最短路，因为 \(dis(1,n)\) 和 \(dis(n,1)\) 最多只有 \(O(n)\) 条边，所以复杂度是对的。

最终复杂度 \(O(nm\log n)\) 或者 \(O(n^3+m)\)

E - 火灾

显然问题可以转化为若干个区间长度为 \(T\) 右端点在区间 \([L,R]\) 内的区间的 \(\max\) 的和。

先对询问进行差分，然后扫描线。

对每个点预处理出左边和右边第一个比它大的数的位置后，可以发现发现一个点有贡献的地方是两个阶梯状的东西，具体一点就是一条斜率为 \(1\) 的线段上方的点，询问则是某一条 \(y=b\) 的直线的前缀和 。

考虑把这个阶梯状的东西的贡献分成两种情况。

一种是整个阶梯状的东西都在左侧，贡献就是一个区间加等差数列，需要资瓷单点询问，可以线段树维护。

一种是处于阶梯状的东西的上方或者下方。

设阶梯状的东西的线段的左下角是 \((i,j)\)，当前询问是 \((k,T)\)。

则贡献是 \(a_i \times \max(0,\min(k-i+1,T-j+1))\) 。

内层的 \(\min\) 可以推下不等式式子，用三个树状数组维护。

外层的 \(\max\) 考虑如果是取前面的 \(0\) 的话后面的 \(\min\) 肯定是取 \(T-j+1\)，这里再可以用两个树状数组维护下，再加回来。

所以总的我用了五个树状数组和一个线段树维护这 jb 东西。

另外一个询问和每个点不知道拆成了多少个东西..

复杂度是 \(O(n \log n)\) 的。

代码可以去 LOJ 上看。