ZROI 暑期高端峰会 A班 Day6 离线问题

FBI Warning：本文含有大量人类本质之一。

动态联通问题

允许离线。

模板，不讲了。

归并排序

%@)(#&%)++%($@)%!#(&%)(&@)))

主定理

U^(*#^$!^*%(@&)(!#*()!@&!)@)%&()!()$))))

快速排序

真·快速排序 $O(n^2)$（期望 $O(n\log n)$）

由不等式 $P(x\ge a)\le \frac{E(x)}{a}$（实际上是个很松的上界），快速排序被卡到 $\Omega(n^2)$ 的概率是 $O(\frac{\log n}{n})$，基本不可能。

Median of medians

把序列分成五等份。对每一列排序。由于一列只有五个数所以不用管复杂度。

找到第三行的中位数，并放到中间的位置。把比中位数小的放前面，大的放右边。那么这个中位数左上角的肯定更小，右下角的肯定更大。

复杂度分析：$T(n)=T(\frac{n}{5})+T(\frac{7}{10}n)+O(n)=O(n)$。（？？？）

经典问题

两道简单模板，不讲了。

CF958E3

$n$ 个红点，$n$ 个黑点，保证互不相同，没有三点共线，求一个红点到黑点的完美匹配，使得匹配之间的连线互不相交。保证有解。

$n\le 10^4$

首先明显对于任意的$)&!@(都是有解的。证明不难。

然后……突然离线。

咕了。

CF429D

给 $n$ 个数 $a_i$ 求
\[
\min_{i<j}((j-i)^2+(\sum_{k=i+1}^ja_k)^2)
\]
$n\le 10^5$

把一个点看成 $(i,s_i)$，答案就是平面最近点对的距离。

$O(n\log n)$。

CF938G

如果没有删边，就是个 [WC2011]XOR 了。

有删边，线段树分治即可。

？？？

给定一棵树，求有多少个大小为 $k$ 的点集 $S$，使得存在一个点 $u$，满足对于任意 $v\in S$，有 $dis(u,v)\le L$。

$n\le 10^5$

发现对于一个点集，满足条件的 $u$ 构成一个连通块，一定满足点数-边数=1。

那就可以对每个点计算多少个，对每条边计算多少个，加加减减就好了。

对于点怎么算呢？就是离他距离不超过 $L$ 的中选正好 $k$ 个的方案数。这个可以在点分树上跑，复杂度是 $O(n\log n)$。

边也差不多。建个虚点即可。

总复杂度 $O(n\log n)$。

CF1010F

Day 4 讲过。

[WC2014]紫荆花之恋

不管了。

动态区间第 $k$ 大

整体二分模板。

？？？

给定一个有向图，支持动态加边，求每次加边后点对 $(u,v)$ 数，使得 $u,v$ 可互达。

$n,q\le 10^5$

转化为求每条边，求什么时候 $(u,v)$ 开始可互达。

对于一条边可以二分，然后 tarjan 判一下。

对于所有边就要整体二分。如果是最暴力的，把 $1$ 到 $mid$ 的所有边放进去。复杂度炸了。

实际上由于是个分治，可以每次在前面已经缩起来的图的基础上，加边。

emmm……会意就好。

？？？

眼熟。

对于左边每个点维护最短路径树。

发现矩阵上每个点的父亲只有 $3$ 中可能（左，上，下），而且肯定是逆时针旋转的。

所以边的变化数是 $O(wh)$。

然而……怎么判断要不要旋转呢？

分治。求出 $[l,r]$ 的所有最短路径树。

求出以 $l$ 为起点和以 $r$ 为起点的最短路径树。对于在这两棵生成树上都相同的边，肯定在 $[l,r]$ 中所有树上都出现。

否则递归求。

复杂度简单（？？？）分析一波发现是 $O(wh\log w)$。（最短路是个分层图，可以 $O(wh)$ 求）

一些奇淫技巧

离线求逆元：普及组，不讲了。

树上分块+四毛子：（四毛子是啥？？？）

tarjan LCA：~~被 ST 表全面吊打~~也就没有那个预处理的 $O(n\log n)$。

巴特西