OI Journal

看到学长txc爷的blog里写了个“最近写的题目”

然后心血来潮准备自己也弄个这个东西

2019.11.3

Codeforces 557I

发现 BIT 可以实现平行四边形修改（把坐标系扭转一下，也就是把 $(x ,y)$ 映射到 $(x , x + y)$ ），考虑在超过边界的时候平行四边形可以被认为是一个直角梯形。直角梯形加，矩形减，用二维 BIT 维护，就能达到三角形加的效果。

2019.11.2

Codeforces 997E

考虑题目中要求的子串满足 $\max - \min = r - l$ ，把询问离线下来，枚举右端点，维护 $(\max - \min) - (r - l)= 0$ 的个数，本质就是维护最小值出现次数，注意打标记实现前缀和统计。

2019.11.1

Codeforces 585E

枚举前一半数的 $\gcd$ ，那么先算前一半数必须要在 $\gcd$ 的倍数中取，后面的数不在 $\gcd$ 的倍数中取的方案数，然后容斥，发现容斥系数正好是 $\mu$ ，证明可以感性理解（捂脸）。

2019.10.31

Codeforces 587D

前来膜拜一波神仙学长 txc 的集训队作业。

对于每个点，如果连着他的一条边被割了，那么与之相连的其他边都不能被割。

对于每个点连着的边的每种颜色，如果其中一条边没有被割，其他边都必须被割。

二分 + 前后缀和优化建图 + 2-SAT 即可。

2019.10.21

Codeforces 576D

对于每个存在某个航班从不可用到可用的分界点专门拿出来考虑。

中间可以用 floyd + 矩阵乘法维护每个点可不可以在这个时刻到达，可以用bitset优化。

对于每个分界点跑一遍多源最短路即可。

2019.10.20

2019.10.12

Codeforces 954I

$\Theta(6^2)$ 的枚举两个字符，然后发现如果在这个子串中存在 $s[i] \neq t[i]$ 则表示有必要把 $s[i]$ 和 $t[i]$ 两种字符合并，存不存在可以写成卷积性质然后 FFT / NTT 解决，后半部分可以并查集。

2019.10.8

Codeforces 573E

发现肯定存在一个分界点，左边不取，右边去，然后就可以平衡树维护了。严格证明在这篇题解里有。

2019.10.3

Codeforces 1172D

$\color{black}{\text{S}}\color{red}{\text{ooke}}$ 跟我讨论怎么出题。

结果 $\color{black}{\text{S}}\color{red}{\text{ooke}}$ 一句「你做过Portals没」就把话题变成了Portals做法讨论了……

在 $(x,1)$ 和 $(y,1)$ 放一对传送门，满足 $r[x] = 1, r[y] = 1$ ，这样子 $x$ 和 $y$ 一行一列就解决了，然后递归即可。

2019.9.26

2019.9.25

Codeforces 568E

由于是严格的LIS，所以每个数只能填一遍跟没有一样，然后用正常的 $\Theta(n \log n)$ LIS，做到gap的时候就枚举取哪个数，复杂度 $\Theta(mk + n \log n)$ ，还是比较松的。

BZOJ 3427

~~为什么POI全是权限题~~

发现最优解的每个元素 $\in \{-1, 0, 1\}$ ，然后瞎dp就可以了。

2019.9.23

Codeforces 555E

将原图中所有边双都拎出来，这些是可以做到强连通的。

拎出来之后就是树了，一条路径上一半设为向上另一半向下，判断有无矛盾即可。

2019.9.22

Luogu4768 [NOI2018]归程

$\text{Kruscal}$ 重构树…

跑出 $1$ 到每个点的最段路之后就可以搞了。

Luogu4197 Peaks

还是 $\text{Kruscal}$ 重构树…

把询问最小值改成第 $k$ 大即可。

2019.9.21

CometOJ #11 D

$\text{Kruscal}$ 重构树。

询问的是整一棵重构树上的子树的积。

但是因为 $0$ 的存在，不能树状数组，必须线段树。

比赛的时候写了个 $O(n \sqrt n \log n)$ 的莫队结果过不去。

最后半个小时的时候改写正解喜提 $\text{rush}$ 失败，心情极差。

2019.9.19

Codeforces 555D

每次二分当前这玩意儿可以掼到哪里，注意加一个如果两次掼回去的话可以直接取模，这样每次至少减少一半就是 $O(n \log^2 n)$ 的了。

2019.9.18

Codeforces 1209F

不美好的回忆 $\times 2$ …

虽然我打的很臭但是这场的题还是蛮有意思的…

先拆点，然后建出最短路 $\text{DAG}$ 之后分层贪心取，细节很多…

2019.9.17

Codeforces 1209E2

不美好的回忆…

E1的基础之上（ $f[i][j]$ 表示枚举到第 $i$ 列，状态为 $j$ 的行的最大值已经被确定）状压之后记录一下对于当前列，每个状态可以达到的最大和优化DP，并且注意只取 $max$ 值最大的 $n$ 列。

2019.9.16

Codeforces 1215F

前一天CF的F题。

建出 $M$ 个点，代表 $f \le i$ 是否成立，建图十分神仙，最后 $2-SAT$ 即可。

Sooke txdy

2019.9.14

Codeforces 553D

二分答案，得出对于每个点，最少有多少个被选中的点和他相邻，然后每次把已经不可能选进的点给删掉即可。

2019.9.13

2019.9.11

2019.9.10

Codeforces 536D

直接把每个点转换为坐标为 $\left(dis(s, i), dis(t, i)\right)$ 的点，然后就可以DP了。

2019.9.9

2019.9.6

Codeforces 521D

先把赋值操作转换成加操作，再把加改成乘，因为对于一个数上加的顺序是固定的，贪心即可。

打了场CometOJ。

这C题难度实在超标。

虽然做完之后发现不难但是我就是愣是没想到 $(x, x + 1) = 1$ 然后就可以 $O(2^{\text{质因数个数}})$ 暴力枚举了艹。

似乎是打CometOJ以来rk最高的一次（雾）毕竟我之前打的两场都是打到一半回家了（大雾）

顺便把标题改了下

2019.9.5

Codeforces 516D

令 $f(x)$ 为离 $x$ 最远的点离 $x$ 的距离。

两边 $dfs$ 之后以 $f(x)$ 最小的点为根，可以证明 $\forall x\ f(x) \geq f(fa(x))$ ，倍增即可。

2019.9.4

Codeforces 512E

想办法把两个状态变成一个 $(1, 3), (1, 4) ... (1, n - 1)$ 的三角剖分，一个正着做一个倒着做即可。

打了场CF。

$zxyhh$ 和 $Sooke$ 讨论了半个小时 $F$ ，得出了一个优秀的假做法。

我和 $Sooke$ 讨论了半个小时 $H$ ，得出了一个优秀的假做法，赛后问 $Isonan$ 爷发现距离正解仅仅差一个无解判断。

2019.9.3

Codeforces 506D

先用unordered_map维护 $n$ 个并查集，把每个联通块拎出来做根号分治即可。

Codeforces 512D

删掉环，他就是一个树形DP，连着环的可以直接做，没连环的枚举最后一个取了哪个点。

2019.9.2

Codeforces 504E

倍增 + 哈希维护一条链上的哈希值。

由于是倍增所以不用二分，是 $O(\log n)$ 的。

口胡完事（大雾）

都怪Sooke疯狂怂恿我口胡（大雾）

Codeforces 505D

对于一个联通块，如果有环，贡献为 $size - 1$ 否则贡献为 $size$ 。

~~我以为这是1D，做到一半：这真的是1D吗，然后去看了一下发现是2D~~

2019.9.1

一不小心就咕咕咕了3个月了…

都是高中生！怎么能这么咕咕咕！（这就是你晚自修跑出来玩电脑的理由？）

我要重新开始！

从现在的开始要反一下…越往上越新

之前的就懒得改了…反正也没什么人看这只菜鸡的blog

现在开始准备模仿zxyhh神仙每次随机找 $\texttt{Codeforces}$ 的Div1 D E做了。

2019.4.18

CF321E Ciel and Gondolas

今天的考试题

一道神奇的斜率优化

~~考场上随便打的暴力艹过去了，CF上特判了一组数据就过了~~

2019.4.19

昨天23:35到今天1:35打了一场CF，还行，小号上紫成功w

（这出题人B题放码农题然后CDE三道傻逼题算什么意思啊）

CF442D Adam and Tree

每次暴力向根更新+DP+剪枝是正确的。

因为答案最大是 $\log$ 的（树剖），所以封顶 $n \log n$

CF1154G Minimum Possible LCM

淦前天Div 3怎么全都是水题

直接用桶存一下数字然后再调和级数 $O(10^7 \ln 10^7)$ 枚举即可。

CF311D Interval Cubing

奇奇怪怪的找规律 + 线段树

发现所有数都在 $48$ 的时候形成循环，然后再用线段树打标记维护一下。

2019.4.21

CF746F Music in Car

又双叒叕是细节题

用两个 $set$ 维护一下整首播放的和半首播放的即可。

~~其实这sb题我22号才调出来的~~

~~但是我看21号没做其他题就放过来的~~

2019.4.22

CF176E Archaeology | LOJ #10132. 「一本通 4.4 例 3」异象石

结论：把需要求的点个按照 $DFS$ 序排个序，设得到的序列为 $s_1, s_2, s_3 ... s_m$ 那么这个时候的答案就是 $\frac{\sum\limits_{i = 1}^{m - 1}dis(s_i, s_{i + 1}) + dis(s_1, s_m)}{2}$ ，然后再用 $set$ 维护 $s$ ，和 $\sum\limits_{i = 1}^{m - 1}dis(s_i, s_{i + 1})$ 然后把 $dis(s_1, s_m)$ 单独拎出来，询问的时候加上就行了。

CF609F Frogs and mosquitoes

~~怎么又双叒叕是set~~

~~整天就知道set, set 我看CF你这个OJ就像个set~~

用两个set维护青蛙能影响的区间和未被吃掉的问题

完整题解：>Here<

2019.4.24 ~ 4.27

ZJOI期间，只打了一场CF，其他啥都没写

~~帮可爱的xay5421写了1个小时的假算法~~

2019.4.28

ZJOI2019爆完0回来了。

[CF295E Yaroslav and Points](<https://codeforces.com/problemset/problem/295/E)

不用离散化，算出 $[l, r]$ 之间每个点的贡献。

直接用 $fhq\ treap$ 维护一个区间的答案，滋瓷插入和删除即可。

CF542A Place Your Ad Here

首先枚举电视台。

钦点当前这个区间跟左边/右边其中一边不接触，用ST表维护一下区间内最右边/左边的点，然后特判一下广告区间包含电视台的区间的情况即可。

2019.4.29

CF618E Robot Arm

线段树 + 计算几何。

线段树区间 $[l, r]$ 维护一个向量，表示 $l$ 的起点和 $r$ 的重点之间的位置关系，注意开 $long\ double$ 和使用 $atan2()$ 防止过大精度误差。

CF558E A Simple Task

线段树大水题。

$26$ 棵线段树随便艹。

orz $spfa$ ODT神仙。

CF420D Cup Trick

使用 $fhq\ treap$ 逆着题意模拟即可。

一开始所有点都不确定，每次取出第一个，判无解， $erase$ + $insert$ 二连，最终把不确定的瞎填一通输出即可。

2019.4.30

CF316E3 Summer Homework

我们考虑线段树，一个段里维护 $\displaystyle\sum_{i = 1}^{n} a_i fib_i$ 和 $\displaystyle\sum_{i = 1}^{n} a_i fib_{i - 1}$ ，然后可以矩阵乘法预处理出 $\displaystyle\sum_{i = 1}^{n} a_i fib_{i + k}$ 和 $\displaystyle\sum_{i = 1}^{n} a_i fib_i$ ， $\displaystyle\sum_{i = 1}^{n} a_i fib_{i - 1}$ 的关系 $pushup$ 的时候从预处理好的里面取系数就行了。

CF1149C Tree Generator™

orz $S\color{red}{ooke}$ 红名巨爷。

首先两点之间一段可以转换为一个类dfs序状物，然后把距离可以做一个转换，变为序列上首尾相接的两端，前面那半段取反。接下来用线段树维护就行了。

CF653F Paper task

如果我们钦点左括号为 $1$ ，右括号为 $-1$ ， $sum_i$ 为 $\displaystyle\sum_{i = 1}^{i} a_i$ ，一个序列 $[l, r]$ 是括号匹配的当且仅当 $\displaystyle\min_{l \leq i \leq r} (sum_i) \geq sum_{l - 1}$ 且 $sum_r = sum_{l - 1}$ 那么用二分 + 后缀数组可以得出对于一个左端点，它右端点的范围。最后主席树维护一波即可。

CF1070B Berkomnadzor

先建出字典树（只针对需要被屏蔽的，白名单直接在他和根的路径中打个标记就好了）。

再判个无解。

然后遍历一遍字典树，尽量取浅的未被标记的节点即可。

2019.5.1

CF436E Cardboard Box

首先把所有的关卡按照通过第二关的难度排个升序，然后再对于枚举一个点 $i$ ，使得在 $i$ 前面的关卡拿了一颗星， $i$ 后面的关卡没拿第二颗星（可以证明肯定存在一个最优解使得满足性质的 $i$ 存在）。我们令 $w_j$ 为使第 $j$ 关拿到下一颗星的代价，然后用 $fhq\ treap$ 动态维护前 $n - i + 1$ 个最大的 $w_j$ 即可。

2019.5.2

打了场CF还unr了。。。今天一大半时间都在做前一天CF的题目w

CF887D Ratings and Reality Shows

显然脱口秀放在一个事件后面一个单位时间最优。

然后枚举放在哪个后面 + 模拟即可。

CF1156E Special Segments of Permutation

分治。

每次从一个线段中的最大值割开，维护一个 $map$ ，然后合并的时候启发式合并一波即可。

感谢 $L\color{red}{JC0118}$ 教我的orz

CF1156D 0-1-Tree

简单DP， $f1[i]$ 表示以 $i$ 点为开始的只有 $0$ 边的路径的数量 $f2[i]$ 表示…只有 $1$ 边的…数量。

两遍DFS解决，最后显然答案就是 $\displaystyle\sum_{i = 1}^{n} f1[i] * f2[i]$ 。

CF1156F Card Bag

期望DP。 $f[i][j]$ 表示取到第 $i$ 个，目前包里还有还有 $j$ 个球。

注意要开个 $f2$ 辅助 $f$ 的转移，否则要枚举下一个在什么地方取，就是 $O(n^3)$ 的。

2019.5.3

CF15D Map

把每个矩形的代价丢进 $set$ 里面，每次取出代价最小的。

再把因为这个矩形取了导致不能够取的矩形删掉，就可以了。

2019.5.4

luogu比赛正好和课外班撞了一大半。。。半个小时的时间只够打个 $T1$ 了（艹要是我T2的倍增优化建边打出来了我就rk前10了w）

T2边过个几天再补（咕咕咕）

洛谷P5343 【XR-1】分块

简单矩阵乘法。

很像CF1117D Magic Gems，我的题解：>Here<

把柿子改改就可以了。

2019.5.6

昨天回初中学校考试去了。。。

CF269D Maximum Waterfall

用一个线段树维护一下每个点上最下面的节点，每次一直往下面加入线段。

每次分治一下+DP转移即可。

CF513D2Constrained Tree

简单构造。

直接按照先序遍历为 $1...n$ 这个性质乱搞，每次取尽量少的点构造一棵树，如何还有不够的就在最后直接加

因为如果在最右边的一个节点的右子树上加，不管是先序还是后序，表现出来都是在序列最后加。

CF431E Chemistry Experiment

先离散化一波

然后直接大力二分 + 权值树状数组维护一波就行了。

2019.5.7

洛谷P5344 【XR-1】逛森林

裸倍增优化建边

注意要用一个类似ST表的东西来让它的点数小一个 $\log$

2019.5.8

CF286D Tourists

答案可以转换成很多个斜线和一个奇奇怪怪的矩形组成的图形的交

接下来用堆 + 单调栈维护一下即可。

CF845E Fire in the City

一个火区在一段时间后影响的时间是一个正方形，然后非常显然地想到二分答案

然后 $check$ 里面把所有火区影响范围的边界弄出来，离散化一下，可以得到最上、最下、最左、最右的未着火区，然后就可以确定最后一个的位置了。

2019.5.9

CF1117G Recursive Queries

我们令 $rb[i]$ 为 $i$ 右边的最近的比 $a[i]$ 大的数字的位置， $lb[i]$ 就是在左边的…

考虑一个数字 $i$ 会使 $[i + 1, rb[i] - 1]$ 和 $[lb[i] + 1, i]$ 区间内的元素的贡献+1（前提是 $i$ 在范围询问内）

两端分开来算，分别从左到右和从右到左加贡献 + 询问，线段树维护即可。

CF873E Awards For Contestants

首先，暴力枚举第一个和第二个，显然前二个里面最优的解的数量封顶是 $O(n^2)$ 的

接下来在前两个最优的情况下我们显然可以得到第三个的取值范围，就可以用 $st$ 表维护差分最大值了。

2019.5.10

CF257E Greedy Elevator

按照题意模拟。

用一个 $set$ 维护等电梯的和坐电梯的人即可。

CF446C DZY Loves Fibonacci Numbers

我们可以在线段树上的Lazy标记改成一个斐波那契数列的第一和第二项（斐波那契数列是可以直接相加的）

$pushdown$ 里面套一个矩阵乘法，就可以 $O(n \log^2 n)$ 解决了。

2019.5.11

CF455D Serega and Fun

分块。

每个块里开一个 $deque$ 和一个桶，每次修改的时候瞎jb乱搞一下就行了。

2019.5.12

CF515E Drazil and Park

套路性拆环，直接把序列倍长一遍就变成区间最大字段和问题了。

直接用线段树解决即可。

2019.5.13

CF1158C Permutation recovery

这是 $Sooke$ 验题的CF里的题

可以建图DFS过序过去，也可以树状数组乱搞。

CF551E GukiZ and GukiZiana

实名diss洛谷上的第二篇题解。。。代码是抄的，注释跟简单介绍分块基本没有区别 $O(q \sqrt{n \log n})$ 被硬生生说成了 $O(nq\log n)$ 不知道作者是怎么想的

就是分块块内有序查询的时候从左和右分别开始每个块内二分看是否存在要找的数。

~~似乎每块开个unordered_map就能去log了~~

2019.5.16

CF786C Till I Collapse

我们用主席树上二分可以得到每个地点可以最多往左走到哪里

每次询问从右往左暴力跳就行了，因为最多跳 $\frac ni$ 次，加起来就是 $n \log n$ 加上主席树上二分就是两只 $\log$ 的

2019.5.17

CF348C Subset Sums

把集合分成大小 $> \sqrt n$ 和大小 $< \sqrt n$ 的两种，加的时候大集合打标记小集合暴力加，并且给所有大集合加上所对应的贡献。

查询的时候对于大集合，我们把它的标记和加小集合对它的贡献加起来就行了。

小集合照样暴力即可，注意要加上修改大集合对它的贡献。

2019.5.18

CF1166E The LCMs Must be Large

结束了？结束了。

orz $\color{black}s\color{red}{pfa}$

CF650D Zip-line

发现答案只有可能原LIS + 1, LIS, LIS - 1中的一个

我们对于它是不是在原LIS节点作分类讨论，接下来用主席树维护即可。

2019.5.21

CF911G Mass Change Queries

线段树， $f[i]$ 表示在这个区间内， $i$ 全都变成了 $f[i]$ ，可以将 $f$ 认为是一种特殊的懒标。

每次下传的时候 $t[lc(cur)].f[i] = t[cur].f[t[lc(cur)].f[i]]$ 即可，右儿子也是这样。

CF240F TorCoder

直接丢篇完整题解好了

2019.5.22

CF992E Nastya and King-Shamans

每次往后跳，直接跳到 $s[j] > 2s[i]$ 的最小的 $j$

可以用线段树上二分实现。

2019.5.24

CF1030F Putting Boxes Together

其实最终的决策就是一个带权带修中位数

然后用一个线段树维护即可。

CF1051E Vasya and Big Integers

求出LCP之后就可以比较两个的大小然后就可以DP了

完整题解

2019.5.25

CF940F Machine Learning

考虑带修莫队，每次更新的时候分块 $O(1)$ 修改。

每个询问的时候 $O(\sqrt n)$ 查询即可。

2019.5.28

CF749E Inversions After Shuffle

对于每一个选择的区间，序列分成前面的，中间的，后面的三部分。

然后中间的每对数，贡献 $\frac 12$ ，其他的每个逆序对贡献 $1$ ，使用树状数组维护即可。

Dilute