打摆被抓自闭了
A感觉可以平衡规划，按一种颜色的点个数分类来计算
计算了一下块长和时间复杂度
(O(nsqrt{nlogn}))?
(n<=666666)?
写了还跑的飞快
居然正解就是这个
B是CodeChef 2014 April Challenge Final Battle of Chef
感觉可以(O(nlog^3n))在线维护
但是(n<=100000)？
再见
C是「LibreOJ NOI Round #1」动态几何问题
好像就枚举非平方因子得到
(sum_{i=1}^{n} mu(i)^2 lfloor sqrt{lfloor frac{n}{i} floor} floor lfloor sqrt{lfloor frac{m}{i} floor} floor)
对(lfloor frac{n}{i} floor)分块
然后算一个(mu(i)^2)的前缀和？
然后(sum_{i=1}^{n} mu(i)^2)可以化成
(sum_{i=1}^{sqrt{n}}mu(i) lfloor frac{n}{i^2} floor)
可以分块一下(O(sqrt[3]{n}))计算
于是就分块套分块？
结果1e12都慢到自闭
后来发现对(lfloor frac{n}{i} floor)分块
可以改成对(lfloor sqrt{lfloor frac{n}{i} floor} floor)分块
从(O(sqrt{n}))变成(O(sqrt[3]{n}))
于是就飞快了
改题发现B就是(O(nlog^3n))信仰跑非常自闭
主要是我分析了一波网上的整体二分好像不是(O(nlog^2n))而是(O(nlog^3n))
写了整体二分的做法，慢得邪恶