五月颓废记录

2log 的做法很神秘，很精妙。

放在线段树上做，每条加入的线段都看做 log 条线段。

对于线段树上的每条线段，都要开一棵子线段树。

总之要维护出每次加入一段线段后，哪些位置的线段被完全 pop 掉，不断 pop 就行了。

大概会了，等下再写

写一个 dp，\(f(i,0/1,0/1)\) 表示看了 \(i\) 个课，在哪个教室，另一个教室此刻的课有没有看过，此时的最小时间。

然后只有两种转移，二分一下就可以转移了。

不太会通信题。

首先题目中给出了 A 和 B 的集合大小，这是要用上的，这点就没想到。

经过转化后变成了 A 和 B 的集合大小相等，要求上中位数或下中位数。

然后就好做了很多，可以让 A 和 B 互相发中位数的 highbit。每次可以集合大小减半或值域减半。

感觉好难啊！！

对 \(T_1\) 点分治，设分治中心为 \(u\)。

讨论 \(T_2\) 中路径的两个端点来源（只可能来自 \(T_1\) \((u,x)\) 路径上，在 \(T_2\) 中距离 \(u\) 最远的两个点）。

给每个点赋随机权值 Xor Hash，然后转化成了另一个统计问题，就可以做了。

很久之前看过这题，会一个高复杂度的做法，现在来补一下 \(n^2\) 做法。

考虑容斥把矩形并变成矩形交，矩形交仍然是一个矩形。

很牛逼的题。

关键思想：确定最高位的一段 1，然后递归判定，复杂度可以证明是对的。

考虑猜结论，想一想对于一个集合怎么判定能不能生成。

如果能生成一个 101010101 和 1010 , 那可以生成 10101010 和 10101，也就是可以把长的串最后一位移到短的串上。

那可以先写一个贪心，贪心生成一组串 \(a_1,a_2,...,a_n\)，使得 \(a_1\) 最大，然后 \(a_2\) 最大，以此类推。

这样可以猜测一个集合是由 \(a_1,a_2,...,a_n\) “从长的末尾移动字符到短的” 来生成。

那么充要条件就是对于前 \(i\) 长的串，\(0/1\) 的个数 \(\le a_1,...,a_i\) 中 \(0/1\) 的个数，可以写一个 \(O(n^3\log n)\) dp。