工艺 题意：给定长度为     n    n   n的序列，求字典序最小的长度为     n    n   n且与原序列循环同构的序列 思路：利用最小表示法（也有后缀自动机以及后缀数组的解法）  暴力的比较所有的     n    n   n个循环同构的串 纯暴力会被卡到     O   (    n   2    )    O(n^2)   O(n2)，因此需要加点优化，代码如下  #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)&...

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 and ...

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

陌上花开 第二遍写这个题了 题意：若某个元素的三个维度的值都小于等于另外一个元素，则是真的小于等于；给出一些元素，求等级分别为     0  <mtext>   </mtext>  n   −   1    0~n-1   0 n−1的元素数量；而一个元素的等级被定义为小于等于这个元素的元素数量。 思路：(⊙o⊙)…标准的板子，CDQ分治就是细节多一点 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<&...

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

矩形藏宝地 这题虽然题面有种自相矛盾的感觉，但是样例还是清晰的，简单题 题意：在一个二维平面上，求有多少个矩形是被包含在一个更大的矩形中的。 思路：伪四维偏序  由于题目竟然没有给出坐标的范围，因此我们拿到坐标还是离散化一下吧 现将所有的矩形按照     x   2    x2   x2（先按     y   2    y2   y2也行）从大到小排序，然后直接分治（至于为什么从大到小，想一下就好了） 在分治中为了保证第一维(     x   2    x2   x2)的有序性，要先处理左右两个区间，再考虑左区间对右区间的影响 然后将左右区间按照     y   2    y2   y2从大到...

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

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

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

动态逆序对（重庆OI） 先写一个CDQ分治的写法吧，主席树。。。希望我以后会补。 题意：先给定一个     1    1   1~     n    n   n的全排列，然后有     m    m   m次删除操作，求每次删除操作之前逆序对的个数。 思路：  题目说求删除操作之前逆序对的个数，反过来不就是每次插入操作之后逆序对的个数吗？然后如果能求出每次插入操作所增加的逆序对个数，再利用前缀和不就可以得到答案了吗？ 对，就是这么简单，把题目反过来，然后CDQ分治，CDQ部分难度比较低。 CDQ部分：第一维按时间维度（反过来的时间），第二维按照插入元素的位置排序（两遍），第三维就是直接把元素的...

query 这题和HH的项链简直是异曲同工之妙，只不过预处理不同，此题略巧妙些 题意：给定一个     1    1   1~     n    n   n的全排列，然后有     m    m   m个询问，每次询问求     [   l   ,   r   ]    [l,r]   [l,r]内满足条件的     p   a   i   r    pair   pair有多少对。条件为：     p   a   i   r   (   a   ,   b   )    pair(a,b)   pair(a,b)满足一个数是另外一个数的倍数即可 思路：  记录好每个数字的位置 预处理出每个数...

Random Access Iterator 唉！你能一手双向边秒了我？场上SB了，竟然天真的以为出题人给我的数据时会按照从父节点到儿子节点的顺序给我单向边。。。然后WA到mdbrsl 题意：给定一棵以     1    1   1为根的树（以后存树千万记得存双向边！），然后问从     1    1   1开始能到达最大深度的概率。细节补充：从某个父节点可以等概率的选择到达某个儿子节点，并且选择次数为儿子数，即在多次移动中只要有一次遍历到最大深度即可 思路：  一遍     d   f   s    dfs   dfs处理出最大深度，然后给最大深度的节点概率标记为     1    1   ...

Colorful String 比赛一开，我看的第一题就是这题。然后一看，回文串！那肯定回文自动机搞一下不就行了吗？再仔细一看，发现有个小地方我不敢确定，遂想用     m   a   n   a   c   h   e   r    manacher   manacher水过去，想了一小会，发现不好实现，于是又转战回文自动机。由于当时一下子想不起来回文自动机的两棵树的转移边有没有交叉的，马上去找了篇博客看一下树的形态。发现，嗯，应该是没有交叉的。于是马上敲了一个     d   f   s    dfs   dfs+状压，结果写的有点问题，费了点劲过了样例，     18   m   i  ...

Fire-Fighting Hero 赛后自己写了一个。。。因为舍不得开大数组，挂了三次。。。好在场上是队友做的，     1   A    1A   1A，hhh 题意：英雄从给定的     s    s   s点出发，求到所有点的最短路径最大值；消防员从     k    k   k个出发点随便选一个出发，求到所有点的最短路径最大值；并拿上面两个最大值进行比较，然后是“若，否则”的形式。 思路：  显然对于英雄来说直接跑一个单源最短路即可 对于消防员而言，可以新建一个超级源点，跟其他出发点连上边权为     0    0   0的边，也同样跑一遍单源最短路即可 然后，没有然后了，就这么简单...