“まだ動くまだ進む 物語の上を泳げ” —— 《スイマー》 分析 维护一个栈，每次加入一个值。 如果栈顶在之后也会出现并且比加入的值大就弹出。 这样使得每个值尽可能放在前面。 粗略的证明一下。假设有两个序列 A,BA,BA,B，AAA...

“遥か月を目指した 今日の空は 彼方西に流れた もう届かないや 届かないや”——《回る空うさぎ》 分析 首先对于每个坐标开一颗平衡树，要维护的东西需要全局取 max，但是自己不能取。 士气值和团结值在一个点没加进去之前是好算的，直接...

“「あるべき人間の姿へ」 「正しい人間の姿へ」 そう思えばなんだか 人間全てが汚く思えてくるな”—— 《不可解》 题意简述 给定一张点数为 NNN 的有向图，初始 pi(1≤pi≤i,1≤i<N)p_i(1\leq p_i \...

模拟赛考到了，正好写一下。 简介 圆方树是一种将图变成树的方法，解决一些路径连通性相关的东西或者是仙人掌。 描述 前置知识：点双连通分量。以下不考虑孤立点。 在圆方树中，原来的点为圆点，点双为方点。每个点双内部是一个菊花图 [1]...

“我仍然在无人问津的阴雨霉湿之地” —— 《世末歌者》 题意 高橋君有 NNN 瓶糖水，青木君有 MMM 瓶糖水。 高橋君的第 iii 瓶糖水有 AiA_iAi​ 份糖 BiB_iBi​ 份水。 青木君的第 iii 瓶糖水有 C...

都是典中典，我之前还不是很会。 简介 对于一颗正常的线段树，如果要支持所有版本都既可以访问又可以修改（完全可持久化），对于每个版本保存一颗线段树是不可接受的。 发现每次修改操作修改的点的个数只有 log⁡n\log nlogn 个，...

“かけがえのない日々を ここで 積みかさねて ひとつひとつ いまさらわかった”—— 《想いよひとつになれ》 题意简述 设 f(x)f(x)f(x) 为 xxx 的数字和。例如 f(158)=1+5+8=14f(158)=1+5+8=...

发现这部分学的最烂，稍微整理下。 强连通分量 定义 强连通的定义：有向图 GGG 强连通，当且仅当 GGG 的任意两个节点联通。 强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连...

很久之前写的烂尾笔记 根号数据结构 简介 顾名思义，复杂度含 O(n)O(\sqrt n)O(n​) 的数据结构叫根号数据结构，一般都运用了分块和分值的思想。 分块 简介 分块的基本思想是，通过对原数据的适当划分，并在划分后的...

“空高く舞う鳥へ かさねたハート”—— 《Jump up HIGH!!》 题意简述 有一颗深度为 DDD 的满 KKK 叉树，你需要剪掉一些边使其存在大小为 XXX 的联通分量，求最少剪掉的边的条数。 分析 考虑选择 所有 大小大...