停课后学习笔记

Michael Wong - 二两碘酊 / 2023-06-12 / 原文

\[\Large{\textbf{后竞赛时期} \quad \textbf{2023.5.12 - ?}} \]

用于记录做题过程中的小收获、经验教训。

P.S. 习惯上，我们称一个 OIer 停课后的阶段为后竞赛时期。 —— Walski Schölder（沃茨基·硕德）

5.12 周五

P4243 [JSOI2009] 等差数列

RE -> RE & WA -> AC

重申 构造函数 的重要性（lazy 的初值）
对于需要重载运算符的结构体，考虑 分离无关变量 撇出结构体以防止错误（L、R 的移出）
重申 数据范围 的重要性（lval、rval 的 long long）
没必要封装的，尽量不封装（class segment_tree 的删除）
对于占内存较大的变量，采用 全局声明（node 型 nd[N<<2] 的声明从类中移出，segment_tree 采用全局变量）
考虑特例的出现（\(s=t\) 的情况）
将每一部分维护到位（差分需要维护区间后一个元素）
将思路从板子灵活出来（四种区间不同计数 sum[4] 的运用，极大减少了 pushup 的工作量）

\(AC\ CODE\)

5.13 周六

学习分治，很多时候依靠递归实现

Sand Fortress

WA -> AC

注意二分边界（范围 \([1,n)\)）
注意大数乘法导致的溢出（#4 1000000000000000000 1000000000000000000）
巧妙判断（溢出的绝对偏大了，返回 LONG_LONG_MAX）

Abracadabra

这道题有思路，而且是对的，但是去看了题解，发现大家的标程很精炼。

灵活运用 std::max 等函数（int solve 里的四种分治的 max 和 min 发挥了 拆分区间、排除非法、缩小范围 等多个职能。）
把握分治的核心思想和大部分代码思路：基本都是二分和递归。

P2218 [HAOI2007] 覆盖问题

dfs 不会写……

熟练朴素的模拟

Empty Rectangles

下位黑，但是自己写不好……

加强逻辑能力（构建和校正代码）
正确评估复杂度（分治到边界复杂度是正确的）

大概的把 ZR D 班的分治都练完了，大概的有那么几个通式，有折半的，有交替分治的……等等等等

5.15 周一

P4315 月下“毛景树”

写好 pushdown ！
快读快写 别和 关闭流同步 一起用！！
树链剖分的第二个 dfs 要实现 重儿子优先遍历！！！

made……

5.19 周五

TTM - To the moon

不算毒瘤的可持久化线段树，刚开始写 WA 了，以为是主席树的问题，于是就改了一个有 pushup 的版本，后来发现是这句话

rt[++T]=change(rt[T-1],l,r,d,1,n);

的问题，在一些编译器中会成为未定义行为，先执行左边还是右边不确定。所以下次还是别写这样的，还有，多听 -Wall 哥的话，有用捏。

所以写了有上传

void pushup(int x,int l,int mid,int r) { t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+(mid-l+1)*t[t[x].ls].lz+(r-mid)*t[t[x].rs].lz; }

和没有上传纯是

t[x].sum+=(r-l+1)*k;

的版本。

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

总结了两个点警示后人。不算很难吧也，但是思路有点绕。是权值线段树合并 + 树上差分。

5.20 周六

今天是全国学生营养日，不是什么奇怪的 520 节，我们要积极发扬新发展理念，坚持协调发展，保证全国所有学生的营养充足。

P5494 【模板】线段树分裂

错误如下：

不开 long long 见祖宗。多练练怎么判断哪个变量该开朗朗。
分裂后为上传 pushup 节点。
查询 kth 到右儿子时没有给 k 减去左儿子权值。
分函数传参两次解 rt. ~~能不能别这么马……~~
未对 kth 超出总数情况特判 -1.

Distinctification

噫！暴切黑题！爽！

就是

判断当前集合大小用的 fa[i]==i 不对嗷，应该是 size[rt[get(i)]]==1;
连通的时候要考虑 \(x \geq N\) 或 \(y \geq N\) 的情况。因为到最后 连通块的大小和总数相当，导致 \(x\) 或 \(y\) 远远超出 \(n\) 了。这样下去会炸的！！！

5.22 周一

[省选联考 2023] 过河卒

差点没死。

首先是码量大，然后调了一圈之后发现错的是 in_range 的判断写成了 y<=n 而非 y<=m。

相似了。

然后那个 {1,0} 的初值，1 指的是当前出棋方必败，不是先手必败。

为什么拓扑排序能通过有环但不平局 / 多种选择取最优的情况？

我们观察我们的代码：

inline void toposort() {
	while(!topo.empty()) {
		auto u=topo.front(); topo.pop();
		if(ws[u].fr==1) {
			for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to) {
				if(ws[v].fr==inf) ws[v]={0,ws[u].sc+1};
				if(!ws_vis[v]) ws_vis[v]=1,topo.push(v);
			}
		}
		else {
			for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to) {
				if(--ind[v]==0) {
					if(ws[v].fr==inf) ws[v]={1,ws[u].sc+1};
					if(!ws_vis[v]) ws_vis[v]=1,topo.push(v);
				}
			}
		}
	}
}

首先，在反图中，环在结果一边的出点 出度大于 1.

对于 ws[u].fr==1 的情况，证明当前是出棋者的必败状态，则 出点是出棋者的必胜状态。所以无所畏惧，我们将他的 所有出点 入栈，不考虑入度是否清零。即，即使有环，我照样赢。

对于 ws[u].fr==0 的情况，证明 如果出环，出棋者必输。所以我们考虑将 无入度的出点 入栈。即，我 不能让你进入环内，或者从起点方向说，我 不会选择出环。

这同样也是拓扑排序可以在多种不同的选择中做出最优选择的原理。与环不同的是，多个选择的决定点 出度大于 1. 但异曲同工的是，魔改后的拓扑排序 永远对将当前点判定为出棋者胜的点给予最高优先级。

5.25 周三

P1763 埃及分数

dfs 再用结构体我是狗

dfs 再类型转换我是狗

1.20s TLE -> 1.10s AC -> 227ms AC

这俩 B 玩意是真扣时间

5.26 周五

P3304 [SDOI2013]直径

手写栈开栈空间里，于是爆了。

static 关键字可以在函数中声明 静态空间 的变量，和 全局变量 一个效果。
复制开销大的类函数建议传参使用 const T&，使用 const 左值引用可以减少开销，且适用于绑定右值的场景。

5.29 周一

平面最近点对（加强加强版）

及其优雅的分治，伟大的人类智慧。

本来是 5.26 的考试题，做的是平面最近点对（加强版），当时大家提出了很多的想法：

暴力 \(37\ pts\)
随机化 \(37\ pts\)
初级人类智慧 \(\mathbf{90\ pts}\) - 我们充分发挥人类智慧，认为在 \(x,y\) 轴上投影距离不远的两点距离一定也不远。于是我们两次 std::sort，遍历选取相邻两点求出距离。这样能够在 689ms 内跑到 \(90pts\) 的好成绩。

于是……
初级人类智慧 \(+\) 1e6 随机化 \(\color{red}\mathbf{100 \ pts}\) - 非常的屌，用这种及其离谱的方法把这题草过了。

当然，这不是正解。当时我提出了一个正义的（没错！初级人类智慧太不正义了！！！怒斥 agy！！！）最高分方法——
基于贪心的交替分治 \(\mathbf{60\ pts}\) - 这道题 zcq 讲过，当时只知道是分治，现在既然学了分治，当然照着正解做。本身是二维点题，基于 Empty Rectangles 的经验，选择 交替分治。但是众所周知，我的代码稳定性有待提高，ub 与日俱增。所以，为了更好地保证正确率，我没有完全横竖交替，而是加入了一点点的贪心，即每次选择 两侧距离分治线最近点距离最远的方向 进行分治。这样可以保证当时分治线上的最近点对后续被分在同一组，多少管点用。~~（其实可能并没有）~~

不过代码水平确实有提高，最后写完的时候基本上没有程序错误了，只是算法较劣，惨得 \(64\ pts\)。~~甚至没超过 agy 的人类智慧。~~
人类智慧 - 最高赞题解这样写到……

当然，对于我来说可能有点难写，不太会用旋转，而且貌似这种方法局限性也挺大的，还是老老实实连分治吧。
优化后的 \(x\) 轴分治 \(\color{gold}\mathbf{100\ pts}\) - 这种做法是真真切切连加强加强版都能切的，当然了我从 \(16\) 改到 \(100\) 也经历了很多的改善，接下来介绍一下：

经过了很多修改，最后事实是囧仙大佬题解的 C++ 底层数据结构实现版。（qs，估计到考场上我也不怎么会用指针……）
- 首先是从交替分治上修改，将其完全修改为 \(x\) 轴分治。出现一个问题：可能有多个点 \(x\) 坐标相等；进行修正，在分治到 \([l,r) , r-l \leq 2\) 时直接枚举相邻点之间距离取 \(\min .\) 交上去几乎是全 T，在 \(n \geq 1000\) 后甚至明显被交替分治算法甩在身后，必须上优化。
- 改变思路，由于可能有多个点 \(x\) 坐标相等，考虑以 std::sort 后的点数组下表作为分治依据，不再使用 \(x\) 轴，即 \([l,r)\) 表示第 \(l\) 个到第 \(r-1\) 个点的分治，而非坐标。大部分还是 T，但是加强版过了。
- 发现是 合并分治区间 的问题，即枚举的范围过大。题解中使用 std::vector 记录了所有与分治线距离 \(\leq ans\) 的点，在其范围中进行枚举。~~由于本人倔，~~ 考虑到存点用的都是数组而不是 std::vector，干脆就别用了。所以最后选择用手写栈实现。又是 T，又是 T 啊！！！
- 对比与题解的区别，修改了一下手写栈，之前把类指针直接当成编号用了……改回了一部分 WA；然后又把 long long 记录平方改成了 long double 记录距离最后再平方回来，莫名其妙的快了，解决了一些 TLE；最后将分治内部重新以 \(y\) 轴为准排序的算法从 std::sort 修改为和题解一样的归并排序 std::inplace_merge，TLE -> WA！历史性的突破！证明了归并排序在特定场景下的牛逼性！
- 寻找 WA 的原因，感谢出题人让我的样例 #2 没过，一会儿就发现了错点，是 std::inplace_merge 的两个序列本身的有序性没有保证好，因为我写了一句
```
if(r-l==2) return ans=std::min(ans,caldis(l,r-1)),void();
```
  导致了没有保证含有两个元素的序列有序。
  
  把这句删了，成功切掉。然后又优化了这个语句并加回来：
```
if(r-l==2) { if(p[l].y>p[r-1].y) std::swap(p[l],p[r-1]); return ans=std::min(ans,caldis(l,r-1)),void(); }
```
  大抵是因为少递归一层，非常成功地将时间缩短了 0.35s.

最后，放上这个优美的代码，我真的太爱这道题的 \(AC \ CODE\) 了：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
const int N=4e5+5;
const ld inf=1e18+18;
int n;
int s[N],top=0;
ld ans=inf;
struct point { ll x,y; } p[N];
inline ld caldis(int a,int b) { return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)); }
void solve(int l,int r) {
	if(r-l<=1) return;
	int mid=l+r>>1,cmpx=p[mid].x;
	if(r-l==2) { if(p[l].y>p[r-1].y) std::swap(p[l],p[r-1]); return ans=std::min(ans,caldis(l,r-1)),void(); }
	solve(l,mid),solve(mid,r);
	std::inplace_merge(p+l,p+mid,p+r,[](const point &a,const point &b){ if(a.y==b.y) return a.x<b.x; return a.y<b.y; });
	top=0;
	for(int i=l;i<r;++i) if(llabs(p[i].x-cmpx)<=ans) s[++top]=i;
	for(int dn=1,up=dn;dn<=top;++dn) {
		while(up<=top && p[s[up]].y<=p[s[dn]].y+ans) up++;
		for(int it=dn+1;it<up;++it) ans=std::min(ans,caldis(s[dn],s[it]));
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>n;
	for(int i=1;i<=n;++i) std::cin>>p[i].x>>p[i].y; 
	std::sort(p+1,p+1+n,[](const point &a,const point &b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; });
	solve(1,n+1);
	std::cout<<fsp(0)<<ans*ans<<'\n';
	return 0;
}

短短的 35 行，却是一部史诗。

6.4 周日

海尔霍尔泽正确性检验 - Hierholzer

需要注意的是，由于点可以重复，所以 不打标，采用 \(hd_u\) 记录遍历边数 的方法确定是否遍历结束所有边。
如果需要最小字典序，那么就只能使用 一般邻接表（通常是 std::vector），然后进行 std::sort。如果不需要字典序，可以考虑 前向星，速度会更快。
看起来很简单，只是在 判定确实存在欧拉路径 后 找合适的起点（根据性质，比如半欧拉图中无向图的 奇度点，有向图的 唯一出大于入点）然后 一路 dfs 到底。但事实上，在一个节点的所有出边 遍历结束 后入栈是一个经过了严谨思考与证明的巧思。从正面讲，可以证明合理性；从反面讲，可以证明正确性。应该加深理解。

6.11 周日

【模板】可持久化文艺平衡树

注意使用函数简化操作，增加正确性（增加 clone 函数）
注意 FHQ - treap 分裂区间 —— v 在左边！

6.12 周一

偏序

made，看不懂他们不加 \(\LaTeX\) 的 shaber 公式，我自己打吧……

偏序关系：集合内只有部分元素间在这个关系下是可以比较的
全序关系：集合内任何一对元素在这个关系下都是可以比较的

我们设 \(\operatorname{R}\) 是集合 \(A\) 上的一个二元关系，如果有：

自反性：对任意 \(x \in A,\) 有 \(x \operatorname{R} x;\)
反对称性：对任意 \(x,y \in A,\) 若 \(x \operatorname{R} y,\) 且 \(y \operatorname{R} x,\) 则 \(x=y;\)
传递性：对任意 \(x,y,z \in A,\) 若 \(x \operatorname{R} y,\) 且\(y \operatorname{R} z,\) 则 \(x \operatorname{R} z.\)

则称 \(\operatorname{R}\) 是 \(A\) 上的偏序关系，通常记作 \(\preccurlyeq.\)

一般来讲，二维偏序采用 树状数组 解决。将一维排序，另一维采用权值树状数组维护，按序查询 \([1,a_i-1]\) 后在 \(a_i\) 出插入 \(1\) 即可。可以看出，本质上这是 离线做法。以后用到的离线做法会越来越多。

之前做过的逆序对就是典型的二维偏序。最开始，我们是考虑采用线段树解决的；现在我们知道，对于 单点修改，区间查询，树状数组更加优秀（修改查询都是 \(O(\log n)\)）。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to)
const int N=5e5+5;
int n,cnt,a[N],o[N];
ll ans,t[N];
inline int lowbit(int x) { return x&(-x); }
inline void change(int x) { while(x<=cnt) t[x]+=1,x+=lowbit(x); }
inline int query(int x) {
	ll ans=0;
	while(x) ans+=t[x],x-=lowbit(x);
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>n;
	for(int i=1;i<=n;++i) { std::cin>>a[i]; o[i]=a[i]; }
	std::sort(o+1,o+n+1); cnt=std::unique(o+1,o+n+1)-o-1;
	for(int i=1;i<=n;++i) a[i]=cnt-(std::lower_bound(o+1,o+cnt+1,a[i])-o)+1;
	for(int i=1;i<=n;++i) ans+=query(a[i]-1),change(a[i]);
	std::cout<<ans;
	return 0;
}

什么？你想要二维偏序在线做法？有本事你树套树啊！

接下来我们就要搞一些好玩的，三维偏序。

一般来讲，如果考虑在线，每一维都需要采用一个数据结构来维护，典型的两个数据结构维护两位就是 树套树；而现在我们要处理三维，不可能树套树套树对吧，给评测机整个二倍空间都费劲，更何况你手写这东西也是要疯的。所以就只能考虑离线了。

我们要先介绍一个新的算法：cdq 分治。顾名思义，这是由陈丹琦引入国内 OI 界的。其核心思想是对需要计算贡献的点先 二分递归计算子问题贡献，再 合并子问题计算跨子问题贡献。

比如还是逆序对，我们就考虑将需要计算贡献的点 \([l,r)\) 分成 \([l,mid),[mid,r)\) 两个子问题，然后分别计算子问题贡献，最后计算 \(i \in [l,mid), j \in [mid,r)\) 的这种跨子问题贡献。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to)
const int N=5e5+5;
int n,cnt,a[N],o[N],s[N],top;
ll cdq(int *A,int sz) {
	if(sz==1) return 0;
	int M=sz>>1,*ptr1=A,*ptr2=A+M;
	ll ans=cdq(A,M)+cdq(A+M,sz-M); top=0;
	while(ptr2<A+sz) {
		while(ptr1<A+M && *ptr1>*ptr2) s[top++]=*ptr1++;
		ans+=ptr1-A,s[top++]=*ptr2++;
	}
	while(ptr1<A+M) s[top++]=*ptr1++;
	memcpy(A,s,sizeof(int)*top);
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>n;
	for(int i=0;i<n;++i) { std::cin>>a[i]; o[i]=a[i]; }
	std::sort(o,o+n); cnt=std::unique(o,o+n)-o;
	for(int i=0;i<n;++i) a[i]=std::lower_bound(o,o+cnt,a[i])-o+1;
	std::cout<<cdq(a,n);
	return 0;
}

你可能会想起逆序对的两种招牌做法——归并排序和树状数组，然后发现 这道题的 cdq 分治做法就是前者。从这点看，可以说 cdq 分治是归并排序的拓展，归并排序是 cdq 分治解决二维时的简单情况。