农场道路修建

与没有上司的舞会类似，关键在于添加道路。
添加的道路一定是两点中一有一无或两无，则判断哪些点必须有，用总方案数减去不合法方案数即可。

P7828 [CCO2021] Swap Swap Sort

基本思路不难，没有想到根号分治（准确来说是不会，呃呃），以及在 \(x\) 确定的情况下不会 \(O(n)\) 处理 \((x,y)\)。（\((x,y)\) 表示每个 \(x\) 前 \(y\) 的个数之和）

每次更新 \(ans\) 涉及 \((x,y)\) 和 \((y,x)\)，可知 \(\underline{ cnt_x\times cnt_y=(x,y)+(y,x)}\) 。

根号分治：
根据 \(cnt\) 的大小，选择不同的统计 \((x,y)\) 的方式。（对于一种 \(cnt\)，最多出现 \(\frac{n}{cnt}\) 次）

• \(cnt_x\) 和 \(cnt_y\) 均较小时，直接暴力枚举 \(x\)，\(y\) 出现的位置，统计答案即可；
  复杂度 \(O(cnt\times q)\)

• 存在 \(cnt\) 较大时：
  复杂度 \(O(n\times \frac{n}{cnt})\)

  • \(cnt_x\) 较大时，将询问存储在 \(x\) 上，离线 \(O(n)\) 处理所有 \((x,y')\)，然后 \(O(1)\) 获取询问的 \((x,y)\)；
  • \(cnt_y\) 较大时，将询问存储在 \(y\) 上，离线 \(O(n)\) 处理所有 \((x',y)\)，然后 \(O(1)\) 获取询问的 \((x,y)\)；

总复杂度 \(O(cnt\times q+n\times \frac{n}{cnt})\)
根据基本不等式 \(cnt=\frac{n}{\sqrt{q}}\) 时复杂最优，即 \(cnt=100\) 为界限。