简介 是一种非旋平衡树。在学习这篇文章之前，还是先学习一下普通吧 优点 相比于普通的，它可以处理区间操作。相比于，它简洁易懂，代码也较短。 缺点 要比和慢 基础操作 最基本的两个操作就是分裂和合并。 分裂 即把一个分为两个。有按照权值分和按照大小分两种方式。具体方法:比着代码划拉划拉就知道了(懒)。按权值分 void split(int rt,int val,int &x,int &y) { if(!rt) { x = y = 0; return; } if(TR[rt].w <= val) { x ...

定义 所谓笛卡尔树，就是将给定的个二元组建成一棵树。使得如果只关注，那么这是一个堆。如果只关注,那么这是一棵二叉搜索树。 有没有很像。 与不同的是，笛卡尔树是可以在时间内构建的。而且如果给定key,那么是可以被卡成一条链的。 构造 以小根堆为例。 借助栈来完成。先按照val从小到大排序。然后用栈维护出最右边的一条链。即 显然，这条链上的val是自上到下递增的。key也是自上到下递增的。 因为已经按照val排好序了，所以当我们往这棵树里插入点的时候，权值一定是当前最大的了。所以插入的这个点要么是最右下的一个点，要么就是根并且其他所有的点都在左子树上。 然后考虑，只要沿着最右边这条链自下而上...

Day0 路上紧张到不行。特别担心今年会挂掉。 Day1 一塌糊涂T1似乎是积木大赛的原题。当时只用了个分治的做法在洛谷上水过去了。考场上发现能被卡成T2看了很久只好写了个exgcd，最后10分钟发现是个完全背包。哎。写完过不了大样例啊啊啊。果断删掉，又不小心把iostream库改了，只好用g++手动编译程序。哎。T3瞎几把推结论，乱写了几个部分分，以为是考到11：30呢。哎真不知道为啥自己先去写了t3，要是先去写t2说不定就能跳出来了。今天题不难却考炸了。大家考的都那么好。哎。想睡觉也睡不着。只想哭下午一起在活动中心看了个电影，心情好点了。无意中听到其他人已经民间数据已经200+了。哎，凉了...

Rand1 Day0 一大早就起床，结果忙活了整整一上午。12：20从gryz出发，路上发现把耳机和笔忘另一个背包里了(都怪老爸非得让我换背包)，15：30差不多就到山师了。 山师也是蛮漂亮的，花开得挺好。到处是牵着手的小情侣。啧啧啧~。恰逢清明，给他们烧柱香吧一时间难以表达内心的欢愉(第一次带着这么轻松的心情来考试，舒服)。</br>16：00到宾馆安排房间，魏老师把我叫过去问:"你跟孟老师一个房间吧"。顿时"好吧"(假笑...)，我还能怎么说！然后还只有一张房卡！！你交点押金多要一张会si么。。。不管了，先躲mjt屋里去了。。。一开始就这...

功能 李超线段树资瓷以下两种操作: 1.在二维平面内插入一条线段2.询问与直线相交的线段中，交点纵坐标最大为多少。 原理 结点 李超线段树的每个节点，都维护这一个优势线段。这个优势线段使得该节点所维护区间的中点在该优势线段上最大。 修改 考虑如何维护上面的结点呢。分三种情况讨论：1.该区间无优势线段或要插入的线段在该区间内完全在优势线段之上，将该区间的优势线段记为该线段并返回。2.要插入的线段完全被之前的优势线段覆盖。直接返回3.否则下放到左右两个子区间。 查询 从根节点走到查询位置的叶子结点。对路径上所有结点的优势节点在查询位置的取最大值即可。 时间复杂度 查询一次的时间复杂度显然为 修...

A 题意 有种饮料，每两个种类相同的饮料组成一组。每种饮料都有无限组。有个同学。每个同学有一种想喝的饮料。选择种饮料。问最多能有多少个同学喝到自己想喝的饮料。 solve 统计出每种饮料有多少个同学想喝。找出有奇数个人喜欢的饮料个数。答案就是 code /* * @Author: wxyww * @Date: 2019-07-17 22:34:23 * @Last Modified time: 2019-07-17 22:42:55 */ #include<cstdio> #include<iostream> #include<cstdlib> #in...

题目链接 思路 首先这是一个阶梯博弈。 我们将金币两两组合，如果对方移动前一个，那么我们把后一个移动相同的距离，局面相当于没有变化。如果对方移动后一个，就相当于\(NIM\)游戏中，取走了一些石子。 所以这个游戏也就是金币两两组合后，有\(\lceil \frac{m}{2}\rceil\) 堆石子，进行\(NIM\)游戏 统计方案 然后考虑如何统计方案。 根据上面的结论。也就是我们要找出\(\lceil \frac{m}{2}\rceil\)堆石子，使他们个数异或和为0。 \(f[i][j]\)表示异或和的前i位异或起来为\(0\)，已经有了j个石子的方案数。 就有如下的转...

题目链接 题意 有n个bug和s个系统。每天会等概率的在某个系统中找一个某一个bug。问找到全部n个bug并且在每个系统中都找到bug的期望天数。 思路 f[i][j]表示在j个系统中找到了i个bug的期望天数。 某天有四种可能： 1.在新的系统中找到新的bug，概率为\(\frac{(n-i)\times(s-j)}{n\times s}\) 2.在旧的系统中找到新的bug，概率为\(\frac{(n-i)\times j}{n\times s}\) 3.在新的系统中找到旧的bug，概率为\(\frac{i \times (s-j)}{n\times s}\) 4.在旧的系统中找到...

SG函数 作用 对于一个状态i为先手必胜态当且仅当SG(i)!=0。 转移 那怎么得到SG函数尼。 SG(i)=mex(SG(j))（状态i可以通过一步转移到j） 首先说一下mex。一个集合的mex是最小的没有出现在这个集合里的非负整数。 其实想一下这个也是挺明显的。状态i是先手必败态当前仅当i转移到的状态都是先手必胜态。同样，只要当前状态可以转移到一个先手必败态，那么当前就是先手必胜态。 小定理 对于两个独立的游戏A，B，他们的SG函数=SG(A) ^ SG(B) 这个比较难描述，看一下后面的题就明白了。 真模板题 先来娱乐一下 题面 给一个有向无环图，一开始在某个节点有个棋子，Alice和...

A.小y的序列 对于每种颜色，只要找到出现的最靠右的位置和最靠左的位置输出即可。如果找不到，那就藏在下一种颜色下面。 其实可以做到数据范围受限于 B.小y的线段 画出图来，可以发现具有单调性，只要计算出有多少个位置回到了源点就行了。 C.小y的质数 首先换个姿势看这个问题 求有多少个满足，并且 众所周知，与等价。 所以问题转化为求区间内有多少满足 因为区间比较大。所以可以对分解质因子。 然后容斥一下公因数，假设当前枚举到的质因子个数为。那就暴力搜索出来所有可能的公因数。然后计算内为当前公因数倍数的数字个数。然后容斥就行了。 D.小y的盒子 此题为送温暖题目。。 把所有的数字转换为三进制，对于每...

题目 思路 首先按照\(t\)排序！！！！ 首先考虑一个暴力\(dp\) 用\(f[i]\)表示前\(i\)个人到达地点所需要的时间。 那么就有如下的转移 \[f_i = min_{1 \le j \le i}(max(f_j,t_i) + max\{w_{j + 1} ... w_i\} * 2)\] 这样复杂度是\(o(n^2)\)的 考虑优化上面的\(dp\) 因为已经按照\(t\)从小到大排过序了，所以如果\(w_i \le w_{i + 1}\)那么第\(i\)这个人就一定是和第\(i+1\)个人一起跟优秀。所以就可以把第\(i\)人剔除掉。 用单调栈可以完成...

$cdq$分治主要思想就是将操作离线下来，然后分治之后统计二分之后，左边的修改对于右边查询的贡献。可以顶替很多复杂的数据结构。 学会下面这几类问题差不多就会$cdq$了。 个人认为看代码比较容易学。 二维偏序 先考虑这样一类问题 给出n个二元组$(a,b)$，求出有多少对$i,j$满足$a_i<b_i$并且$a_j<b_j$。 一个显然的思路就是，先按照$a_i$排个序，然后树状数组求下顺序对。那么，用$CDQ$分治应该怎么做呢。同样先按照$a_i$排个序，然后用归并排序求顺序对。归并排序就是最简单的$CDQ$分治。这种问题叫做二维偏序，可以发现，我们用$so...

题目链接 思路 用\(f[i]\)表示完成第\(i\)棵子树所需要得时间。 考虑如果有两个子树\(a\)和\(b\),如果先去完成子树\(a\)，那么对于花费得时间就是\(f[b] + siz[a] \times 2 + 1\) 所以如果有先遍历\(a\)更优秀的话。那么一定有\(f[b] + siz[a] \times 2 + 1 \le f[a] + siz[b] \times 2+ 1\) 即\(f[a] - siz[a] \times 2 \le f[b] - siz[b] \times 2\) 所以对于当前节点的每个子树按照上面的方法排个序。然后统计一下答案即可。 有个坑点就是必...

80分(最小割)思路 先考虑如果没有题目中东南角为\(1\)那个限制的话会怎样。 那么只要让每个点的海拔都是\(0\)就行了。这样不论怎样走，最后的答案都是0. 然后再考虑那个东南角为\(1\)的限制表达了什么。其实说明了最后的答案一定是右下角一部分海拔全部为\(1\)，左上角一部分海拔全部为\(0\)。 所以这样只要找到分界点就行了。 这就是最小割的裸题啊。以\((1,1)\)为起点，\((n+1,n+1)\)为终点跑一遍最小割就行了。 100分(对偶图)思路 直接最小割过不去后面的大数据。所以要用对偶图优化一下。 平面图就是像题目中这样两条边的交点都是顶点的图。 如图 图中\(9\...