Diary - 2024.12.22

吸取之前教训，今天早点写日记。

看起来我还缺：

• Solution - Luogu P11394 [JOI Open 2019] ウイルス実験
• Solution - Luogu P11398 众数
• Solution - Luogu P11401 [Code+#8 初赛] 普勒亚
• Solution - Luogu P11402 [Code+#8 初赛] 图
• Solution - Luogu P11405 [RMI 2020] 秘鲁 / Peru
• Solution - Luogu P11390 [COCI 2024/2025 #1] 教师 / Učiteljica
• Solution - Luogu P11408 [RMI 2020] 树咖 / Arboras

我去怎么还有这么多，明天一个晚上肯定写不完了，但肯定还是要写的。

感觉，写题解还是得趁热打铁。
不然越后面越没有兴趣写之前的题解。

后面的自己 be like：

欸要不写下这题题解吧。
欸这题有啥意义来着。
（经过自己评判，其实就是摆了）
感觉不写也没事，就不写了吧。

而且从这个 Luogu 题目 id 能够看出来，我现在在神秘从后面开始板刷有难度的题。

但是 Luogu 加题咋这么快阿？？？？？？？？
我记得我当时周五看的时候，这些题还是最后一页，而且最后一页看起来还能放一些题的阿？？？
记得当时发现单周五就加了 16 还是 17 道题来着，太恐怖了。
Luogu 搬题的都不学 oi 了吗？？？哥我觉得你真的可以拿点时间自己卷一卷而不是拿这么多时间拿来造福大家了，，，（仅个人观点）
或者说搬题时间或许不需要很长？我感觉遇到有的抽象题可能还是要废点时间的吧，，，

感觉还不如尝试尝试板刷，吃石或许也不是不能接受的。
毕竟还是不能保证正式比赛出了依托是吧（？）。

“Solution - Luogu P11390 [COCI 2024/2025 #1] 教师 / Učiteljica”为什么被删除了？

Luogu P11390 [COCI 2024/2025 #1] 教师 / Učiteljica。

题解清一色的容斥，爆笑了。

明天写个题解，但我觉得这题是在没意思。

算了就当提供新思路把，

来自 Diary - 2024.12.20。

又经过我仔细想了想，我真的觉得这题没啥意思，所以我不想写了。
（我是不是进入了上面我说的状态？但是这题确实有点唐了。）

那我还是简短写一下吧。

首先直接跳到移动右端点然后扫描线的步骤，毕竟前面应该真的不会有什么不同了。

考虑扫描线的线段树其实有一种写法是：

inline void pushup(int k) {
   cnt[k] = cover[k] ? siz[k] : (cnt[ls] + cnt[rs]);
}

其实这个依然可以套用到这题上。

考虑这个 pushup 的本质是，我们只关注线段树这个节点对应的子树内部的覆盖情况，而不去关系祖先的是否覆盖。
而且在 pushup 时让子树的信息合并上当前结点的信息。

于是可以定义 \(cnt_{k, 0\sim 15}\) 代表只考虑 \(k\) 及其子树内部的 \(0\sim 3\)（其实是出现 \(1\sim 4\) 次，只是我整体 \(-1\) 了一下）的存在情况对应的数量。

对于 pushup，首先可以根据标记永久化得到对于节点 \(k\) 覆盖情况的二进制数 \(z\)。
那么这个时候例如 \(cnt_{ls, x}\)，就合并上 \(z\) 的这个覆盖贡献，也就是 \(cnt_{k, x | z}\leftarrow cnt_{k, x | z} + cnt_{ls, x}\)。
需要特判一下叶子，叶子就是 \(cnt_{k, x} = [x = z]\)。

然后这样子会发现上面给出的正常扫描线的例子其实只是这个的弱化，就是只有 \(0 / 1\) 而已。

这题核心代码：

int c[maxn * 4][4], f[maxn * 4][16], islf[maxn * 4];
inline void pushup(int k) {
   int z = 0;
   for (int i = 0; i < K; i++) z |= (c[k][i] > 0) << i;
   memset(f[k], 0, sizeof(f[k]));
   if (islf[k]) {
      f[k][z] = 1;
   } else {
      for (int i = 0; i < (1 << K); i++) {
         f[k][z | i] += f[k << 1][i] + f[k << 1 | 1][i];
      }
   }
}

好的锐评一下要写题解的题，顺便也能合理让自己写的时候不会忘记怎么写：

• Luogu P11394 [JOI Open 2019] ウイルス実験
  首先可以预处理出来每个方向是否感染时的最长时间段用来 check。
  然后就从开头考虑起，考虑到如果 \(u\) 感染了就能感染 \(v\)，但是 \(v\) 感染了感染不了 \(u\)，那么因为最小化这个 \(u\) 是肯定不会感染的。
  于是实际上可以成许多个连通块，找到关键点，使得从这个关键点能感染到的点实际上都满足能互相感染的关系（不能就可以更小）。
  那么就可以考虑合并连通块，如果连通块关键点 \(u\) 被感染了就可以感染另一个连通块关键点 \(v\)，就把 \(u\) 合并到 \(v\) 上，就是让关键点只有 \(v\)。
  这是因为这个时候不清楚 \(v\) 能不能感染 \(u\)，所以用 \(v\) 一定不亏。
  然后会发现这是个类 boruvka 的过程，每轮下去连通块数至少 /2。
  然后就做完了。

  其实感觉写起来题解又觉得不是很难，但是自己做的时候就没有头绪，怎么回事呢？？？

• Solution - Luogu P11398 众数
  先发现这必然是要求前缀众数的，所以可以考虑分块这类的方法，反正就是把信息数减少。
  然后根号的就比较简单了。
  发现根号对散块处理太不牛了，是 \(q\sqrt{n}\) 的，完全跟 \(\sum k\) 没有联系。
  然后想法是去套上 \(\sum k\)，然后就可以想到倍增，这样子浪费掉的也是 \(\sum k\) 级别的。

  没想出来倍增，废掉了。
  写代码的时候没开 ll 调了死久，666。

• Solution - Luogu P11401 [Code+#8 初赛] 普勒亚
  直接 SAM 套完建 fail 树然后启发式合并阿！
  其实线段树合并会更优，但是启发是合并跑挺块而且好些，不管了。

  笑点解析：

  inline void extend(int c) {
     int p = lst, now = ++tot;
     siz[now]++;
  

  没有在加入时更新 \(\operatorname{len}_{now}\) 可以过模板题。
  我：怎么这么久没用还能一次过，无敌了。
  但是这个是为啥，我个人认为我还是大致搞懂了 SAM 的，这个我真的不会解释了/kel

• Solution - Luogu P11402 [Code+#8 初赛] 图
  首先前面的结论很好发现，很好打出 \(\mathcal{O}(n^2)\)。

  然后仔细研究可以去拆式子，然后拆出来个东西。
  然后非常神秘的是这个存在递推式，我推了几个小时没推出来，又对着 std 推了半个小时才弄懂，，，

  但是这个有点厉害了，公式我存在着的，不慌直接粘。

• Solution - Luogu P11405 [RMI 2020] 秘鲁 / Peru
  首先 \(\mathcal{O}(n^2)\) 以及 \(\mathcal{O}(n\log n)\) 都是比较简单的。
  （那有人还是第二天重新想才会的？）

  然后优化需要用到一个很厉害的双栈模拟。
  有点牛了，之前没见过这玩意，学会了。

其实“Solution - Luogu P11408 [RMI 2020] 树咖 / Arboras”被划掉的原因单纯是还没写这题代码。

在阅读了官方题解后，我大概是会了，写在着防止后面又忘了。

首先有 dp 就是最大值次大值，然后最大值继续转移上去。
然后对于修改的 \((i, p_i)\)，只会改 \(p_i\to rt\) 的链。

考虑到因为只要不是最大值，就更新不上去了。
所以每次更新到的一定是一个从 \(p_i\) 开始的链，且只有可能最高点不是作为最高点的，这个直接暴力分讨就行了。

然后考虑作为最大值的这一部分，那么一样的，对于从 \(i\) 开始上来的这条链，一定也是经过 作为最大值 - 次大值或者不出现了 - 不出现了 这样的。

然后找到断点一样的分讨一下就可以啦。
看起来都可以用矩阵维护，因为涉及到最大值转为次大值的类轮换操作。

等一下，我怎么知道是不是最大值？？？
emm，好问题，回去想吧（

我猜测一下，一样可以矩阵，好像确实没啥问题（？），只要我维护的是这个最深的叶子节点就可以判断了，111。
还得回去仔细思考一下。

这样子说我突然想到了 Codeforces 2041K Trophic Balance Species。

为啥会想起我也不知道，额额，后面记得写个题解。
这个都是一个月前做的题了，我们当时找着这场 icpc 过了人少题的队问，基本每个人少题都问了，有点难绷。

说到 cf，圣诞节到了我觉得可以改改我以前懵懂时期开的几个小号的名字了。

第一是这个本身就不太好。
第二这个一看就知道是我阿/fn

我觉得还是得，撇清关系，这个号已经不是我的了 111。

我不会就这样被 ban 掉吧？？？

但是我也没拿过那些号打比赛，rizynvu 现在 cf 也没打过。
应该不会被 mike ban 掉吧（？）。

为什么感觉右眼（刻意）眨眼有点痛，应该问题不大吧（？）。

我要是以后在回家又晚上耍手机到凌晨真的找个时间给自己毙了阿。
在这样下去，这辈子有了。
还是得，拥有良好睡眠，拥抱健康人生（。

感觉宿舍的大家回家都或多或少熬夜（
只要不是回校那天的晚上，都会在关灯后颇有兴致的聊天。
但是回校那天感觉大家都是小讲一点就全都睡了，乐。

感觉班主任真的红温爆了。

大致梳理一下周五：

• 班主任发现最信任的课代表干出极端（？）恶劣事件，应该是可以遭校级处分（可能是正经处分了，而且可能更厉害）的级别，然后好像破防了。
• 下去做操又在教室抓到一堆不下去的。
• 当天 3 个做清洁的一个没来清洁问题扣分了。
• 有同学玩一体机，浏览一些学习无关东西。
• 知道了班上考试接近一半同学作弊（啥提前借答案，偷卷子，搜题），无敌了。

完蛋了明天是班会课，这下要没救了。

班上也是，神人神事越来越多了。

好在我为人正直来着，哼哼。