工艺 题意：给定长度为 n n n的序列，求字典序最小的长度为 n n n且与原序列循环同构的序列 思路：利用最小表示法（也有后缀自动机以及后缀数组的解法） 暴力的比较所有的 n ...

2-3-4 Tree 介绍 Conclusion 2-3-4 is great regarding memory and time complexity. Why isn’t it widely used? You may have noticed that while understanding 2-3-4 Tree is easy but implementing such a tree is complicated due to multiple node types and frequent switching of node types at each insertion a...

Continuous Intervals 线段树好题呀！比赛的时候根本看不出来，赛后惊叹“学到了！” 题意：给定一个数组，求数组内有多少连续区间。“连续区间”的定义：将区间内数字按大小排序后，相邻元素差值不大于1，可以等于0。 思路：绝妙的思路！线段树+区间修改+区间最小值及最小值个数+单调栈 可以将“连续区间”的定义等价为：区间最大值 − - −区间最小值 ...

陌上花开 第二遍写这个题了 题意：若某个元素的三个维度的值都小于等于另外一个元素，则是真的小于等于；给出一些元素，求等级分别为 0 <mtext>   </mtext> n − 1 0~n-1 0 n−1的元素数量；而一个元素...

天使玩偶 题意：有两种操作： 给二维平面上加入一个点 询问二维平面上到某个点最近的一个点（用曼哈顿距离来表示） 思路：标准的CDQ分治，离线处理两种操作 当想到CDQ分治后本题的重点在于如何处理曼哈顿距离，毕竟看到绝对值都头疼 我们最希望的是能去掉绝对值！这里有一种处理方法：我们只考虑每个询问点左下角的点，则显然可以去掉绝对值，用普通的CDQ分治，按照 x x x坐标排序，按照 ...

矩形藏宝地 这题虽然题面有种自相矛盾的感觉，但是样例还是清晰的，简单题 题意：在一个二维平面上，求有多少个矩形是被包含在一个更大的矩形中的。 思路：伪四维偏序 由于题目竟然没有给出坐标的范围，因此我们拿到坐标还是离散化一下吧 现将所有的矩形按照 x 2 x2 x2（先按 ...

粟粟的书架 一下子做了两个题？ 题意：一个问题求区间前K大的和，另一个问题求矩形内前K大的和。 思路： 前一个问题直接上主席树+二分搞定 后一个问题由于数据范围比较小，用 c n t [ i ] ...

森林 题意：有两种操作： 1. 将某两个点连起来（连边后保证为森林或者一棵树） 2. 询问两点之间路径上第K小权值（强制在线且保证询问合法） 思路：树上主席树+启发式合并 先离散化一下还是有必要的 连边后分别在每一棵树上建立主席树，每一棵树上的每一个节点的主席树维护从所在的树根到当前节点路径上的权值 合并的过程用比较小的树合并大比较大的树上 求解询问的关键： s = s ...

任务查询系统 题意：区间修改（修改区间每个位置某个数的数量，注意每个位置有多个数）+单点查询前K小的权值和+强制在线 思路： 由于主席树运用了前缀和思想，每个位置保存了所有权值的前缀和；因此若此题的区间修改利用差分思想，则主席树的每个位置恰好就维护的是自身位置（差分与前缀和相互抵消了），也就是不必手动求前缀和了。 这样我们就只需要离散化一下，然后利用差分思想处理所有的修改 而主席树部分跟普通主席树不同的是，主席树的每个位置并不是维护前缀和了（这样反而使代码更简单了），而是维护的自身位置的权值线段树（相当于n棵普通的权值线段树） 题面描述 #include &quot...

动态逆序对（重庆OI） 先写一个CDQ分治的写法吧，主席树。。。希望我以后会补。 题意：先给定一个 1 1 1~ n n n的全排列，然后有 m m ...

query 这题和HH的项链简直是异曲同工之妙，只不过预处理不同，此题略巧妙些 题意：给定一个 1 1 1~ n n n的全排列，然后有 m m ...

Random Access Iterator 唉！你能一手双向边秒了我？场上SB了，竟然天真的以为出题人给我的数据时会按照从父节点到儿子节点的顺序给我单向边。。。然后WA到mdbrsl 题意：给定一棵以 1 1 1为根的树（以后存树千万记得存双向边！），然后问从 1 1 1开...

Colorful String 比赛一开，我看的第一题就是这题。然后一看，回文串！那肯定回文自动机搞一下不就行了吗？再仔细一看，发现有个小地方我不敢确定，遂想用 m a n a c h e ...

Fire-Fighting Hero 赛后自己写了一个。。。因为舍不得开大数组，挂了三次。。。好在场上是队友做的， 1 A 1A 1A，hhh 题意：英雄从给定的 s s s点出发，求到所有点的最短...