二逼平衡树题目要求题目要求就是写一种数据结构，对于一个长度为$N(N≤50000)$的序列快速对以下的$M(M≤50000)$个操作快速的询问。 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区 ...

动态树—维护树的连通性的强力武器 功能LCT(link-cut tree)支持树（森林）的link,cnt,换根(makeroot)等等操作，而且也能维护树上的权值。 实现比较神奇。每个点都有一个preferred son。但是这不一定是由子树大小来决定的。他们两个之间的边称为preferred e ...

线性基定义张成设 $T⊆S$，所有这样的子集 $T$ 的异或和的集合称为集合 S $ S $的张成，记作 $ span(S)$。 线性相关对于集合$S$，如果存在一个元素$S_i$，使得$S$去除这个元素之后得到的集合 $S’$的张成$span(S’)$ 中包含$S_i$则称这个集合线性相关。 也就 ...

NOI2016区间在数轴上有$ n $个闭区间 $[l_1,r_1],[l_2,r_2],…,[l_n,r_n]$。现在要从中选出 $m $个区间，使得这$ m $个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$，使得对于每一个被选中的区间$ [l_i,r_i]$，都有 $l_i≤x≤ ...

计算几何解决几何问题的有力工具OI中的几何知识考查通常是需要大规模运算的问题。如果对于每道题都去现成的推公式，必将会浪费大量的时间。对此，可以解决一切几何问题的解析几何便十分常用。而将解析几何模式化的工具就是向量。 向量的基本运算向量的表示：$\vec a $ 向量a 向量的加减运算:满足平行四 ...

博弈博弈在OI中大概是解决两个人玩一个游戏，在两个人都采用最优策略的情况下，当前局面是必胜还是必败。 博弈大概分以下几种解决方法： 找出必胜策略，DFS或者DP直接求，SG函数 找出必胜策略这种方法并不常见。 例1：有一堆石子有$n$个，每次可以拿$1$个或者$2$个，不能拿就输了。问先手必胜还是必 ...

星座题目描述世界上有两种人，数星星的人和画星座的人为了探索我们头顶那美丽的星空，伟大的 C 学给了我们一张星图，这张星图 可以看做一个平面，其中包含了 $n $颗星星，每颗星星可以用平面上的一个点来表 示，C 学告诉我们这张星图中包含着多种神奇的$α- β- γ$星座，这些星座在平 面内构成了很多平 ...

bzoj 2432NOI2011兔农。斐波那契变形版，要推一些式子，不好推啊。但是可以打表找找规律，可以发现斐波那契数列在取模意义下是有循环节的。然后矩阵快速幂优化。还是见得不够多，自己推不出来啊。 bzoj 1023首次接触仙人掌啊，但是就是DP了，先学了学DFS，就是一个tarjan。然后看了看 ...

bzoj 1015这题挺有意思的。大意是在删除点的同时，输出连通块的个数。乍一看挺水的，反向操作就行了，用并查集维护，dfs求连通块，但是第一次全部WA了，还是忍不住看了数据。 自己没有想到的是，每次加入星球后，连通块会变多，想了想，因为有些星球被摧毁了，就不算连通块，所以需要在在恢复星球时，先把当 ...