2022-12-27 #20 再一次 向星光闪烁的天空 倔强伸出双手

文明已经打的不记得多少小时了。。。

【洛天依原创曲】仍与你心跳同步。

我听见了你的歌声 我听见了我的心声
在遥远屏幕那边 但梦境却紧密地相连
我听见了你的歌声 这一刻我们心跳重叠
你在温暖的旋律中浮现 我们相见

前两天一共做了三道题，是不是很厉害！

100 CF1423M Milutin's Plums

100 了！（进度好慢啊）

SMAWK 算法：

核心为 reduce 过程，将一个 \(n\times m\) 矩阵压缩成 \(n\times\min(n,m)\)，保留最小值出现的关键列。（不妨称非最小值位置为冗余位置，没有最小值出现的列为冗余列）

维护指针 \(k\)，初始为 \(1\)，每次比较 \(a_{k,k}\) 与 \(a_{k,k+1}\)。（注意，我们维护的过程会保持 \([1,k]\times[1,k]\) 的子矩形对角线严格以上的位置为冗余位置）

• 若 \(a_{k,k}\geqslant a_{k,k+1}\)，删除第 \(k\) 列。
• 否则：
  • 若 \(k=n\)，则删除第 \(n+1\) 列；
  • 否则令 \(k\leftarrow k+1\)。

而 SMAWK 算法即取出矩阵所有偶数行，reduce 后递归下去，然后把奇数行类似决策单调性分治，暴力扫描即可。

啊啊啊啊，不太会分析这个常数。

复杂度 \(O(n+m(1+\max(0,\log\frac nm)))\)。

101 P8492 [IOI2022] 无线电信号塔

若 \(D\) 固定，我们可以考察一座塔 \(i\) 左右第一个合法的中转点，假设为 \(l_i,r_i\)，那么任意两个区间要么包含要么不交。

可以发现我们选择的区间一定需要两两不交，我们只用把包含其他区间的区间删掉就好了。于是区间询问只需将询问内部的区间数量加上左右两边能不能多选一个。

考察左边能选的条件，我们取出最左边的区间 \([l,i,r]\)，假设询问区间为 \([ql,qr]\)，考察 \([ql,i]\) 最大值的位置 \(p\)，可以证明新选的位置一定在 \(p\) 左边，直接判断就好了。（否则这个位置会形成一个在询问区间里的合法区间）

若 \(D\) 不固定，我们从大到小扫描 \(D\)：

我们发现两个区间一旦包含，之后所有 \(D\) 都会包含。而如果 \([l,i,r]\) 中 \(i\) 不为最小值，那么其一定包含一个区间。

于是我们只需用单调栈找到 \(O(n)\) 个区间，然后计算出这个区间应该在 \(D\) 不超过某个数是加入就好了。

复杂度 \(O((n+m)\log n)\)。

102 P8495 [IOI2022] 千岛

都会做？？？我不会。

如果某个点无法到达环，我们是不会到达这种点的，将这些点都删掉。

如果起点出度为 \(1\)，我们就把起点改成其到达的点。否则，我们通过构造说明一定有解。

任取两个起点 \(u\) 能到达的点 \(v_1,v_2\)，若 \(v_1,v_2\) 能到达同一个未删去的点 \(x\)，我们可以：\(u\rightarrow v_1\rightarrow \cdots\rightarrow x\rightarrow\cdots\rightarrow x\rightarrow v_1\rightarrow u\rightarrow v_2\rightarrow\cdots\rightarrow x\rightarrow\cdots\rightarrow x\rightarrow v_2\rightarrow u\)。

否则两个点能到两个不交的环，容易构造。

复杂度线性。

vp：CF1667。

不会 D！

103 CF1667D Edge Elimination

未补。

看了一眼 SHCSP-S2022 的题，跟出题人胡了一下，做法应该都是对的！

orz Kubic。

T1：不知道咋回事，这种题没秒掉。

一开始想枚举用多少时间做题，但这个背包复杂度承受不起。

将这个背包“转置”，记录拿了多少分，最小化用的时间就可以了。

T2：矩阵快速幂板板。

T3：真不会这种题，随便猜了个结论，结果是对的？

答案是“左上-右下”的点对的最远距离的一半，线段树维护即可，复杂度 \(O(n\log n)\)。

104 SHCSP-S2022 T4 集合

一开始想了个 \(O((n+m)\log^2 n)\) 的做法，后来发现想复杂了，是 \(O(n\log^2 n+m\log n)\) 的。

对值域分治，取出所有经过中点的线段，它们的交一定是一条过中点的线段，而且很容易用主席树维护。

我原本的想法是记录“左边被上层节点覆盖了多长”，然后递归下去，这样一次询问是 \(O(\log^2 n)\) 的。

事实上不需要递归下去，因为询问一旦被劈开，一个端点会始终为递归区间的端点，那么对线段的限制变成了一维的，我们按照那一维排序依次加入，维护一棵主席树就好了。（感觉说的有些混乱，但这一部分只要意识到了都是很简单的）

std 做法：

直接扫描线，将线段按照右端点顺序依次加入。

对于一个位置，它的贡献是一段前缀，（当 \(l\) 小于等于某个值时造成贡献）但注意其并不是单调的。

加入一条线段 \([l,r]\)，相当于这条线段上所有位置对 \(l\) chkmax，可以用 segbeats 维护这一过程，只有 \(O(n\log n)\) 次修改。用一棵树状数组维护答案，每次 segbeats 修改的同时维护一下树状数组就好了。

复杂度一样的。

105 P8596 「KDOI-02」一个截的拦

这个代价，明显就是按位或最小生成树。

按位贪心，

还不会

106 Ptz2022 Day7 HSE Koresha Contest K Decoding The Message