日记

那我能说什么呢？

先把 6-28 模拟赛写了吧。

T1 # Link to T1

唐题。

T2 # Link to T2

我们发现，对于一个出现次数最多的字符 $a$ 和出现次数最少的字符 $b$，我们可以只考虑他俩在字符串里出现的次数。

如果 $a$ 和 $b$ 并非出现次数最多和最少的呢？
那么这种情况肯定会在枚举 出现次数最多的 字符时被考虑到。

我们把 $a$ 考虑成 $1$，$b$ 考虑成 $-1$。然后就是跑个最大子段和的事。

如何求 $-1$ 至少出现一次的最大子段和？二项式反演
我们把 $sum$ 初始赋值成 $-1$。然后对于第一个 $-1$ 不计算就是了。

T3 # Link to T3

至今还是没有驯服扫描线。

用 $(x,y)$ 表示选择 $x,y$ 两个点作为答案，$calc(x,y)$ 表示 $x,y$ 作为答案时的值。

首先，我们有口胡的结论：设 $l_i$ 表示满足 $h_{l_i} \le h_i \land l_i < i$ 的最大的下标，$r_i$ 表示 $h_{r_i} \le h_i \land r_i > i$ 的最小的下标。那么答案一定是 $(l_i,i)$ 和 $(i,r_i)$ 中的一个。可以用单调栈维护 $l_i,r_i$。

我们把 $(l_i,i)$ 和 $(i,r_i)$ 统一作为 $(x,y)$ 考虑。用扫描线和后缀最小值树状数组，枚举 $y$。对于每个当前 $y$ 对应的 $(x,y)$，用 $calc(x,y)$ 更新 $x$ 的值。对于查询，直接查询 $l$ 的后缀最小值就是了。

Jzzhu and Numbers# Link to

考虑枚举 $s$，我们可以计算出来是 $s$ 超集的方案数，然后容斥一下就是了，容斥系数就是 $(-1)^{\operatorname{popcount}(s)}$。

Counting Reorders# Link to

依然是二项式反演。我们钦定有 $i$ 个相邻的数相同，然后反演一下得到答案。

后日谈 # Link to 后日谈

尝试驯服扫描线。但是如上文所说，至少写日记的时候没有。
其实也并非没有驯服，就是看到某些题想不到扫描线。学可持久化数据结构学魔怔了。

然后今天招惹到了阿凉学姐，原因为了保护隐私就不说了。我以后再也不视奸别人的屏幕了

我就赌阿凉学姐找不到我的日记，找到了肯定是要戳我的。