8.12 Day5

推荐歌曲《我是逆蝶》。

A Divide Square

挖掘特殊点：有一个端点在边缘上。

如果我们扫 x 坐标，维护 lst 横 和交叉的 竖，非常不好维护，并且 TLE。

结论：一个交点会至少增加一个区域。证明显然。

当然还有一点 corner case。

B Cow Tennis Tournament

一开始想的是三元环会是怎的，推出的性质是错的，也不好做。（没注意到可以多次反转）

正难则反。对不合法的三元环计数。

发现性质非常好，只要有一个点出度是 2 就好了。

考虑枚举从一个点出发，答案就是 \(\dbinom {deg_x}{2}\)。

这个东西可以维护二维的邻接矩阵，每次求一行的全局和减去单点即可。

又是一个二维的问题了，容易想到扫描线，如何对操作进行差分。发现一次操作就是区间取反，可差分。

一次反转，我们找到对 \(a\) 影响的 \(l,r\)，对矩阵 \((l,l)\sim(r,r)\) 反转即可。

C Treasure

自然的思路就是枚举起点和终点。

这个宝藏的限制钥匙，最终应该是从树上一段 dfn 区间开始，到另一段区间，代价是 \(w\)。

考虑终点的这一维用扫描线处理。

经典问题之分类讨论：

• 满足祖先关系。找到 \(x\) 到 \(y\) 的第一个点 \(u\)，那么 \(u\) 子树外的所有点进入子树必然会经过 \(x\)。

• 没有祖先关系。就是子树走到子树的关系。

• \(x=y\)。发现简单算很容易算重。

又是正难则反，直接用 \(w\) 来减不经过这个点的方案。

不经过 \(x\) 是树上的经典问题，考虑子树内经过，子树外即可。

子树外面很简单，子树内部要枚举儿子点计算。

如果每次操作都枚举可以被菊花卡爆，所以要打标记最后统一处理一个点。

D k-d-sequence

注意排序后。

那么就和区间内的数值域连续差不多了。转化如下：

区间内所有 \(a_i\bmod d\) 相等，但是 \(a_i\) 两两均不相等。

这玩意可以用双指针和 cnt 数组求出。

需要 \(k\) 的数量就是 \(\max(a_i/d)-\min(a_i/d)-(R-l)\)。

然后就是 pudding monsters，单调栈动态更新一下，维护最值即可。

注意有 \(lst\) 的区间限制，为了避免写 sb 的区间线段树二分，我们可以直接把 \([1,lst]\) 前缀设成极大值。

E Colorful square

F 内部白点

做过。