Day1

T1

这道题目离线相信大家都比较熟悉了。
首先使用最短路算法得到每个点回家的最短距离dis。

然后坐车可以通过一个没水的边组成的连通块，所以我们把所有边按照海拔高度排序，逐个加入图中，每一个连通块的代价就是该连通块内最小的dis值。这个可以使用并查集。

那么对于在线的情况呢？我们把操作可持久化，先排序做一遍，然后每次查询就好了。这样使用可持久化并查集可以得到一个可观的部分分。

但是依旧看上去不太能够通过，我们把连通块合并的过程建立成一棵树，也就是并查集合并两个集合的时候，我们选择新建一个父节点，然后两个集合的根节点连向这个父节点。于是我们就得到了一颗连通块合并顺序树。在每个父节点记录这次合并的海拔高度。然后对于一个点的查询，我们就可以遍历这个点到根节点的路径上的每个点，然后就可以判断答案，这部分采用树上倍增优化一下，就可以做到$NlogN$了。

所以本题最终复杂度$O(NlogN)$。

T2

首先冒泡排序的交换次数是等于逆序对个数的。
我们分析题目所写的下界$\frac{1}{2} \sum_{i=1}^{N} |i-p_i|$的具体含义。比如排列231就是好的，而排列321就是不好的。

分析其中原因发现，每次交换必须使得两个数字离自己正确的位置都更近一步才行。
形象一点就是说，如果我们把$p_i$和$i$看成一个由

建立一个线段树管理所有整点上的最优值。
每一个线段树节点存有一条 $X$ 轴范围和自己管理范围相同的线段，每次插入把一个插入线段拆成 $logN$ 段放入线段树内，也就是和普通线段树拆分区间一样，如果原来这个点上存有线段，则进行如下操作:

• 当前线段完全在原线段上方，丢弃原线段保留当前线段。
• 当前线段完全在原线段下方，丢弃现有线段。
• 当前线段与原线段相交，交点在左儿子范围内，当前节点保留红色线段，绿色线段丢弃右半部分后往做儿子下传。
  
• 交点在右边的情况同理。
• 交点在中间随意采用以上两种做法之一。

所以可以得知，如果有两个线段在一个线段树节点相交，最多会造成长为$logN$一条的连续下传。由于一条线段被加入$logN$个线段树节点之中，所以单词操作复杂度最多为$O(log^2N)$。

嗯，最近要做的事情有点多，效率要提高才行。

给自己一个规划。

12.12 ~ 12.17

周一到周五

上午

• 出题 *1
• 作业 *1

下午

• 微积分一章

晚上

• ML一章
• 物理一节
• 休息

周六

上午

• 讲课

下午

• 答疑
• 作业*1

晚上

• 打乒乓

周日

上午

• 休息
• 打乒乓

下午

• 休息

晚上

• 休息

先这样试一周，有问题再调整。

WARNING

希望看到的人能有所警醒。

鬼知道我今天上午经历了什么。

昨天尝试执行这个安排，上午的出题和作业都没有完成，下午的内容都缩水完成了一部分。觉得自己很废。

晚上洗澡开始想到自己生命有限，无法学完自己所有想学的内容，然后自己的生命终究会结束，然后开始惶恐，十分惶恐。想着自己随时可能因为以外死亡，而失去我所爱的一切。

然后一晚上惶恐，早上骑车上学也小心翼翼，担心被后面的车撞死，被建筑工地的钢管砸死，走在路上担心被掉下来的高空抛物砸死，整个人神经特别敏感。

回家之后开始担忧更多，上厕所担心地震被砸死，走路上随时想着中美可能开战，成都可能被核平，最近的防空点在人民公园，自己能否在限定时间内到达。坐在卧室担心厨房煤气泄漏爆炸，还特地去把煤气总闸关掉，前所未有的担心失去女朋友（单生狗哪来的女朋友），失去自己的生命。

然后开始上知乎搜索“害怕死亡”，各种都无法缓解我内心的焦虑和惶恐以及不安。然后想睡觉担心自己梦中死亡。

起来之后开始尝试出题，但是始终无法心安，上知乎继续搜索“死亡焦虑”，发现了这样一个特别对症了话题,然后看完第一个解答，浑身舒畅了许多。

然后开始搜索“焦虑症”，然后发现自己可能确实是有心理疾病，然后看了这篇,开始设定最低目标，

每日最低目标

• 做自己想做的事情，开心过完每一天。

然后一下真个人轻松了许多。

想了想自己为什么会这样，大概是保送后不能回班上的长期一个人独处的孤独以及对自己的长期高要求添加高压力，以及较为空闲的生活容易让人乱想，然后昨天没有完成自己的要求是压垮自己心理的最后一根稻草。于是陷入心理崩溃，现在整个人轻松多了，感觉自己确实需要一些时间去彻

进队后就一直不停地颓废啊——deeeep.io factorio 以撒胎衣+ "oxygen not included" "risk of rain"

还是要靠deedline才有生产力啊！那就三天一个规划吧

10.16~10.18

• arc058_D
• arc062_E
• arc062_F
• arc063_E
• arc063_F
• arc064_F
• arc065_E
• arc065_F
• arc066_E
• arc066_F

update 10.16

还有

• arc063_E
• arc063_F
• arc064_F
• arc065_E
• arc065_F
• arc066_E
• arc066_F

update 10.18

没能完成deadline

还有

• arc063_F
• arc064_F
• arc065_E
• arc065_F
• arc066_E
• arc066_F
• arc067_F
• arc068_E
• arc068_F

update 10.19

那么接下来 10.19~10.21

updatae 10.19

• arc063_F
• arc064_F
• arc065_E
• arc065_F
• arc066_E
• arc066_F
• arc067_F
• arc068_E
• arc068_F

update 10.20

• arc066_E
• arc066_F
• arc067_F
• arc068_E
• arc068_F

update 10.21

这个ARC066F 真的有毒！
57组数据错一组，数据内$300000$个询问错一个(/≧▽≦)/
找不到错啊！！！

• arc066_E
• arc066_F
• arc067_F
• arc068_E
• arc068_F

update 10.22

终于做完了！

update 10.23

• arc069_F
• arc070_F
• arc071_F
• arc072_E
• arc072_F
• arc073_E
• arc073_F
• ar

由于广电封杀国内VPN，所以国内VPN基本上全挂了。┑(￣Д ￣)┍

VPN没了怎么办？自己搭啊或者去国外卖啊

解决方案1——VPN类

VPN自己买的话有点小贵，由于大多数VPN支持3~5个设备登陆，而且设备之间不抢带宽，所以拉上几个好基友一起买一个高质量VPN还是很资磁的。

如果只有一个人呢？

计时VPN推荐——pureVPN

这家主要服务器在日本，大约有40个节点，有自己定制的客户端。下载速度大约10Mb/s，平时使用是没有什么问题的。

一个账号可以有5个设备同时登陆，短期大约10＄/月，长期（两年）3＄/月。

所以长期上还是很便宜的。

计流量VPN推荐——Greenss

据说是GreenVPN旗下某VPN。

30+的节点遍布全球各地（包括Taiwan和香港阿里云机房）。使用shadowsocks。

按照倍率计流量，（比如香港机房算2倍流量，但同时存在一些不计流量的机房[一般比较慢]）。

阿里云香港机房的速度十分给力，延迟也特别低。最高速度大约50Mb/s(有可能是我的带宽上限）。youtube可以无压力4K。

价格上，120G流量一年80元，300G流量一年144元。

解决方案2——VPS类

搬瓦工

便宜到不能再便宜了，20＄/年。搭个梯子，做个简单网页服务器还是够用的，网速很不稳定。

注意购买的节点一定要是有中国直连的洛杉矶或者凤凰城。

之前我有一个Fremont的节点，那个坑啊，掉包率5%，网速0.2~1.5Mb/s，延迟230ms。

相比之下洛杉矶中国直连的节点，掉包率0%，网速0.3~3Mb/s，延迟170ms。

搬瓦工刚买的时候的头几天很快，后来会变慢。

hustus

一番对比和朋友推荐之后，发现hustus不错。

洛杉矶节点，网速1~8Mb/s，延迟230ms，掉包率0%。

最便宜的OpenVZ 16＄/年,KVM 40＄/年。

CTSC,APIO,Thusc都完了啊！

还是算签到了点什么吧。。。

那么下一步计划核心——减少代码中的Bug数

Thusc计时表示，Debug时间远高于写代码时间。

所以做题的时候要尽量做题计时。

适当增加数学题的比例。

题库范围：Gym 省选题

update5.25

现在写代码和Debug 时间比为1:1.5。

开一个DZY love Math 系列作死吧

• DZY Loves Math
• DZY Loves Math II
• DZY Loves Math III
• DZY Loves Math IV
• DZY Loves Math V
• DZY Loves Math VI
• DZY Loves Math VII
• DZY Loves Math VIII

udpate 5.31

DZY系列果真不好做

• DZY Loves Math
• DZY Loves Math II
• DZY Loves Math III
• DZY Loves Math IV
• DZY Loves Math V
• DZY Loves Math VI
• DZY Loves Math VII
• DZY Loves Math VIII

还是做Atcoder吧

AGC 1~14
ARC 51~74

update 6.1

DZY系列真经典啊！

• DZY Loves Math
• DZY Loves Math II
• DZY Loves Math III
• DZY Loves Math IV
• DZY Loves Math V
• DZY Loves Math VI
• DZY Loves Math VII
• DZY Loves Math VIII

AtCoder 同一分值题目难度不同啊！

update 6.11

DZY 系列终于坑完了

Atcoder 好难啊！
最近智商好低啊！

Day1

T1

时空限制

时间限制：5s
空间限制：512M

题目大意

给出一个$N*M$的四连通网格，每个格子有一个颜色$C_{i,,j}$和一个权值$V_{i,j}$。其中有一些格子是坏的，不能够被选中。现在要求你选出一个连通块，使得该连通块至少含有$K$种颜色，且面积最小，满足前两种条件下所有选中格子的权值中位数最小（定义为第$\lfloor \frac{x+1}{2} \rfloor$小的数）。
输出最优连通块所含格子数和中位数。

如果中位数出错，格子数正确，则得到该点60%的分数

数据范围

$N*M \leq 233$
$K \leq 5$

大暴搜有5分

对于$40\%$的点 $N*M \leq$

先贴图不说话，感受悲伤与愤怒

依次说死法

A 上界判断出错 double精度不足导致二分死循环
B cout输出精度不足被判WA 数组开小一倍
C 被边界"0 1"卡死，没取摸

然后狂跌100+
这真是个悲伤的故事

!fuck

省选完了，那么开始准备NOI吧！

感觉这两天怎么这么颓啊！
把俄罗斯方块，超级玛丽等小时候玩的游戏又温习了一遍......
感觉吃枣药丸

首先，还是提高代码能力，这个短板太严重。
然后，补一下数论，这块实在是太弱了。

那么怎么解决这个问题呢？

等我有计划了再来补上，先颓去

update 4.14

SRM600-650 div1 hard

每天两道TC
代码能力练习list每天一道
每天看两小时具体数学
每天花两到三小时做VP（？VP做什么啊？）
再做一些杂题

等待每天打卡

• 4.16
• 4.17
• 4.18
• 4.19
• 4.20
• 4.21
• 4.22
• 4.24
• 4.25
• 4.26
• 4.27
• 4.28
• 4.29
• 5.1
• 5.2
• 5.3
• 5.4
• 5.5
• 5.6

update 4.28

感觉药丸，并没能完成。
算了还是分成deadline，还有去哪里找vp啊！！！CF都做过了啊！

重新制定吧
5.1之前

• 具体数学第四章
• SRM706
• SRM707
• SRM708

update 5.1

赶完了上面的内容
快要CTSC和APIO和Thusc了
重新制定计划

5.2~5.5

• SRM 709~713 补全计划
• 板子复习计划

板子复习：

• LCT*2
• FFT*2
• 点分治*2
• 凸包*2
• 半平面交*2
• 树套树

就先这么多吧 （好像有点多了）

哎，照着源代码打洞穴探测都要打错
还有两个错，还调了半个小时，吃枣药丸

update 5.3

余下：

• SRM 711
• SRM 712
• LCT*1
• 凸包*1
• 半平面交*1
• SAM
• 网络流
• 费用流

(怎么越变越多)

(可能要去找个妹子催我)

update 5.5

• LCT*1
• 凸包*1
• 半平面交*1
• SAM
• 网络流
• 费用流

update 5.10

• 凸包*1
• 半平面交*1
• SAM
• 费用流

题面描述

你有一个$N$个点$M$条边的带边权无向图，现在有Q个询问，每次询问给出三个数 $X_i,Y_i,Z_i$,询问如果两个人分别从$X_i,Y_i$出发，他们总共需要访问$Z_i$个点，行走的路径可以不是简单路径，那么他们访问的边的最大边权最小能使多少。

数据范围

$N,M,Q \leq 10^5$

题解

正解：整体二分+并查集 复杂度$O(NlogN)$

首先我们二分一个答案$x$，然后做一遍，拿并查集连接连通块。然后接下来所有询问分为，答案比$x$大的和答案比$x$小的。如果答案比$x$大，那么这些边一定早就被加入了，那么把没有加入的边和那