TH911 Blog

「光阴不可测，岁月亦无歌。」

题解：[AHOI2009] 维护序列

洛谷P2023

题目传送门 与 线段树 2 几乎一模一样，直接放出代码。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 ...

Posted by TH911 on December 14, 2024

线段树详解

例题：线段树1（P3372）、线段树2（P3373）、[AHOI2009] 维护序列

之后很长一段时间都不会怎么深度碰 OI 了，防止哪天自己忘掉。 线段树 1 传送门 线段树 2 传送门 [AHOI2009] 维护序列 作用 线段树是算法竞赛中常用的用来维护区间信息的数据结构。 线段树可以在 $\mathcal O\left(\log n\right)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操...

Posted by TH911 on December 13, 2024

题解：[ARC173D]Bracket Walk

AtCoder ARC173D

题目传送门 题意分析 给定一张图，每一条边都对应着一个 ( 或 )，构造一条路径使得最终形成的括号序列是合法的。 首先，这个序列想要合法，长度肯定得是偶数，且其中 (、) 的数量相等。 那么我们将序列分开来看，已经能够匹配上的 ( 和 ) 先不管，那么匹配不了的只能形如 )...(。（否则就匹配上了） 考虑到合法路径一定是个环（起点、终点相同），因此我们可以通过更换起点的方...

Posted by TH911 on November 28, 2024

浅谈分数取模

费马小定理及证明 | 对质数取模

费马小定理 定理 若 $p$ 为质数且 $\gcd(a,p)=1$，有 $\large a^{p-1}\equiv1\pmod p$，即 $\large a^p\equiv a\pmod p$。 证明 取一质数 $p$ 和整数 $a$ 满足 $\gcd(a,p)=1$，即 $a$ 不为 $p$ 的倍数。 显然： \[\large \prod\limits_{i=1}^{p-1}i...

Posted by TH911 on November 27, 2024

FHQ Treap 之区间操作

例题：文艺平衡树 | 洛谷P3391

例题链接 您需要写一种数据结构（可参考题目标题），来维护一个有序数列。 其中需要提供以下操作：翻转一个区间，例如原有有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。 前置知识：FHQ Treap 参见FHQ Treap (无旋 Treap) 详解。 例题 AC 代码 1 2 3 4 5 6 ...

Posted by TH911 on November 22, 2024

FHQ Treap (无旋 Treap) 详解

例题：普通平衡树 | 洛谷P33699,P6136

例题链接 例题加强版链接 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 插入一个数 $x$。 删除一个数 $x$（若有多个相同的数，应只删除一个）。 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。 查询数据结构中排名为 $x$ 的数。 求 $x$ 的前驱（前驱定义为小于 $...

Posted by TH911 on November 21, 2024

C++神奇错误之switch内定义变量

[Error] jump to case label [-fpermissive]

出现 [Error] jump to case label [-fpermissive] 的原因是因为 switch 结构内不能够定义变量。 比如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 case 1: scanf("%d %d",&x,&y); auto p=color[y].upper_bound(dfn[x]); ...

Posted by TH911 on November 21, 2024

C++神奇错误之结构体内变量

undefined reference

写了一棵 FHQ Treap，但是报错： 1 2 C:\Users\ADMINI~1\AppData\Local\Temp\ccYwKop1.o 未命名2.cpp:(.rdata$.refptr._ZN5treap4rootE[.refptr._ZN5treap4rootE]+0x0): undefined reference to `treap::root' D:\1234\collec...

Posted by TH911 on November 21, 2024

如何通过js在IOS锁屏封面显示播放歌曲的信息

有些话不得不说，虽然我不太信任百度的AI只能回答，但这次给的真是正经答案…… 原本各类CSDN、百度知道、腾讯云……给出的回答都是不能，只有应用程序才能，但是我去 StackOverFlow 上搜索，竟然还搜到了：link。 通过一个叫做 Media Session API 的东西可以，然后尝试，成功。 然而，这是 百度AI 给的答案： 代码： 1 2 3 4 5 6 7 ...

Posted by TH911 on November 21, 2024

题解：[USACO19DEC] Milk Visits S

强化版：[USACO19DEC] Milk Visits G

题目传送门 强化版：[USACO19DEC] Milk Visits G。 题意重述 给定一棵无根树，每次给出 $a_i,b_i,c_i$，求 $a_i\sim b_i$ 的路径上是否存在一个点的权值为 $c_i$。 题意分析 首先这样一眼树链剖分，将一对多的非线性信息转化为线性信息后处理即可。 但是，本体还存在更简单的算法：倍增。 可以参考倍增 LCA，在从 $u...

Posted by TH911 on November 21, 2024

FEATURED TAGS
普及+/提高 题解 提高+/省选− 线段树 数学 贪心 倍增算法 树状数组 LCA 前端 字符串 普及/提高− 未完 树链剖分 模拟 RMQ ST表 二分 前缀和 堆 字典树 对顶堆 差分 平衡树 搜索 省选/NOI− 队列 C++错误合集 FHQ Treap KMP Manacher
ABOUT ME

要做一个优秀的 OIER

FRIENDS