题意你需要维护一个可重集\(S\)，支持插入删除以及查询最大的方案使得给定正整数\(k\)，划分为\(k\)个非空子集的按位与结果之和最大。\(n\le10^5\)Sol先上个trie。然后考虑一次查询怎么搞。先转化一下，如果需要划分为\(k\)个子集，显然需要合并\(n-k\)次。我们只

题面传送门首先根据Dliworth定理，原问题等价于前缀LIS。考虑如何做到\(O(n^2)\)求出LIS的变化点（显然这只有\(n\)个）。按照值从小到大考虑，记\(f_{i,j}\)表示考虑到第\(i\)个值，长度为\(j\)的LIS最早在哪个前缀处出现，转移只需要two-pointers一遍就能更新。这个转

CF1987E题解题意给定一棵大小为\(n\)的有根树，各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了，赛后十五分钟调出来，可惜为时已晚。读懂题之后

题目描述给你一棵\(n\)个节点的树，每个节点有一种颜色，有\(m\)次查询操作。查询操作给定参数\(l\r\x\)，需输出：将树中编号在\([l,r]\)内的所有节点保留，\(x\)所在连通块中颜色种类数。每次查询操作独立。对于\(100\%\)的数据，所有出现过的数在\([1,10^5]\)之间，保证每

题目描述给定一棵\(n\)个点的树，在\(k\)个位置上存在蝴蝶，我们需要给\(n-1\)条边定向，如果一条边的起点有蝴蝶且终点没有蝴蝶，那么蝴蝶将被移动到终点，我们会按照给定边的顺序移动，问最终所有蝴蝶的树上距离的和的期望，答案除于\(\frac{k(k-1)}{2}\)，对\(998244353\)取模\[k\len\le300

视频链接：   C09【模板】可持久化字典树（Trie）-董晓-博客园(cnblogs.com)P4585[FJOI2015]火星商店问题-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(nlognlogn)#include<iostream>#include<cstring>#include<algorithm>#include<vect

给定n个结点，q次询问，每次询问分为三类：1xy，将x和y两个点连通，如果已经连通则不操作。2，撤销上一次连通操作，如果全部撤销完了则不操作。3xy，询问x和y是否连通。对于每个询问3，输出结果YES或NO。提示：可销撤并查集，使用按秩合并或启发式合并，不能用路径压缩。合并时记录操作的结点

前置知识：树的左旋、右旋。Splay树是一种平衡树。能够做到每个操作均摊\(O(\logN)\)。前言与上文AVL树不同之处在于，AVL树在任何操作结束后，都能保证每个节点的左右子树高度相差不超过\(1\)。相应地，每个操作都是严格的\(O(\logN)\)。而Splay树并没有对“平衡”的确切定义，任何结

AVL树是一种严格平衡的二叉搜索树，任何操作结束后，都能保证每个节点的左右子树高度相差不超过\(1\)。内容源自BV1rt411j7Ff-【AgOHの数据结构】平衡树专题之叁树旋转与AVL树。模板题：P3369【模板】普通平衡树。结构体定义&基本函数structnode{ intl;//左孩子int

发现今天做不了一点题，遂来补以前的比赛。B.378QAQandMocha'sArray秒了。排序，取最小的数记为\(x\)，再取最小的无法被\(x\)整除的数记为\(y\)，如果仍然存在无法被\(y\)整除的数，则无解。C.ChamoandMocha'sArray容易想到一个结论：如果一个数比它左边或右边的数小，那么

视频链接： P2147[SDOI2008]洞穴勘测-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(mlogmlogm)#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<map>usingnamespacestd;#definels(u<<1)

题意简述有一棵树\(n\)个点，你有一个门，你现在从一个你选定的点开始走，目标是所有点都至少访问一次。每次你可以选择：经过一条树边走到相邻点，花费\(1\)。将门放在当前点。将自己传送到门所在的点。求最小花费。\(n\le2\times10^5\)。分析先考虑根（出发点）固定怎么做。由于

视频链接： P4219[BJOI2014]大融合-洛谷|计算机科学教育新生态(luogu.com.cn)#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<map>usingnamespacestd;#definels(u<<1)#definers(u<<1|

视频链接： P5631最小mex生成树-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(nlognlogw)#include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;#definels(u<<1)#definers(u<<1|1)#d

题意简述给定一个\(N\)个节点的树，接下来有\(q\)次询问。每次询问给定\(a,b,c\)，请问存在多少个节点\(i\)，使得这棵树在以\(i\)为根的情况下，\(a\)和\(b\)的LCA是\(c\)。解题思路首先通过分析样例，我们发现：\(a,b\)的LCA一定在它们之间的简单路径上，所以如果\(c\)不在\(a,b\)之间的简

引入在点分治的过程中，它的遍历顺序会遍历每棵子树的重心，而这棵由重心生成的树会产生一棵新的树，便是点分树。常用来解决树上与树的形态无关的路径问题。过程如下图，它的点分树是它自己。因此可以看出一棵树的点分树可能是它本身。性质因为点分树\(\mathcal{O}(\logn)\)

abc355f直接贺lct维护mst的代码。思路观察到\(w_i\le10\)，考虑分开建\(10\)个图表示边权小于等于\(i\)的边组成的图。连并查集，记录当前图连了\(siz_i\)条边。可以发现第\(i-1\)个图是第\(i\)个图的子图。所以差分\(siz_i-siz_{i-1}\)可以得到原图的最小生成

CF1575E思路点分治，记录当前子树到分治中心的权值和和换车次数。将新子树的答案合并时分类讨论分治中心到子树祖先\(u\tov\)的颜色。树状数组维护前缀和。复杂度\(O(n\log^2n)\)。codeintn,k,a[maxn],ans;inthead[maxn],tot;structnd{ intnxt,to,fl;}e[maxn<<1];

一、主要思想很容易理解，我们将一个树以一个节点分割成若干个子树。对于这个节点，我们以一些方式统计和改变答案，然后不断地向子树递归。那应该选择哪个节点呢？显然是重心。树的重心有一个性质：所有子树的大小小于等于当前树的大小的二分之一。也就是说，这保证了递归层数\(log_2\)的

E-Boomerang(动态维护树的直径+二分)分析代码实现#include<bits/stdc++.h>#ifdefLOCAL#include"algo/debug.h"#else#definedebug(...)42#endif#defineintlonglongusingEdge=int;structHLD{ intn,times=0; std::vector<int>siz,top,

题目传送门前置知识无旋treap解法与luoguP3391【模板】文艺平衡树不同的是本题翻转后需要放到整个序列的末尾。由于需要翻转后放到末尾，故无旋Treap在维护文艺平衡树的过程中合并时跳着合并即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong

平衡树\(\tt{Treap}\)&\(\tt{Splay}\)壹.单旋\(\tt{Treap}\)首先了解\(\tt{BST}\)非常好用的东西，但是数据可以把它卡成一条链\(\dots\)于是，我们将\(\tt{Tree}\)与\(\tt{heap}\)(堆)合并，以保证平衡树\(\log\)的深度。具体地，我们可以使用旋转操作实现K8He的图

平衡树\(\tt{Treap}\)&\(\tt{Splay}\)壹.单旋\(\tt{Treap}\)首先了解\(\tt{BST}\)非常好用的东西，但是数据可以把它卡成一条链\(\dots\)于是，我们将\(\tt{Tree}\)与\(\tt{heap}\)(堆)合并，以保证平衡树\(\log\)的深度。具体地，我们可以使用旋转操作实现K8He的图

Treap弱平衡的随机性很强的老鼠看不懂的平衡树Q:为什么叫Treap?A:看看二叉搜索树(BST)和堆(Heap)，组合起来就是Treap其中，二叉搜索树的性质是：左子节点的值(val)比父节点小右子节点的值(val)比父节点大如果这些节点的值都一样，这棵树就会退化成一颗（？）链。对，我知道你在想

一类以并查集在建树过程中维护各种信息的值——克鲁斯卡尔重构树前身第一次见到是在zzu的校赛中，印象深刻H.SumofMaximumWeights题意：给定一棵树，求树上任意两点间最短路径中的最大边权的sum官方Solution：我们先将边按权值排序，这样每次处理的都是当前的最大权值处理每一